Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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 :
Reports (Research report)
Complete list of metadata
Contributor : Rapport De Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 8:20:00 PM
Last modification on : Wednesday, October 26, 2022 - 8:16:46 AM
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⟩



Record views


Files downloads