Fast Computation of the Bezout and Dixon Resultant Matrices

✍ Scribed by Eng-Wee Chionh; Ming Zhang; Ronald N. Goldman

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 264 KB
• Volume: 33
• Category: Article
• ISSN: 0747-7171
• DOI: 10.1006/jsco.2001.0462

✦ Synopsis

Efficient algorithms are derived for computing the entries of the Bezout resultant matrix for two univariate polynomials of degree n and for calculating the entries of the Dixon-Cayley resultant matrix for three bivariate polynomials of bidegree (m, n). Standard methods based on explicit formulas require O(n 3 ) additions and multiplications to compute all the entries of the Bezout resultant matrix. Here we present a new recursive algorithm for computing these entries that uses only O(n 2 ) additions and multiplications. The improvement is even more dramatic in the bivariate setting. Established techniques based on explicit formulas require O(m 4 n 4 ) additions and multiplications to calculate all the entries of the Dixon-Cayley resultant matrix. In contrast, our recursive algorithm for computing these entries uses only O(m 2 n 3 ) additions and multiplications.