Fast Algorithms for Zero-Dimensional Polynomial Systems Using Duality
Résumé
Many questions concerning a zero-dimensional polynomial system can be reduced to linear algebra operations in the algebra $\Quo=k[\LVar]/\I$, where $\I$ is the ideal generated by the input system. Assuming that the multiplicative structure of the algebra is (partly) known, we address the question of speeding up the linear algebra phase for the computation of minimal polynomials and rational parametrizations. We present new algorithm- s extending ideas introduced by Shoup in the univariate case. Our approach is based on the $\Quo$-module structure of the dual space $\widehat\Quo$. An important feature of our algorithms is that we do not require $\widehat\Quo- $ to be free and of rank 1. The complexity of our algorithms for computing the minimal polynomial and for the rational parametrizations are $O(2^nD^5/2)$ and $O(n2^nD^5/2)$ respectively, where $D$ is the dimension of $A$. This is better than algorithms based on linear algebra except when the complexity of the available matrix product has exponent less than 5/2.