Fast Computation of Resultant Matrices

 

ABSTRACT: "The resultant is a useful mathematical tool for determining
the intersections of polynomial curves by reducing the curves into a
formula with roots at these intersections.  In particular, they are
useful for eliminating variables in systems of equations.  However,
the resultant is classically calculated using the determinant - a
computationally expensive operation. The goal of this presentation is
to explore various techniques for simplifying the computation of two
types of resultants: one for the case of two uni-variate polynomials,
the other for three bi-variate polynomials.  Specifically, this
presentation seeks to explore how the computations can be optimized
to reduce the number of operations in the the uni-variate
case from
O(n^3) to O(n^2) and the bi-variate case from O(m^4 n^4) to O(m^2
n^3), along with even further possible refinements."

 
                                          Related paper: fast-computation.pdf