Details:
Title  On the complexity of computing with zerodimensional triangular sets  Author(s)  Adrien Poteaux, Éric Schost  Type  Article in Journal  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 quasiinverse 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 quasilinear 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.  Keywords  Triangular sets, Modular composition, Power projection, Change of order, Equiprojectable decomposition  ISSN  07477171 
URL 
http://www.sciencedirect.com/science/article/pii/S0747717112001083 
Language  English  Journal  Journal of Symbolic Computation  Volume  50  Number  0  Pages  110  138  Year  2013  Edition  0  Translation 
No  Refereed 
No 
