Project topics and materials
Get Complete Project Material File(s) Now! »
Polynomial systems representations
This section presents two representations of polynomial systems which are of practical interest. The primitive element and triangular representations of a polynomial system. The first one has a good behavior under numerical approximations. In real geometry it allows to reduce problems to the univariate situation, where powerful methods of isolation of real roots exist. It is a central object in this topic, and we refer to the book [12] for the details. More precisions are given in § 1.1.2.
The second one, triangular systems, is used in manipulation of algebraic numbers, Galois theory [2, 4, 97], differential algebra [59], dynamic evaluation [35] and in the CAD algorithm of real geometry (Cf. [12] and the references therein), where the management of the lifting step is handled by triangular systems [98]. In § 1.1.3 more details are added.
Primitive element representation
This kind of representation is commonly attributed to Kronecker, Macaulay in [82] calls Kronecker substitution, the specialization by a separating linear form as done in Lemma 1.2. The Shape Lemma representation (1.3) was first considered in computer algebra, actually coming from numerical analysis work of Auzinger-Stetter [10]. Then after the remark on the size of coefficients made in Alonso-Becker-Roy-W¨ormann [3], the alternative equivalent representation of Definition 1.2 is nowadays preferred. Main algorithms to compute it are implemented by Rouillier [101] (the RUR, following the ideas presented in [3]), relying on a Gr¨obner basis pre-computation, and to Lecerf [76]. This last implementation follows the Geometric Resolution algorithm resulting on a long and exacting task initiated by Giusti and Heintz [48] in the aim to have a subexponential solver of polynomial systems. With their collaborators Krick, Morgenstern, Monta˜na, Morais and Pardo, they carry on in the 90’s this work in the series of articles [50, 51, 49]. In [52], Giusti, Lecerf and Salvy removed some constraining assumptions of regularity. For more details we refer to the thesis of Schost [102], Ch.1 §1.1, and Lecerf [75] Ch.1 §I.5. Both algorithm can take into account multiplicity numbers. The algorithm [76] treats the positive dimension in the equidimensional situation. The Rouillier’s approach is improved by Noro-Yokoyama in [92] by using the Chinese Remaindering Theorem. The algorithm of Lecerf relies him on lifting techniques with the use of a formal Newton-Hensel operator.
Basic algorithmic
This section is devoted to some well-known definitions and statements concerning basic algorithmic that is of use all along this work. A good reference is the book of Gathen- Gerhard [117]. The first subsection “Generalities” defines some notions of elementary algorithmic such that super-additive functions, and the subproduct tree, useful for stating the results in Chapter “On the complexity of D5 principle”. The second subsection recalls the complexity of basic operations, multiplication, division, extended GCD, simultaneous remainders, multivariate multiplication.
Lifting techniques
This section provides all the material required for using the Newton-Hensel operator: construction of the triangular operator, rational reconstruction, and the stop criterion. These three steps are sometimes known as the specialize and lift paradigm, and are enclosed in the generic term of lifting techniques.
The Newton operator is used in this thesis in its triangular form: We only give here the main lines of its description, in the next subsection and refer to the thesis of Schost [102, Chapitre 6 and Annexe C]. Subsection 1.4.2 tackles the “Rational reconstruction” problem. More details on the multivariate rational reconstruction are given in Paragraph 4.3 of [103], which strongly inspired these lines. The presentation of Lecerf in his thesis [75, § II.4] is also of interest. Both of these works are in the continuity of the articles of Giusti, Heintz, Pardo et al. [49, 50] and also in [56]. Inside their work, appears an use of the Newton operator with complexity considerations. The complexities of the algorithms for changing of order (Chapter 3) and for the equiprojectable decomposition (Chapter 4) both rely on a study in the same vein of the Newton operator.
Table of contents :
Introduction
1 Preliminaries
1.1 Polynomial systems representations
1.1.1 Hypotheses – Presentation
1.1.2 Primitive element representation
1.1.3 Triangular systems
1.2 Chow form and height
1.2.1 Chow form
1.2.2 Height theory
1.3 Basic algorithmic
1.3.1 Generalities
1.3.2 Basic operations
1.4 Lifting techniques
1.4.1 Triangular Newton-Hensel operator
1.4.2 Rational reconstruction
1.4.3 Probabilistic aspects
2 Height bounds for polynomial representations
2.1 Bounds from derivation of the Chow form
2.1.1 Formulas of derivations
2.1.2 Bounds for primitive element representations
2.1.3 A link between Chow forms and triangular polynomials
2.1.4 Height of coefficients
2.1.5 Attempt of bounds for (Ti)i from (Mi)i
2.2 Bounds from interpolation formulas
2.2.1 Interpolation formulas
2.2.2 Links with Chow forms
2.2.3 From interpolation to height bounds
3 Change of order for regular chains
3.1 Introduction
3.2 Preliminaries
3.2.1 Additional results on regular chains
3.2.2 Algorithmic prerequisites
3.3 Matroids
3.3.1 Definition and examples
3.3.2 A greedy optimization algorithm
3.4 Computing the exchange data
3.4.1 Characterization of the target set of algebraic variables
3.4.2 Linearization
3.4.3 Computing the initial specialization
3.4.4 Computing the exchange data
3.5 Changing the lifting fiber
3.5.1 Setup and preliminaries
3.5.2 Finding the new lifting fiber
3.5.3 Proof of Proposition 3.14
3.6 Proof of Theorem 3.1
3.7 Conclusions and future work
4 Lifting techniques for triangular decompositions
4.1 Introduction
4.2 Split-and-Merge algorithm
4.3 proof of Theorem 4.1
4.4 Proof of Theorem 4.2
4.5 Experimentation
4.6 Conclusions
5 On the complexity of the D5 principle
5.1 Introduction
5.2 Basic complexity results: multiplication and splitting
5.3 Fast GCD computations modulo a triangular set
5.4 Fast computation of quasi-inverses
5.5 Coprime factorization
5.5.1 Computing multiple gcd’s
5.5.2 Computing all pairs of gcd’s
5.5.3 A special case of coprime factorization
5.5.4 Conclusion: Proof of the main result
5.6 Removing critical pairs
5.7 Concluding the proof
Appendix: merging triangular sets for inversion
Conclusion
