Numerical local rings and local solution of nonlinear systems

ABSTRACT

Adapting a 1915 method of Macaulay, one can give a calculation of the local ring of an isolated zero of a polynomial system {f₁, f₂, . . . , f_t} ⊆ C[x₁, x₂, . . . , x_s] using oating point arithmetic. Using an approximate reverse reduced row echelon form algorithm (ARRREF) one gets a Gröbner basis with respect to a global, rather than local, ordering which leads to the usual representation as a matrix algebra. This can be exploited by relaxing the tolerance in the ARRREF to get information on zeros in a small Euclidean neighborhood of the given zero. The technique, which may be useful in the endgame stage of the homotopy continuation method, is applied to analytic as well as polynomial systems.

REFERENCES

• 1: G. Birkhoff, S. Mac Lane, A survey of Modern Algebra, Macmillan, 1941.
• 2: D. Bates, J. Hauenstein, A. Sommesse and C. Wampler II, Bertini: Software for Numerical Algebraic Geometry, available at http://www.nd.edu/sommese/bertini.
• 3: D. Cox, J. Little, D. O'Shea, Using Algebraic Geometry. Springer Verlag, 1998.
• 4: Barry H. Dayton , Zhonggang Zeng, Computing the multiplicity structure in solving polynomial systems, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.116-123, July 24-27, 2005, Beijing, China [doi>10.1145/1073884.1073902]
• 5: A. Griewank and M.R. Osborne, Analysis of Newton's Method at irregular singularities. SIAM J. Numer. Anal. 20(4), pp. 747--773, 1983.
• 6: G.-M. Greuel and G. Pfister, A Singular Introduction to Commutative Algebra. Springer Verlag, 2002.
• 7: Itnuit Janovitz-Freireich , Lajos Rónyai , Ágnes Szántó, Approximate radical of ideals with clusters of roots, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy [doi>10.1145/1145768.1145796]
• 8: A. Leykin, J. Verschelde, and A. Zhao, Evaluation of Jacobian matrices for Newton's method with de ation to approximate isolated singular solutions of polynomial systems. In Symbolic-Numeric Computation, edited by D. Wang and L. Zhi, editors, pp. 269--278. Trends in Mathematics, Birkhäuser, 2007.
• 9: Anton Leykin , Jan Verschelde , Ailing Zhao, Newton's method with deflation for isolated singularities of polynomial systems, Theoretical Computer Science, v.359 n.1, p.111-122, 14 August 2006 [doi>10.1016/j.tcs.2006.02.018]
• 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: Maria Grazia Marinari , Teo Mora , Hans Michael Möller, Gröbner duality and multiplicities in polynomial system solving, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.167-179, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220368]
• 13: 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]
• 14: T. Mora, Solving Polynomial Equation Systems II. Encyclopedia of Mathematics and its Application, 99, Cambridge University Press, Cambridge, 2005.
• 15: B. Mourrain, Isolated points, duality and residues, J. of Pure and Applied Algebra, 1996, 117 & 118, pp. 469--493.
• 16: B. Mourrain, Computing the isolated roots by matrix methods, Journal of Symbolic Computation, v.26 n.6, p.715-738, Dec. 1998 [doi>10.1006/jsco.1998.0236]
• 17: R. Scott, Approximate Gröbner bases -- a backwards approach. Master of Science Thesis, Greg Reid supervisor, Graduate Program in Applied Mathematics, University of Western Ontario, London, Ontario, Canada, 2006.
• 18: A. J. Sommese and C. W. Wampler II The Numerical solution of Systems of Polynomials Arising in Engineering and Science. World Scientific Publishing Co., 2005.
• 19: Hans J. Stetter, Numerical Polynomial Algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2004
• 20: Jan Verschelde, Algorithm 795: PHCpack: a general-purpose solver for polynomial systems by homotopy continuation, ACM Transactions on Mathematical Software (TOMS), v.25 n.2, p.251-276, June 1999 [doi>10.1145/317275.317286]

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:
analytic system, local ring, polynomial system, reduced row echelon form