Ontario Research Centre for Computer Algebra Technical Reports
The Ontario Research Centre for Computer Algebra

The UWO ORCCA Reading Room


UWO ORCCA TR-03-01 Summary

Improved algorithms for computing determinants and resultants, February 11, 2003, Ioannis Z. Emiris and Victor Y. Pan, 17 pages

Abstract: Our first contribution is a substantial acceleration of the randomized computation of scalar, univariate, and multivariate matrix determinants, in terms of the output-sensitive bit complexity bounds, including computation modulo a product of random primes from a fixed range. This acceleration is particularly dramatic in a critical application, namely solving polynomial systems and related studies, via computing a resultant. This is achieved by combining our techniques with the primitive-element method, which leads to an effective implicit representation of the roots. We systematically examine quotient formulae of Sylvester-typr resultant matrices, including matrix polynomials and the u-resultant. We reduce the known bit complexity bounds by almost an order of magnitude, in terms of the resultant matrix dimension. Our theoretical and practical improvements cover the highly important cases of sparse and degenerate systems.


If you have any questions or comments regarding this page please send mail to tech-reports@orcca.on.ca.


About ORCCA

Members

Events & Seminars

ORCCA Home
ORCCA Home

Research Activities

Positions

Reading Room

Contact Info