Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleOn the complexity of computing with zero-dimensional triangular sets
Author(s) Adrien Poteaux, Éric Schost
TypeArticle in Journal
AbstractWe 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.
KeywordsTriangular sets, Modular composition, Power projection, Change of order, Equiprojectable decomposition
URL http://www.sciencedirect.com/science/article/pii/S0747717112001083
JournalJournal of Symbolic Computation
Pages110 - 138
Translation No
Refereed No