Skip to Main content Skip to Navigation

Complexity of polynomial systems representations: triangulation, modular methods, dynamic evaluation.

Abstract : The polynomial systems in their triangular shape, notably the regular chains and especially the Lazard triangular sets, are simple data structures, permitting to consider modular computations (by specialization of the coefficients, then lifting through the Newton-Hensel operator), to "solve'' the polynomial systems ("decomposition-triangulations'' methods) and to represent tours of fields extensions to compute with algebraic numbers. For those three topics, the methods and results provided here, notably on the complexity front, extend the fields of applications of triangular sets, and their impact compared to other methods of manipulation of algebraic equations, especially the Gröbner bases. First of all the space complexity of the coefficients is only on quadratic growth in function of natural geometric data. Straightforward corollary is a (triangular) Newton operator requiring less lifting steps, hence more promising modular methods. So it is for the equiprojectable decomposition}, first polynomial systems triangulation algorithm based on a modular method, and for the problem of the change of monomials orderings in positive dimension, yet in some quite specific cases for a first approach. In addition, computing modulo a triangular set by following the dynamic evaluation model, is now endowed, 20 years after its apparition, of a first satisfaying complexity study.
Document type :
Complete list of metadatas

Cited literature [114 references]  Display  Hide  Download
Contributor : Ecole Polytechnique <>
Submitted on : Thursday, July 22, 2010 - 11:27:07 AM
Last modification on : Wednesday, March 27, 2019 - 4:41:26 PM
Long-term archiving on: : Monday, October 25, 2010 - 11:06:22 AM


  • HAL Id : pastel-00003835, version 1



Xavier Dahan. Complexity of polynomial systems representations: triangulation, modular methods, dynamic evaluation.. Computer Science [cs]. Ecole Polytechnique X, 2006. English. ⟨pastel-00003835⟩



Record views


Files downloads