On the complexity of computing with zero-dimensional triangular sets

Details On the complexity of computing with zero-dimensional triangular sets On the complexity of computing with zero-dimensional triangular sets

2011-09-20

arxiv.org/abs/1109.4323v1

Computer Science

Symbolic Computation

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On the complexity of computing with zero-dimensional triangular sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the complexity of computing with zero-dimensional triangular sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the complexity of computing with zero-dimensional triangular sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-147550