ORCCA Home |
|||
The Ontario Research Centre for Computer Algebra
The UWO ORCCA Reading Room |
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.
|
ORCCA Home |
|||