Approximate radical of ideals with clusters of roots

ABSTRACT

We present a method based on Dickson's lemma to compute the "approximate radical" of a zero dimensional ideal I in C[x₁, . . . , x_m] which has zero clusters: the approximate radical ideal has exactly one root in each cluster for sufficiently small clusters. Our method is "global" in the sense that it does not require any local approximation of the zero clusters: it reduces the problem to the computation of the numerical nullspace of the so called "matrix of traces", a matrix computable from the generating polynomials of I. To compute the numerical nullspace of the matrix of traces we propose to use Gauss elimination with pivoting, and we prove that if I has k distinct zero clusters each of radius at most ε in the ∞-norm, then k steps of Gauss elimination on the matrix of traces yields a submatrix with all entries asymptotically equal to ε². We also prove that the computed approximate radical has one root in each cluster with coordinates which are the arithmetic mean of the cluster, up to an error term asymptotically equal to ε². In the univariate case our method gives an alternative to known approximate square-free factorization algorithms which is simpler and its accuracy is better understood.

REFERENCES

• 1: Z. Bai , J. Demmel , A. McKenney, On the Conditioning of the Nonsymmetric Eigenproblem: Theory and Software, University of Tennessee, Knoxville, TN, 1989
• 2: E. Briand and L. Gonzalez-Vega. Multivariate Newton sums: Identities and generating functions. Communications in Algebra, 30(9):4527--4547, 2001.
• 3: J. Cardinal and B. Mourrain. Algebraic approach of residues and applications. In J. Reneger, M. Shub, and S. Smale, editors, Proceedings of AMS-Siam Summer Seminar on Math. of Numerical Analysis (Park City, Utah, 1995), volume 32 of Lectures in Applied Mathematics, pages 189--219, 1996.
• 4: E. Cattani , A. Dickenstein , B. Sturmfels, Computing multidimensional residues, Algorithms in algebraic geometry and applications, Birkhauser Verlag, Basel, Switzerland, 1996
• 5: E. Cattani, A. Dickenstein, and B. Sturmfels. Residues and resultants. J. Math. Sci. Univ. Tokyo, 5(1):119--148, 1998.
• 6: M. Chardin. Multivariate subresultants. Journal of Pure and Applied Algebra, 101:129--138, 1995.
• 7: Robert M. Corless, Gro¨bner bases and matrix eigenproblems, ACM SIGSAM Bulletin, v.30 n.4, p.26-32, Dec. 1996 [doi>10.1145/242961.242968]
• 8: 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]
• 9: Robert M. Corless , Patrizia M. Gianni , Barry M. Trager , Stephen M. Watt, The singular value decomposition for polynomial systems, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.195-207, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220371]
• 10: 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]
• 11: James Demmel, Accurate Singular Value Decompositions of Structured Matrices, SIAM Journal on Matrix Analysis and Applications, v.21 n.2, p.562-580, Oct.-Jan. 2000 [doi>10.1137/S0895479897328716]
• 12: J. Demmel and P. Koev. Accurate SVD's of polynomial vandermonde matrices involving orthonormal polynomials. Linear Algebra Applications, to appear, 2005.
• 13: G. M. Díaz-Toca and L. González-Vega. An explicit description for the triangular decomposition of a zero-dimensional ideal through trace computations. In Symbolic computation: solving equations in algebra, geometry, and engineering (South Hadley, MA, 2000), volume 286 of Contemp. Math., pages 21--35. AMS, 2001.
• 14: L. Dickson. Algebras and Their Arithmetics. University of Chicago Press, 1923.
• 15: K Friedl , L Rónyai, Polynomial time solutions of some problems of computational algebra, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.153-162, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22162]
• 16: G. H. Golub and C. F. Van Loan. Matrix computations. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, third edition, 1996.
• 17: V. Hribernig , H. J. Stetter, Detection and validation of clusters of polynomial zeros, Journal of Symbolic Computation, v.24 n.6, p.667-681, Dec. 1997 [doi>10.1006/jsco.1997.0160]
• 18: W. Kahan. Numerical linear algebra. Canadian Mathematical Bulletin, (9):757--801, 1966.
• 19: Erich Kaltofen, On computing determinants of matrices without divisions, Papers from the international symposium on Symbolic and algebraic computation, p.342-349, July 27-29, 1992, Berkeley, California, United States [doi>10.1145/143242.143350]
• 20: Erich Kaltofen , John May, On approximate irreducibility of polynomials in several variables, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.161-168, August 03-06, 2003, Philadelphia, PA, USA [doi>10.1145/860854.860893]
• 21: Nonlinear Polynomial Systems: Multiple Roots and Their Multiplicities, Proceedings of the Shape Modeling International 2004 (SMI'04), p.87-98, June 07-09, 2004 [doi>10.1109/SMI.2004.45]
• 22: D. Lazard. Resolution des systemes d'equations algebriques. Theoret. Comp. Sci., 15(1), 1981. French, English summary.
• 23: G. Lecerf. Quadratic Newton iterarion for systems with multiplicity. Foundations of Computational Mathematics, (2):247--293, 2002.
• 24: A. Leykin, J. Verschelde, and A. Zhao. Evaluation of Jacobian matrices for Newton's method with deflation to approximate isolated singular solutions of polynomial systems. In D. Wang and L. Zhi, editors, SNC 2005 Proceedings. International Workshop on Symbolic-Numeric Computation., pages 19--28, 2005.
• 25: 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]
• 26: 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]
• 27: 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]
• 28: A. P. Morgan, A. J. Sommese, and C. W. Wampler. Computing singular solutions to nonlinear analytic systems. Numer. Math., 58(7):669--684, 1991.
• 29: Alexander P. Morgan , Andrew J. Sommese , Charles W. Wampler, Computing singular solutions to polynomial systems, Advances in Applied Mathematics, v.13 n.3, p.305-327, Sept. 1992 [doi>10.1016/0196-8858(92)90014-N]
• 30: A. P. Morgan, A. J. Sommese, and C. W. Wampler. A power series method for computing singular solutions to nonlinear analytic systems. Numer. Math., 63(3):391--409, 1992.
• 31: S. Moritsugu and K. Kuriyama. A linear algebra method for solving systems of algebraic equations. In RISC-Linz Report Series, volume 35, 1997.
• 32: 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]
• 33: Bernard Mourrain, Generalized normal forms and polynomial system solving, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.253-260, July 24-27, 2005, Beijing, China [doi>10.1145/1073884.1073920]
• 34: T. Ojika. Modified deflation algorithm for the solution of singular problems. I. A system of nonlinear algebraic equations. J. Math. Anal. Appl., 123(1):199--221, 1987.
• 35: T. Ojika. Modified deflation algorithm for the solution of singular problems. II. Nonlinear multipoint boundary value problems. J. Math. Anal. Appl., 123(1):222--237, 1987.
• 36: T. Ojika, S. Watanabe, and T. Mitsui. Deflation algorithm for the multiple roots of a system of nonlinear equations. J. Math. Anal. Appl., 96(2):463--479, 1983.
• 37: R. S. Pierce. Associative algebras, volume 88 of Graduate Text in Mathematics. Springer-Verlag, 1982.
• 38: T. Sasaki , M. Noda, Approximate square-free decomposition and root-finding of lll-conditioned algebraic equations, Journal of Information Processing, v.12 n.2, p.159-168, Jan. 1989
• 39: E. Schost. Personal communication, 2005.
• 40: Victor Shoup, Efficient computation of minimal polynomials in algebraic extensions of finite fields, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.53-58, July 28-31, 1999, Vancouver, British Columbia, Canada [doi>10.1145/309831.309859]
• 41: 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]
• 42: Hans J. Stetter, Numerical Polynomial Algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2004
• 43: A. Szanto. Solving over-determined systems by subresultant methods. Preprint, 2001.
• 44: Kazuhiro Yokoyama , Masayuki Noro , Taku Takeshima, Solutions of systems of algebraic equations and linear maps on residue class rings, Journal of Symbolic Computation, v.14 n.4, p.399-417, Oct. 1992 [doi>10.1016/0747-7171(92)90014-U]
• 45: Zhonggang Zeng, A method computing multiple roots of inexact polynomials, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.266-272, August 03-06, 2003, Philadelphia, PA, USA [doi>10.1145/860854.860907]

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Polynomials, methods for; Systems of equations

General Terms:
Algorithms, Theory