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
(21)- A softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integers
- Linear algebra for computing Gröbner bases of linear recursive multidimensional sequences
- Computing critical points for invariant algebraic systems
- Computing GCDs of Multivariate Polynomials over Algebraic Number Fields Presented with Multiple Extensions
- Real root finding for low rank linear matrices
- Computing Puiseux series: a fast divide and conquer algorithm
- Accelerated tower arithmetic
- Complexity results for triangular sets
- On the Bit-Size of Non-radical Triangular Sets
- Homotopy techniques for multiplication modulo triangular sets
- On the complexity of the D5 principle
- Fast arithmetic for triangular sets: from theory to practice
- Sharp estimates for triangular sets
- Decomposition of polynomial sets into characteristic pairs
- Modular composition modulo triangular sets and applications
- Directed evaluation
- Change of order for bivariate triangular sets
- On the complexity exponent of polynomial system solving
- Fast arithmetic for triangular sets: from theory to practice
- Computing real radicals and \(S\)-radicals of polynomial systems
- Block-Krylov techniques in the context of sparse-FGLM algorithms
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)
