This document has been generated automatically using Hevea software. To wiew its contents correctly you may need to configure your browser (see Hevea Home page for more informations).

Alternatively, you can download the pdf or the ps files.

On the Rational Univariate Representation

Fabrice Rouillier

SALSA (INRIA) project and CALFOR (LIP6) TEAM
8, rue du Capitaine Scott F-75015 Paris - France

Abstract

We propose new algorithms for computing Rational Univariate Representations of the roots of zero-dimensional systems, without any assumption on the associated ideal. The proposed methods can be viewed as a variants of the probabilistic algorithm proposed by A. Bostan, B. Salvy and E. Schost based on baby-step/giant step techniques. Our main contributions are deterministic versions which do not sacrifice the complexity bounds. They have been obtained by mixing baby-step giant-step strategies and some operation from the original RUR algorithm designed by the author. We also illustrate the capabilities of such roots representations by extending their use for computing the values of polynomials at the roots of a zero-dimensional system. For example, we show that we can improve the complexity bounds for computing all the sign conditions realized by a set of polynomials at the roots of a zero-dimensional system.

The Rational Univariate Representation [8] is, from the end-user point of view, a simple way for representing symbolically the roots of a zero-dimensional system without loosing information (multiplicities or real roots). Given a zero-dimensional system I = < p₁, ..., p_s > where the p_i Î Q [ X₁, ..., X_n ], a Rational Univariate Representation of V ( I ) has the following shape : f_t ( T ) = 0, X₁ = g_{t, 1} ( T )/g_t ( T ), ..., X_n = g_{t, n} ( T )/g_t ( T ), where f_t, g_t, g_{t, 1}, ..., g_{t, n} Î Q [ T ] (T is a new variable). It is uniquely defined w.r.t. a given polynomial t which separates V ( I ) (injective on V ( I )), the polynomial f_t being necessarily the characteristic polynomial of the image of t in Q [ X₁, ..., X_n ] / I(see [8]). The RUR defines a bijection between the zeroes of I and those of f_t preserving the multiplicities and the real roots.

For computing a RUR one have to solve two problems :

finding a separating polynomial
given any polynomial t, compute a RUR-Candidate f_t, g_t, g_{t, 1}, ..., g_{t, s} such that if t is a separating polynomial, then the RUR-Candidate is a RUR.

There exists many solutions for computing RUR-Candidates. For example, from a Lexicographic Gröbner basis, one can easily compute a RUR-Candidate, taking for t the smallest variable. Most of the proposed solutions do not guarantee that the RUR-Candidate is a RUR except by checking that f_t is square-free (sufficient condition for a RUR-Candidate to be a RUR).

Almost all linear forms separate V ( I ) so that a RUR-Candidate computed w.r.t. a randomly chosen linear form, is a RUR with a probability 1. But such a probabilistic output is not acceptable for many situations, especially for decision algorithms such as in [1]. Moreover, the complexity bounds of deterministic algorithm using a RUR as a black box must take into account the computation of a separating element.

There are two classes of algorithms for computing a RUR-Candidate : those which suppose that the ideal is radical, and the general ones. In the first case, computing a RUR mainly remains to computing a lexicographic Gröbner basis, and we can easily verify that the RUR-Candidate is a RUR by checking that f_t is square-free. Since at least one among the linear forms X₁ + iX₂ + ... + i^{n - 1} X_n, i = 1 ... nd ( d - 1 ) / 2, d = # V ( I ) separates V ( I ), it is then easy to provide a deterministic algorithm for computing a RUR when I is radical. For algorithm using a Gröbner basis or [10] to represent Q [ X₁, ..., X_n
] ] / I, the main part of the computation is devoted to solving a linear system, which can be done using using Bareiss method, multi-modular or p-adic techniques such as in [5], [4] or [7]. Note that in the particular case of radical ideals, the RUR coincides also with the geometrical resolution proposed in [6].

For the general case, up to our knowledge, only one method [8] computes a RUR (computes a RUR-Candidate and check the it is a RUR), but a recent algorithm [2] may be used to solve partially the problem : it computes an object closed to a RUR-Candidate (multiplicities may be lost) with respect to a linear form t (but do not check that t is separating V ( I )).

