Computing the multiplicity structure in solving polynomial systems

ABSTRACT

This paper presents algorithms for computing the multiplicity structure of a zero to a polynomial system. The zero can be exact or approximate with the system being intrinsic or empirical. As an application, the dual space theory and methodology are utilized to analyze deflation methods in solving polynomial systems, to establish tighter deflation bound, and to derive special case algorithms.

REFERENCES

• 1: Robert M. Corless , Patrizia M. Gianni , Barry M. Trager, A reordered Schur factorization method for zero-dimensional polynomial systems with multiple roots, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.133-140, July 21-23, 1997, Kihei, Maui, Hawaii, United States [doi>10.1145/258726.258767]
• 2: D. Cox, J. Little, and D. O'Shea, Using Algebraic Geometry, Springer Verlag, 1998.
• 3: D. W. Decker, H. B. Keller, and C. T. Kelly, Convergence rate for Newton's method at singular points, SIAM J. Numer. Anal., 20 (1983), pp.296--314.
• 4: J. C. Faugère, A new efficient algorithm for computing Göbner bases, Journal of Pure and Applied Algebra, 139 (1998), pp. 61--88.
• 5: W. Fulton, Intersection Theory, Springer Verlag, Berlin, 1984.
• 6: G.-M. Greuel and G. Pfister, A Singular Introduction to Commutative Algebra, Springer Verlag, 2002.
• 7: Gert-Martin Greuel , Gerhard Pfister , Hans Schönemann, SINGULAR — A computer algebra system for polynomial computations, Symbolic computation and automated reasoning, A. K. Peters, Ltd., Natick, MA, 2001
• 8: Hidetsune Kobayashi , Hideo Suzuki , Yoshihiko Sakai, Numerical calculation of the multiplicity of a solution to algebraic equations, Mathematics of Computation, v.67 n.221, p.257-270, Jan. 1998 [doi>10.1090/S0025-5718-98-00906-5]
• 9: A. Leykin, J. Verschelde, and A. Zhao, Newton's method with deflation for isolated singularities of polynomial systems. Preprint, (2004).
• 10: T. Y. Li , Zhonggang Zeng, A Rank-Revealing Method with Updating, Downdating, and Applications, SIAM Journal on Matrix Analysis and Applications, v.26 n.4, p.918-946, 2005 [doi>10.1137/S0895479803435282]
• 11: F. S. Macaulay, The Algebraic Theory of Modular Systems, Cambridge Univ. Press, 1916.
• 12: Dinesh Manocha , James Demmel, Algorithms for intersecting parametric and algebraic curves II: multiple intersections, Graphical Models and Image Processing, v.57 n.2, p.81-100, March 1995 [doi>10.1006/gmip.1995.1010]
• 13: M. G. Marinari, T. Mora, and H. M. Möller, On multiplicities in polynomial system solving, Trans. AMS, 348 (1996), pp.~3283--3321.
• 14: H. Michael Möller , Hans J. Stetter, Multivariate polynomial equations with multiple zeros solved by matrix eigenproblems, Numerische Mathematik, v.70 n.3, p.311-329, May 1995 [doi>10.1007/s002110050122]
• 15: T. Mora, Solving Polynomial Equation Systems II. manuscript.
• 16: Schuichi Moritsugu , Kazuko Kuriyama, On multiple zeros of systems of algebraic equations, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.23-30, July 28-31, 1999, Vancouver, British Columbia, Canada [doi>10.1145/309831.309846]
• 17: T. Ojika, Modified deflation algorithm for the solution of singular problems, J. Math. Anal. Appl., 123 (1987), pp.199--221.
• 18: Andrew J. Sommese , Jan Verschelde , Charles W. Wampler, Numerical Decomposition of the Solution Sets of Polynomial Systems into Irreducible Components, SIAM Journal on Numerical Analysis, v.38 n.6, p.2022-2046, 2001 [doi>10.1137/S0036142900372549]
• 19: R. P. Stanley, Hilbert function of graded algebras, Advances in Math., 28 (1973), pp. 57--83.
• 20: Hans J. Stetter, Analysis of zero clusters in multivariate polynomial systems, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.127-136, July 24-26, 1996, Zurich, Switzerland [doi>10.1145/236869.236919]
• 21: Hans J. Stetter, Matrix eigenproblems are at the heart of polynomial system solving, ACM SIGSAM Bulletin, v.30 n.4, p.22-25, Dec. 1996 [doi>10.1145/242961.242966]
• 22: Hans J. Stetter, Numerical Polynomial Algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2004
• 23: B. Sturmfels, Solving Systems of polynomial Equations, Number 97 in CBMS Regional Conference Series in Mathematics, AMS, 2002.
• 24: G. H. Thallinger, Analysis of zero clusters in multivariate polynomial systems. Diploma Thesis, Tech. Univ. Vienna, 1996.
• 25: Zhonggang Zeng , Barry H. Dayton, The approximate GCD of inexact polynomials, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.320-327, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005331]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Systems of equations

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

General Terms:
Algorithms, Theory

Keywords:
dual space, multiplicity, polynomial ideal