2011/09/20 by Adrien Poteaux, Poteaux, Adrien, Éric Schost +1 · 1 citation
Computer Science · Mathematics · #Commutative Algebra and Its Applications #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #Polynomial and algebraic computation #Symbolic Computation (cs.SC) #cs.SC
paper · pdf · doi:10.48550/arxiv.1109.4323
arxiv created 2011/09/20 · openalex publication_date 2011/09/20 · arxiv updated 2011/09/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.