Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Accurate solution of polynomial equations using Macaulay resultant matrices

Authors: Guðbjörn F. Jónsson and Stephen A. Vavasis
Journal: Math. Comp. 74 (2005), 221-262
MSC (2000): Primary :, 13P10, 65F15.; Secondary :, 68W30
Published electronically: July 22, 2004
MathSciNet review: 2085409
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We propose an algorithm for solving two polynomial equations in two variables. Our algorithm is based on the Macaulay resultant approach combined with new techniques, including randomization, to make the algorithm accurate in the presence of roundoff error. The ultimate computation is the solution of a generalized eigenvalue problem via the QZ method. We analyze the error due to roundoff of the method, showing that with high probability the roots are computed accurately, assuming that the input data (that is, the two polynomials) are well conditioned. Our analysis requires a novel combination of algebraic and numerical techniques.

References [Enhancements On Off] (What's this?)

  • 1. W. Auzinger and H. J. Stetter, An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equation, Numerical mathematics, Singapore 1988, ISNM vol. 86, Birkhäuser, 1988, pp. 11-30. MR 91g:65112
  • 2. L. Busé, M. Elkadi, and B. Mourrain, Resultant over the residual of a complete intersection, Journal of Pure and Applied Algebra 164 (2001), 35-57. MR 2002h:13042
  • 3. Arthur Cayley, On the theory of elimination, Cambridge and Dublin Math. J. III (1848), 116-120, Can also be found as Appendix B of [10].
  • 4. M. Chardin, Multivariate subresultants, Journal of Pure and Applied Algebra 101 (1995), 129-138. MR 96j:12002
  • 5. Robert M. Corless, Patrizia M. Gianni, and Barry M. Trager, A reordered Schur factorization method for zero-dimensional polynomial systems with multiple roots, ISSAC '97. Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation (Wolfgang W. Küchlin, ed.), ACM Press, 1997, pp. 133-140.
  • 6. David Cox, John Little, and Donal O'Shea, Using algebraic geometry, Springer-Verlag, 1998. MR 99h:13033
  • 7. J. Dennis and R. Schnabel, Numerical methods for unconstrained optimization and nonlinear equations, SIAM, Philadelphia, 1996. MR 96i:90002
  • 8. Alan Edelman and H. Murakami, Polynomial roots from companion matrix eigenvalues, Math. Comp. 64 (1995), no. 210, 763-776. MR 95f:65075
  • 9. Ioannis Z. Emiris and Bernard Mourrain, Matrices in elimination theory, J. Symbolic Comput. 28 (1999), no. 1-2, 3-44. MR 2000h:68249
  • 10. I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinsky, Discriminants, resultants, and multidimensional determinants, Birkhäuser, 1994. MR 95e:14045
  • 11. Gene H. Golub and Charles F. Van Loan, Matrix computations, 3rd ed., John Hopkins University Press, 1996. MR 97g:65006
  • 12. I. S. Gradshteyn and I. M. Ryzhik, Table of integrals, series, and products, 5th ed., Academic Press, 1994. MR 97c:00014
  • 13. Ming Gu and Stanley C. Eisenstat, Efficient algorithms for computing a strong rank-revealing QR factorization, SIAM J. Sci. Comput. 17 (1996), no. 4, 848-869. MR 97h:65053
  • 14. Thomas Hawkins, Another look at Cayley and the theory of matrices, Arch. Internat. Historie Sci. 27 (1977), no. 100, 82-112. MR 58:10105
  • 15. G. Jónsson, Eigenvalue methods for accurate solution of polynomial equations, Ph.D. thesis, Center for Applied Mathematics, Cornell University, Ithaca, NY, 2001.
  • 16. G. F. Jónsson and S. A. Vavasis, Solving polynomials with small leading coefficients, to appear in SIAM J. Matrix Anal. Appl.
  • 17. T. Krick, L. Pardo, and M. Sombra, Sharp estimates for the arithmetic nullstellensatz, Duke Math. J. 109 (2001), 521-598. MR 2002h:11060
  • 18. T. Y. Li, Numerical solutions of multivariate polynomial systems by homotopy continuation methods, Acta Numerica 6 (1997), 399-436. MR 2000i:65084
  • 19. F. S. Macaulay, On some formulæin elimination, Proc. London Math. Soc. 35 (1902), 3-27.
  • 20. -, The algebraic theory of modular systems, Cambridge University Press, 1916.
  • 21. Dinesh Manocha and James Demmel, Algorithms for intersecting parametric and algebraic curves I: Simple intersections, ACM Trans. Graphics 13 (1994), no. 1, 73-100.
  • 22. Dinesh Manocha and Shankar Krishnan, Solving algebraic systems using matrix computations, SIGSAM Bulletin 30 (1996), no. 4, 4-21.
  • 23. Scott A. Mitchell and Stephen A. Vavasis, Quality mesh generation in higher dimensions, SIAM J. Computing 29 (2000), no. 4, 1334-1370. MR 2000m:65146
  • 24. Bernard Mourrain and Victor Y. Pan, Multivariate polynomials, duality, and structured matrices, J. Complexity 16 (2000), no. 1, 110-180. MR 2002c:15048
  • 25. J. Rosen, H. Park, and J. Glick, Total least norm formulation and solution for structured problems, SIAM J. Matrix Anal. App. 17 (1996), 110-126. MR 96m:65046
  • 26. M. Sombra, Private email communication, 2003.
  • 27. G. W. Stewart, Perturbation theory for the generalized eigenvalue problem, Recent Advances in Numerical Analysis (Carl de Boor and Gene H. Golub, eds.), Academic Press, 1978, pp. 193-206. MR 80c:65092
  • 28. Kim-Chuan Toh and Lloyd N. Trefethen, Pseudozeros of polynomials and pseudospectra of companion matrices, Numer. Math. 68 (1994), 403-425. MR 95m:65085
  • 29. B. L. van der Waerden, Modern algebra, vol. II, Frederick Ungar Publishing Co., 1950, English translation of Moderne Algebra, Springer-Verlag, Berlin, 1931.
  • 30. Paul Van Dooren and Patrick Dewilde, The eigenstructure of an arbitrary polynomial matrix: Computational aspects, Lin. Alg. Appl. 50 (1983), 545-579. MR 84j:15009
  • 31. Stephen A. Vavasis, QMG: Software for finite-element mesh generation, See, 1996.
  • 32. Layne T. Watson, Maria Sosonkina, Robert C. Melville, Alexander P. Morgan, and Homer F. Walker, Algorithm 777. HOMPACK90: A suite of Fortran 90 codes for globally convergent homotopy algorithms, ACM Trans. Math. Software 23 (1997), no. 4, 514-549.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): :, 13P10, 65F15., :, 68W30

Retrieve articles in all journals with MSC (2000): :, 13P10, 65F15., :, 68W30

Additional Information

Guðbjörn F. Jónsson
Affiliation: Center for Applied Mathematics, Rhodes Hall, Cornell University, Ithaca, New York 14853
Address at time of publication: deCODE Genetics, Lynghals 1, IS-110 Reykjavik, Iceland

Stephen A. Vavasis
Affiliation: Department of Computer Science, Upson Hall, Cornell University, Ithaca, New York 14853

Received by editor(s): March 7, 2001
Received by editor(s) in revised form: December 30, 2002
Published electronically: July 22, 2004
Additional Notes: This work was supported in part by NSF grants CCR-9619489 and EIA-9726388. Research also supported in part by NSF through grant DMS-9505155 and ONR through grant N00014-96-1-0050.
Article copyright: © Copyright 2004 American Mathematical Society