Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleSymbolic and numeric methods for exploiting structure in constructing resultant matrices
Author(s) Ioannis Z. Emiris, Victor Y. Pan
TypeArticle in Journal
AbstractThis paper identifies and exploits the structure of Newton matrices by designing an efficient numerical rank test and exact polynomial arithmetic in the context of sparse elimination. This yields better time and space complexity bounds for their construction, the computation of the sparse resultant and, ultimately, the solution of nonlinear polynomial systems. Our methods can be extended to the case of imperfectly known coefficients, or to solving overconstrained systems as long as the number of solutions is finite. Hence, our effort is a contribution in efficient and numerically stable algorithms in nonlinear algebra. Construction and manipulation of Newton matrices is a critical operation in some of the most efficient known algorithms for solving zero-dimensional systems of equations [Laz81, CKL89, Man94, Emi96, MP97]. Our practical motivation is the real-time solution of systems with, say, up to 10 variables; or the computation of the resultant polynomial, for instance, in graphics and modeling applications where the implicit expression of a curve or surface is precisely the resultant. Such systems may give rise to matrices with dimension in the hundreds or even higher, as illustrated by specific examples in table 2. By palliating the
eoeects of matrix size, with respect to both time and space complexity, our work deals with what is probably the Achille's heel of Newton's matrices. This general area is a field of active research. The solution of such equations is itself irrational, even in the univariate case. Hence it requires further numeric computation following the construction of a resultant matrix, as explained in section 6. The main contribution of the present paper is to construct Newton matrices with quasi-quadratic time complexity.
JournalJournal of Symbolic Computation
SeriesSpecial Issue on Symbolic-Numeric Algebra for Polynomials
Translation No
Refereed No