Skip to Main content Skip to Navigation

Fast Algorithms for Zero-Dimensional Polynomial Systems Using Duality

Alin Bostan 1 Bruno Salvy 1 Éric Schost
1 ALGO - Algorithms
Inria Paris-Rocquencourt
Abstract : 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.
Document type :
Complete list of metadatas
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 8:20:00 PM
Last modification on : Friday, May 25, 2018 - 12:02:02 PM
Long-term archiving on: : Tuesday, February 22, 2011 - 12:03:50 PM


  • HAL Id : inria-00072296, version 1



Alin Bostan, Bruno Salvy, Éric Schost. Fast Algorithms for Zero-Dimensional Polynomial Systems Using Duality. [Research Report] RR-4291, INRIA. 2001. ⟨inria-00072296⟩