Details:
Title  Symbolic and numeric methods for exploiting structure in constructing resultant
matrices  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 zerodimensional systems of equations [Laz81, CKL89, Man94, Emi96, MP97]. Our practical motivation is the realtime 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 quasiquadratic time complexity. 
File 
 Language  English  Journal  Journal of Symbolic Computation  Series  Special Issue on SymbolicNumeric Algebra for Polynomials  Year  2001  Edition  0  Translation 
No  Refereed 
No 
