Newton's method: a great algebraic algorithm

ABSTRACT

The analytic concepts of approximation, convergence, differentiation, and Taylor series expansion are applied and interpreted in the context of an abstract power series domain. Newton's method is then shown to be applicable to solving for a power series root of a polynomial with power series coefficients, resulting in fast algorithms for a variety of power series manipulation problems. Sample applications of a FORMAC implementation of Newton's method as an algebraic algorithm are presented.

REFERENCES

• 1: Borodin, A. and Moenck, R. (1974) Fast modular transforms. J. Comput. System Sci. 8: 366-386.
• 2: Borodin, A. and Munro, I. (1975) The computational complexity of algebraic and numeric problems. American Elsevier, New York.
• 3: Brent, R.P. and Kung, H.T. (1976) O((n log n)&frac32;) algorithms for composition and reversion of power series. In: Analytic computational complexity, J.F. Traub (ed.). Academic Press, New York.
• 4: Cook, S.A. (1966) On the minimum computation time of functions. Ph.D. thesis, Harvard U.
• 5: Godement, R. (1968) Algebra. Houghton Mifflin, Boston.
• 6: Henrici, P. (1964) Elements of numerical analysis. Wiley, New York.
• 7: Peter Henrici , William R. Kenan, Applied & computational complex analysis: power series integration conformal mapping location of zero, John Wiley & Sons, Inc., New York, NY, 1988
• 8: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 9: Kung, H. T. (1974) On computing reciprocals of power series. Numer. Math. 22: 341-348.
• 10: Moenck, R. and Allen, J. (1975) Efficient division algorithms in Euclidean domains. Research report CS-75-18, U. of Waterloo.
• 11: A. C. Norman, Computing with Formal Power Series, ACM Transactions on Mathematical Software (TOMS), v.1 n.4, p.346-356, Dec. 1975 [doi>10.1145/355656.355660]
• 12: Schönhage, A. and Strassen, V. (1971) Schelle Multiplikation grosser Zahlen (Fast multiplication of large integers). Computing 7: 281-292.
• 13: Sieveking, M. (1972) An algorithm for division of power series. Computing 10: 153-156.
• 14: Strassen, V. (1973) Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten. Numer. Math. 20: 238-251.
• 15: Tobey, R., et al (1969) PL/I FORMAC symbolic mathematics interpreter. IBM Contributed Program Library, 360D-03.3.004, Hawthorne, N.Y.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Iterative methods

General Terms:
Algorithms, Theory