Both methods ([2] and [8]) take as input a multiplication table of Q [ X₁, ..., X_n ] / I (the reduced forms of all products of two elements of a monomial basis of Q [ X₁, ..., X_n ] / I). Let's denote by D the dimension of Q [ X₁, ..., X_n ] / I, B = { w₁, ..., w_D } a monomial basis of Q [ X₁, ..., X_n ] / I and T the multiplication table of Q [ X₁, ..., X_n ] / I. Algorithm from [2] provides a RUR-Candidate with a computing time complexity in O ( n 2ⁿ D^{5 / 2} ), while the one from [8] computes a RUR (guarantees that the associated polynomial separates V ( I )) with a computing time complexity for the computation of a RUR-Candidate in O ( D³ + nD² ), counting O ( 1 ) for basic arithmetic operations in Q in both cases. One can use as complexity parameter the number of elements of T denoted by # T in this text. The complexity bound of algorithm from [2] then becomes O ( n. # T D^{3 / 2} ) and depends strongly on the shape of Q [ X₁, ..., X_n ] / I.

If we assume that a reasonable entry is a suitable description of the quotient Q [ X₁, ..., X_n ] / I : a monomial basis and a normal form (see [10] for an alternative to Gröbner bases), those two complexity bounds have first to be compared to cost of the computation of the multiplication table which is O ( # T D² ), counting O ( 1 ) for basic arithmetic operations in Q. If we take into account the cost of the basic operations (at least proportional to the binary size of the scalars), the computation time of the multiplication table is (not easy to compare upper bounds ...) dominated by the computation time of the RUR-Candidate, at least for a large class of examples.

Our first result is an algorithm that computes a RUR-Candidate, performing O ( # T D^{3 / 2} + nD² ) operations in Q, taking as input a multiplication table of Q [ X₁, ..., X_n ] / I which is slightly better than [2]. The proposed algorithm is mainly the same as in [2] (based on the Baby-Step/Giant-Step algorithm [9]) but computes differently the so called ''transposed product'' (main operation). In addition, the output preserves the multiplicities. Basically, [2] generalizes the formulas from [8] : the coefficients of the RUR-Candidate can directly be expressed w.r.t l ( X_j tⁱ ) where l is a "sufficiently generic" linear form. Taking for l the Trace map (trace of the multiplication in Q [ X₁, ..., X_n ] / I), one recover the formulas from [8]. In both cases, one can decompose the computation into 4 steps :

A compute a sufficient number of scalars in the form l ( tⁱ );
B compute f_t from the l ( tⁱ ) and deduce g_t (square-free part of f_t');
C compute l ( X_j tⁱ ) for i = 1 ... degree ( f_t ), j = 1 ... n;
D deduce g_{t, i}, i=1..n

In the case of [2], f_t is the minimal polynomial of t and is computed using Berlekamp-Massey algorithm. In [8], f_t is the characteristic polynomial of t and the author remarks that the Trace ( tⁱ ) are its Newton sums. Also both methods deduce [B] from [A] performing O ( D² ) arithmetic operations. Note that the lost of multiplicities in [2] is due to the fact that f_t is the minimal polynomial of t (not its characteristic polynomial). Steps [C] and [D] are similar in both cases. To preserve the multiplicities and to get rid of the probabilistic aspect related to the use of the generic linear form l, we mix both approaches :

Algorithm RURCandidate-BSGS

Input : B, T, t, and mulTk(u) a function that computes t^k u modulo I for any u Î Q [ X₁, ..., X_n ] / I, expressing the result w.r.t. B.
Output : a RUR-Candidate of I w.r.t. t.

Compute k = ëD^{1 / 2} ûand k' = D / k
Compute X_i t^j, i = 1 ... n, j = 1 ... k' (modulo I) expressed as a vectors w.r.t. B;
Compute Q = [ Trace ( w_i w_j ) ]_{i, j} the generalized Hermite's quadratic form;
set t⁰ = [ 1, 0, ..., 0 ];
for i = 0 ... k - 1 do
- [ Trace ( t^{k' i} w₁ ), ..., Trace ( t^{k' i} w_D ) ] = Q.t^{k' i}
- for j = 1 ... k' do
  - Trace ( t^{k' i + j} ) = t^j . [ Trace ( t^{k' i} w₁ ), ..., Trace ( t^{k' i} w_D ) ]
  - for l = 1 ... n do Trace ( X_l t^{k' i + j} ) = X_l t^j . [ Trace ( t^{k' i} w₁ ), ..., Trace ( t^{k' i} w_D ) ]
- t^{k' i} = mulTk(t^{k' ( i - 1 )});
for j = 1 ... k' do Trace ( t^{D - k' + j} ) = t^j . [ Trace ( t^{D - k'} w₁ ), ..., Trace ( t^{D - k'} w_D ) ]
Solve the triangular linear system (D-i)a_i=å_j=0ⁱa_i-jTrace(tⁱ) and set f_t ( T ) = å_{i
= 0}^D a_{D - i} Tⁱ (g_t ( T ) is the derivative of the square-free part of f_t).
for j = 1 ... n Set g_{t, j} ( T ) = å_{i = 0}^{d - 1} Trace ( X_j tⁱ ) H_{d - i - 1} ( T ) where d is the degree of the square-free part of f_t and H_j ( T ) = å_{i =0}^j a_i T^{i - j}

For getting the right complexity, the function mulTk used in [2] performs the following operations :

if t^k = å_{j = 1}^D a_j w_j and t^{k ( i - 1 )} = å_{j =
1}^D b_j w_j , the product can be rewritten as t^k .t^{k ( i - 1 )} = å_{m Î T} c_m .m where c_m is a sum of some a_i b_j. It requires at most D² operations to compute the coefficients c_m and then at most # T linear combinations of vectors of size D to get the result. It thus costs O ( # T D ) operations to compute the reduced product.

Our second result shows that one can check that the obtained RUR-Candidate is a RUR performing O ( n # T D^{3 / 2} ) arithmetic operations, so that it produces the same output as [8] with the same computing time as the probabilistic computation of the RUR-Candidate from [2]. Let's suppose that f_t, g_t, g_{t, 1}, ..., g_{t, n} is a RUR-Candidate w.r.t. a linear form t. From [8], this candidate will be a RUR is and only if the polynomials f_t ( t ), g_t ( t ) X_i - g_t,
i ( t ), i = 1 ... n belong to I or equivalently if and only if Trace ( f_t w_j ) = Trace ( ( g_t X_i - g_{t, i} ) w_j ) = 0, " i = 1 ... n, j = 1 ... n. One way for performing such a test is to first compute the images of f_t ( t ), g_t ( t ) X_i - g_{t, i} ( t ), i = 1 ... n in Q [ X₁, ..., X_n ] / I expressed as vectors w.r.t. B and then to compute the needed traces using the relation [ Trace ( p ( t ) w₁ ), ..., Trace ( p ( t ) w_D ) ] = Q.p ( t ). The computation of the reduced expression of a given polynomial p of degree D - 1 can be done in # T D^{3 / 2} operations adapting slightly the algorithm from [3] :

Algorithm ReducedEval

Input : B, T, t, mulTk(u) and p = å_{i = 0}^D p_i Tⁱ
Output : p ( t ) Î Q [ X₁, ..., X_n ] / I as a vector w.r.t. B

Compute the reduced expressions of t, t², ..., t^k w.r.t. B.
Set u = [ 0, ..., 0 ]
for i = k' ... 0 do u = mulTk ( t^k, u ) + å_{j =
0}^k g_{ki + j} t^j
return(u)

The computing time of ReducedEval is clearly O ( D^{1 / 2} T_k ) if T_k is the computing time of mulTk and the algorithm for checking if a RUR-Candidate is a RUR then becomes :

Algorithm CheckRURCandidate

Input : f_t, g_t, g_{t, 1}, ..., g_{t, n} a RUR-Candidate, B, T, t
Output : a boolean which is true if and only if the RUR-Candidate is a RUR

Compute Q = [ Trace ( w_i w_j ) ]_{i = 1 ... D}^{j = 1
... D}
Compute f_t ( t ) = ReducedEval(f_t, B, T),
if Q.f_t ( t ) ¹ [ 0, ..., 0 ] then return(false);
Compute g_t ( t ) = ReducedEval(g_t, B, T);
for i = 1 ... n do
- Compute g_{t, i} ( t ) = ReducedEval(g_{t, i}, B, T);
- Deduce from T, M_{X_i} the matrix of u ® X_i u in Q [ X₁, ..., X_n ] / I w.r.t. B
- Compute test = Q. ( M_{X_i} g_t ( t ) + g_{t, i} ( t ) );
- if test ¹ [ 0, ..., 0 ] then return(false);
return(true)

Let's denote by RUR-ORIG the algorithm from [8]. For providing a full and honest comparison with RURCandidate-BSGS one have to take into account the memory consumed in both cases.

Our third result shows that RUR-ORIG do not need to store the full multiplication table, but simply the reductions of the traces of elements of B and the products X_i m, m Î B. This must be compared to the full storage of the multiplication table (# T D) needed by algorithm RURCandidate-BSGS (but also by algorithm from [2]). For systems with a large number of roots, we then loose the benefit of the baby-step/giant-step strategy since the full multiplication table can not be stored in practice. One can correct this by simply replacing the function mulTk in algorithm RURCandidate-BSGS by :

pre-computing the matrix of multiplication by t^k in Q [ X₁, ..., X_n ] / I, denoted by M_t^k from now;
replacing mulTk by a matrix/vector product using M_t^k

Of course, the computation of M_t^k sacrifices the complexity when counting the number of operations in Q since it requires O ( D³ ) operation, but , if we take in account the growth of coefficients, it appears to be comparable to the computation of the multiplication table; Its use strongly decreases the cost of all the other functions : algorithm RURCandidate-BSGS then requires O ( D^{5 / 2} ) operations in Q and algorithm CheckRURCandidate requires O ( nD^{5 / 2} ) operations in Q. Thus the full complexity of this algorithm for computing a RUR (including the verification) is O ( nD^{5 / 2} ) which is a priori better than [8] and [2].

The choice of the right algorithm (the choice of the right mulTk function) will strongly depends on the system to be studied, but, in general, if D or n is large, one will prefer the use M_t^k to save memory. In practice, the gain compared to the RUR-ORIG algorithm is inexistent except if one want only to compute a RUR-Candidate, skipping the verification.

The second part of our contribution deals with the use of the RUR to check if the zeroes of a zero-dimensional system verifies or not some polynomial equations/inequations/inequalities. In particular we propose an algorithm that computes all the sign conditions realized by a set of polynomials at the zeros of a zero-dimensional system. Its computing time complexity is D times less than the one of algorithm 11.18 p. 375 in [1] for the same input (T). Given any polynomial f, the formulas from [8] or [2] can be used to compute a rational function g_{t, f} / g_t which takes the same values as f at the zeroes of I. According to the results above, given a set of polynomials F = { f₁, ..., f_s }, one can compute a RUR and the rational functions g_{t, f_i} in O ( t₁ + s.D² ) if t₁ is the computing time of the RUR. Thus, computing the sign conditions realized by the f_i remains to computing the sign conditions realized by the g_{t, f_i} at the roots of f_t. We can then substitute the ``Sturm query`` algorithm based on Hermite's quadratic form in [1] (computing time in O ( D³ ) by its equivalent for univariate polynomials (see also for example [1] - computing time in O ( D² ) for the naive version).

References :

References

[1]: S. Basu, R. Pollack, and M.-F. Roy. Algorithms in real algebraic geometry, volume 10 of Algorithms and Computations in Mathematics. Springer-Verlag, 2003.
[2]: A. Bostan, B. Salvy, and É. Schost. Fast algorithms for zero-dimensional polynomial systems using duality. Applicable Algebra in Engineering, Communication and Computing, 14(4):239 -- 272, 2003.
[3]: R.-P. Brend and H.-T. Kung. Fast algorithms for manipulating formal power series. J. Assoc.Comput. Mach., pages 581--595, 1978.
[4]: J.-C. Faugère. A new efficient algorithm for computing gröbner bases (f₄). Journal of Pure and Applied Algebra, 139(1-3):61--88, June 1999.
[5]: J.C. Faugère, P. Gianni, D. Lazard, and T. Mora. Efficient computation of zero-dimensional gröbner basis by change of ordering. Journal of Symbolic Computation, 16(4):329--344, October 1993.
[6]: M. Giusti, G. Lecerf, and B. Salvy. A gröbner free alternative for solving polynomial systems. Journal of Complexity, 17(1):154--211, 2001.
[7]: M. Noro and K. Yokoyama. A modular method to compute the rational univariate representation of zero-dimensional ideals. Journal of Symbolic Computation, 28(1-2):243--263, 1999.
[8]: F. Rouillier. Solving zero-dimensional systems through the rational univariate representation. Journal of Applicable Algebra in Engineering, Communication and Computing, 9(5):433--461, 1999.
[9]: V. Shoup. Efficient computation of minimal polynomials in algebraic extensions of finite fields. In ISSAC'99.
[10]: P. Trébuchet. Vers une résolution stable et rapide des équations algébriques. PhD thesis, Université Pierre et Marie Curie, 2002.

This document was translated from L^AT_EX by H^EV^EA.