Accurate solution of polynomial equations using Macaulay resultant matrices

Jónsson, Guðbjörn; Vavasis, Stephen

doi:10.1090/S0025-5718-04-01722-3

Accurate solution of polynomial equations using Macaulay resultant matrices
HTML articles powered by AMS MathViewer

by Guðbjörn F. Jónsson and Stephen A. Vavasis PDF

Math. Comp. 74 (2005), 221-262 Request permission

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

W. Auzinger and H. J. Stetter, An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equations, Numerical mathematics, Singapore 1988, Internat. Schriftenreihe Numer. Math., vol. 86, Birkhäuser, Basel, 1988, pp. 11–30. MR 1022943
L. Busé, M. Elkadi, and B. Mourrain, Resultant over the residual of a complete intersection, J. Pure Appl. Algebra 164 (2001), no. 1-2, 35–57. Effective methods in algebraic geometry (Bath, 2000). MR 1854329, DOI 10.1016/S0022-4049(00)00144-4
Arthur Cayley, On the theory of elimination, Cambridge and Dublin Math. J. III (1848), 116–120, Can also be found as Appendix B of [I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinsky, Discriminants, resultants, and multidimensional determinants, Birkhäuser, 1994].
Marc Chardin, Multivariate subresultants, J. Pure Appl. Algebra 101 (1995), no. 2, 129–138. MR 1348031, DOI 10.1016/0022-4049(95)90926-C
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.
David Cox, John Little, and Donal O’Shea, Using algebraic geometry, Graduate Texts in Mathematics, vol. 185, Springer-Verlag, New York, 1998. MR 1639811, DOI 10.1007/978-1-4757-6911-1
J. E. Dennis Jr. and Robert B. Schnabel, Numerical methods for unconstrained optimization and nonlinear equations, Classics in Applied Mathematics, vol. 16, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996. Corrected reprint of the 1983 original. MR 1376139, DOI 10.1137/1.9781611971200
Alan Edelman and H. Murakami, Polynomial roots from companion matrix eigenvalues, Math. Comp. 64 (1995), no. 210, 763–776. MR 1262279, DOI 10.1090/S0025-5718-1995-1262279-2
Ioannis Z. Emiris and Bernard Mourrain, Matrices in elimination theory, J. Symbolic Comput. 28 (1999), no. 1-2, 3–44. Polynomial elimination—algorithms and applications. MR 1709416, DOI 10.1006/jsco.1998.0266
I. M. Gel′fand, M. M. Kapranov, and A. V. Zelevinsky, Discriminants, resultants, and multidimensional determinants, Mathematics: Theory & Applications, Birkhäuser Boston, Inc., Boston, MA, 1994. MR 1264417, DOI 10.1007/978-0-8176-4771-1
Gene H. Golub and Charles F. Van Loan, Matrix computations, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR 1417720
I. S. Gradshteyn and I. M. Ryzhik, Table of integrals, series, and products, 5th ed., Academic Press, Inc., San Diego, CA, 1996. CD-ROM version 1.0 for PC, MAC, and UNIX computers. MR 1398882
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 1395351, DOI 10.1137/0917055
Thomas Hawkins, Another look at Cayley and the theory of matrices, Arch. Internat. Hist. Sci. 27 (1977), no. 100, 82–112. MR 490789
G. Jónsson, Eigenvalue methods for accurate solution of polynomial equations, Ph.D. thesis, Center for Applied Mathematics, Cornell University, Ithaca, NY, 2001.
G. F. Jónsson and S. A. Vavasis, Solving polynomials with small leading coefficients, to appear in SIAM J. Matrix Anal. Appl.
Teresa Krick, Luis Miguel Pardo, and Martín Sombra, Sharp estimates for the arithmetic Nullstellensatz, Duke Math. J. 109 (2001), no. 3, 521–598. MR 1853355, DOI 10.1215/S0012-7094-01-10934-4
T. Y. Li, Numerical solution of multivariate polynomial systems by homotopy continuation methods, Acta numerica, 1997, Acta Numer., vol. 6, Cambridge Univ. Press, Cambridge, 1997, pp. 399–436. MR 1489259, DOI 10.1017/S0962492900002749
F. S. Macaulay, On some formulæ in elimination, Proc. London Math. Soc. 35 (1902), 3–27.
—, The algebraic theory of modular systems, Cambridge University Press, 1916.
Dinesh Manocha and James Demmel, Algorithms for intersecting parametric and algebraic curves I: Simple intersections, ACM Trans. Graphics 13 (1994), no. 1, 73–100.
Dinesh Manocha and Shankar Krishnan, Solving algebraic systems using matrix computations, SIGSAM Bulletin 30 (1996), no. 4, 4–21.
Scott A. Mitchell and Stephen A. Vavasis, Quality mesh generation in higher dimensions, SIAM J. Comput. 29 (2000), no. 4, 1334–1370. MR 1745138, DOI 10.1137/S0097539796314124
Bernard Mourrain and Victor Y. Pan, Multivariate polynomials, duality, and structured matrices, J. Complexity 16 (2000), no. 1, 110–180. Real computation and complexity (Schloss Dagstuhl, 1998). MR 1762401, DOI 10.1006/jcom.1999.0530
J. Ben Rosen, Haesun Park, and John Glick, Total least norm formulation and solution for structured problems, SIAM J. Matrix Anal. Appl. 17 (1996), no. 1, 110–126. MR 1372925, DOI 10.1137/S0895479893258802
M. Sombra, Private email communication, 2003.
G. W. Stewart, Perturbation theory for the generalized eigenvalue problem, Recent advances in numerical analysis (Proc. Sympos., Math. Res. Center, Univ. Wisconsin, Madison, Wis., 1978) Publ. Math. Res. Center Univ. Wisconsin, vol. 41, Academic Press, New York-London, 1978, pp. 193–206. MR 519063
Kim-Chuan Toh and Lloyd N. Trefethen, Pseudozeros of polynomials and pseudospectra of companion matrices, Numer. Math. 68 (1994), no. 3, 403–425. MR 1313152, DOI 10.1007/s002110050069
B. L. van der Waerden, Modern algebra, vol. II, Frederick Ungar Publishing Co., 1950, English translation of Moderne Algebra, Springer-Verlag, Berlin, 1931.
Paul Van Dooren and Patrick Dewilde, The eigenstructure of an arbitrary polynomial matrix: computational aspects, Linear Algebra Appl. 50 (1983), 545–579. MR 699575, DOI 10.1016/0024-3795(83)90069-1
Stephen A. Vavasis, QMG: Software for finite-element mesh generation, See http://www.cs.cornell.edu/home/vavasis/qmg-home.html, 1996.
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.