On the complexity of computing with zero-dimensional triangular sets
From MaRDI portal
Abstract: We study the complexity of some fundamental operations for triangular sets in dimension zero. Using Las-Vegas algorithms, we prove that one can perform such operations as change of order, equiprojectable decomposition, or quasi-inverse computation with a cost that is essentially that of modular composition. Over an abstract field, this leads to a subquadratic cost (with respect to the degree of the underlying algebraic set). Over a finite field, in a boolean RAM model, we obtain a quasi-linear running time using Kedlaya and Umans' algorithm for modular composition. Conversely, we also show how to reduce the problem of modular composition to change of order for triangular sets, so that all these problems are essentially equivalent. Our algorithms are implemented in Maple; we present some experimental results.
Recommendations
- Complexity results for triangular sets
- Complexity of triangular representations of algebraic sets
- On the Bit-Size of Non-radical Triangular Sets
- Computing with semi-algebraic sets represented by triangular decomposition
- On the computational complexity of defining sets
- Complexity of finite sequences of zeros and ones and geometry of finite spaces of functions
- scientific article; zbMATH DE number 3880013
- On approximate triangular decompositions in dimension zero
- Bit-size estimates for triangular sets in positive dimension
- On the computational complexity of Erdős-Szekeres and related problems in \(\mathbb{R}^{3}\)
Cited in
(25)- Fast arithmetic for triangular sets: from theory to practice
- Complexity results for triangular sets
- Computing Puiseux series: a fast divide and conquer algorithm
- Computing critical points for invariant algebraic systems
- Real root finding for low rank linear matrices
- Directed evaluation
- Computing real radicals and S-radicals of polynomial systems
- Block-Krylov techniques in the context of sparse-FGLM algorithms
- Accelerated tower arithmetic
- Linear algebra for computing Gröbner bases of linear recursive multidimensional sequences
- On the complexity exponent of polynomial system solving
- A softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integers
- Change of order for bivariate triangular sets
- On the complexity of the D5 principle
- Modular composition modulo triangular sets and applications
- On the Bit-Size of Non-radical Triangular Sets
- Sharp estimates for triangular sets
- Decomposition of polynomial sets into characteristic pairs
- Fast arithmetic for triangular sets: from theory to practice
- Computing GCDs of Multivariate Polynomials over Algebraic Number Fields Presented with Multiple Extensions
- Homotopy techniques for multiplication modulo triangular sets
- Choosing variable orderings based on elimination tree for sparse triangular decomposition
- Faster modular composition
- Complexity analysis of triangular decomposition over F₂ with strongly chordal graphs
- Strongly and transitive chordal graphs and their applications in complexity analysis of triangular decomposition
This page was built for publication: On the complexity of computing with zero-dimensional triangular sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1930161)
