A multivariate Weierstrass iterative rootfinder

ABSTRACT

We propose an algorithm to compute simultaneously all the solutions of an algebraic system (of n equations in n variables) that define a zero-dimentional variety. This new approach generalises the univariate Weierstrass's method. We study the arithmetic complexity of this method that has a quadratic convergence in a neighbourhood of the solutions. Hereafter, we describe a method based on the iteration function of the multivariate Weierstrass's method and on the continuation method for computing the roots of polynomial systems. Finally we describe some numerical experiments of those methods.

REFERENCES

• 1: ABERTH, O. Iteration methods for finding all zeros of a polynomial simultaneously. Mathematics of Computation 27 (1973).
• 2: BELLIDO, A.-M. Construction de fonction d'itration pour le calcul simultan des racines d'une quation f (s) = O. C.R. Acad. Sci. Paris (1992).
• 3: BELLIDO, A.-M. Construction de fonctions d'itdration pour le caleul simultand des solutions d'dquations et de systmes d'dquations algdbriques. PhD thesis, Universita Panl Sabatier de Toulouse, 1992.
• 4: BELLIDO, A.-M. Construction of iteration functions for the simultaneous computation of the solutions of equations and algebraic systems. Numerical Algorithms 6 (1994), 313-351.
• 5: BINI, D. Numerical computation of polynomial zeros by means of aberth's method. Numerical Algorithms 13 (1996), 179-200.
• 6: BLUM, L., SHUB, M., AND SMALE, S. On a theory of computation and complexity over the real numbers: Np-compleness, recursive functions and universal machines. Bulletin of the American Mathematical Society 21, 1 (July 1989), 1-46.
• 7: Cox, D., LITTLE, J., AND O'SHEA, D. Heals, Variety and Algorithms. Springer-Verlag, New York, 1996.
• 8: Jean-Pierre Dedieu , Steve Smale, Some lower bounds for the complexity of continuation methods, Journal of Complexity, v.14 n.4, p.454-465, Dec. 1998 [doi>10.1006/jcom.1998.0486]
• 9: DURAND, E. Solution numdrique des dquations algdbriques, vol. 1. 1968.
• 10: ELKADI, M., AND MOURRAIN, B. Gomtrie algbrique effective : de la thorie aux applications. Notes de cours, prpublication.
• 11: FAUGIRE, J.-C. A new efficient algorithm for computing grSbner bases (f4). Journal of Pure and Applied Algebra 139 (1999), 61-88.
• 12: FROMER, A. A unified approach to methods for the simultaneous computation of all zeros of generalized polynomials. Numer. Math. 54 (1988), 105-116.
• 13: Birkett Huber , Bernd Sturmfels, A polyhedral method for solving sparse polynomial systems, Mathematics of Computation, v.64 n.212, p.1541-1555, Oct. 1995 [doi>10.2307/2153370]
• 14: KERNER, I. Ein Gesamtschrittverfahrenzur Berechnung der Nullstellen yon Polynomen. Numer. Math. 8 (1966), 290-294.
• 15: LASCOUX, A. Note on interpolation in one and several variables, http://schubert.univ-mlv.fr/al/.
• 16: Lb T. Numerical solution of multivariate polynomial systems by homotopy continuation methods. Acta Numerica (1997), 399-436.
• 17: MOURRAIN, B. Isolated points,duality and residues. Journal of Pure and Applied Algebra 117 F 118 (1996), 469-493. Special issue for the Proc. of the 4th Int. Symp. on Effective Methods in Algebraic Geometry (MEGA).
• 18: Bernard Mourrain , Victor Y. Pan, Multivariate polynomials, duality, and structured matrices, Journal of Complexity, v.16 n.1, p.110-180, March 2000 [doi>10.1006/jcom.1999.0530]
• 19: Bernard Mourrain , Philippe Trebuchet, Solving projective complete intersection faster, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.234-241, July 2000, St. Andrews, Scotland [doi>10.1145/345542.345642]
• 20: SMALE, S. Complexity theory and numerical analysis. Acta Numeriea (1997), 523-551.
• 21: VASCONCELOS, W. v. Computational Methods in Commutative Algebra and Algebraic Geometry, vol. 2 of Algorithms and Computation in Mathematics. Springer-Verlag, 1998.
• 22: Jan Verschelde , Pierre Verlinden , Ronald Cools, Homotopies exploiting Newton polytopes for solving sparse polynomial systems, SIAM Journal on Numerical Analysis, v.31 n.3, p.915-930, June 1994 [doi>10.1137/0731049]
• 23: WEIERSTRASS, K. Neuer Beweis des Satzes, dass Jede Ganze Rationale Function einer Verinderlichen Dargestellt werden kann als ein Product aus Linearen Functionen derselben Verinderlichen. Mathematische Werke (1903). Tome 3.
• 24: YAKOUBSOHN, J.-C. Simultaneous computation of all the zero-clusters of a univariate polynomial. Submitted, 2000.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.3 Languages and Systems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Polynomials, methods for

General Terms:
Algorithms, Experimentation, Measurement, Performance, Verification