|Title||Symbolic and numeric methods for exploiting structure in constructing resultant
|Author(s)|| Ioannis Z. Emiris, Victor Y. Pan|
|Type||Article in Journal|
|Abstract||This 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.
|Journal||Journal of Symbolic Computation|
|Series||Special Issue on Symbolic-Numeric Algebra for Polynomials|