Mathematics of Computation

Author(s): Guðbjörn F. Jónsson; Stephen A. Vavasis.
Journal: Math. Comp. 74 (2005), 221-262.
MSC (2000): Primary 13P10, 65F15.; Secondary 68W30
Posted: July 22, 2004
Retrieve article in: PDF DVI PostScript

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.

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 http://www.cs.cornell.edu/home/vavasis/qmg-home.html, 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.

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

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
Email: gfj@decode.is

Stephen A. Vavasis
Affiliation: Department of Computer Science, Upson Hall, Cornell University, Ithaca, New York 14853
Email: vavasis@cs.cornell.edu

DOI: 10.1090/S0025-5718-04-01722-3
PII: S 0025-5718(04)01722-3
Received by editor(s): March 7, 2001
Received by editor(s) in revised form: December 30, 2002
Posted: 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.
Copyright of article: Copyright 2004, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS