On the complexity of skew arithmetic Joris van der Hoeven LIX, CNRS École polytechnique 91128 Palaiseau Cedex France Email: vdhoeven@lix.polytechnique.fr Web: http://lix.polytechnique.fr/~vdhoeven March 28, 2012

1.Introduction

Let be an effective field of constants of characteristic zero, so that all field operations can be carried out by algorithms. Given an indeterminate and the derivation , where , we will study various operations in the skew ring , such as multiplication, division, greatest common divisors, series solutions, etc. In analogy with the commutative case, we will give bounds for the computational complexities of these operations in terms of the complexity of operator multiplication.

For our complexity measures, it is convenient to assume that all field operations can be carried out in constant time . We will try to express the complexities of our algorithms in terms of the following standard complexities:

• The time required for the multiplication of two polynomials of degrees and coefficients in . It is classical [6] that and if admits sufficiently many -th roots of unity [7].

• The complexity of multiplying two matrices with entries in . It is classical [13, 11, 8] that , although in practice.

We will denote by the subset of of polynomials of degree . Likewise, we denote by the set of operators of degree in and degree in .

Now consider two linear differential operators . We start with studying the following complexities:

• The complexity of multiplying and .

• The complexity of applying to a vector of polynomials in .

• The cost to compute a fundamental system of solutions to the monic equation in , up to order , while assuming the existence of such a fundamental system.

• Given a vector of truncated power series in , the cost of computing a monic operator in with .

The special case was first studied in [15], where it was shown that , using evaluation-interpolation techniques. The inverse bound has been proved in [5]; this paper also contains detailed information on the constant factors involved in these bounds.

For fixed constants , we notice that , , , etc. In this paper, we will freely use this remark without further mention. In order to simplify our complexity estimates, it will be convenient to make a few additional assumptions. First of all, we will assume that , whence in particular . We will also assume that the function is increasing and that is increasing in both and . This will indeed be the case for the complexity bounds for that will be given in section 3.

In section 2, we will first prove (see theorems 2 and 3) that the problems of multiplication and operator-vector application are essentially equivalent when . In section 3, we recall the best available bounds in the case when . It remains an open question whether these bounds are optimal.

In section 4, we show that the problems of computing fundamental systems of solution and its inverse can be reduced to operator multiplication modulo a logarithmic overhead (see theorems 13 and 14). This provides a dual way to perform operations on differential operators by working on their fundamental systems of solutions. In section 5, we start with the operations of exact division and division with remainder. In section 6, we consider greatest common divisors and least common multiples. Again, we will show how to express the complexities of these operations essentially in terms of the complexity of multiplication (see theorems 19, 21, 23 and 26).

To the best of our knowledge, the idea to perform operations on linear differential operators via power series solutions was first proposed (but only partially worked out) in [3, Chapter 10]. We were independently aware of this possibility and prefer the use of fundamental systems of solutions (so as to force a clean bijection between operators and solution spaces). It is also possible to mimic classical divide and conquer algorithms for division, greatest common divisors and least common multiples, while using adjoints in order to perform the recursive operations on the appropriate side. Such algorithms were implemented inside Mathemagix [18] and we plan to analyze them in a forthcoming paper.

2.Evaluation and interpolation

The key argument behind the proof from [15] that is the observation that an operator is uniquely determined by its images on the vector . This makes it possible to use a similar evaluation-interpolation strategy for the multiplication of differential operators as in the case of FFT-multiplication of commutative polynomials. More precisely, given , let be the matrix of the mapping with respect to the bases and :

Proof. Consider the expansion of with respect to

For all , we have

In other words, is a lower triangular band matrix

of bandwidth . The coefficients on the -th subdiagonal of are exactly the result of a multipoint evaluation of at . It is classical [10, 14, 2] that both multipoint evaluation and the inverse operation of interpolation can be performed in time . Doing this for each of the polynomials yields the result.

Theorem 2. If , then

(1)

Proof. Let and assume that we want to compute . We may evaluate in time . We may also evaluate in time . Using the lemma, we may recover from in time . This completes the proof.

Theorem 3. If , then

(2)

Proof. Assume now that we are given , as well as a vector and that we want to evaluate . This is equivalent to evaluating the operator at the vector . It is classical [1] that can be computed in time . Using the lemma, we may compute the unique operator with in time . We may next compute the product in time . The lemma finally allows us to evaluate at in time , thereby yielding .

3.Basic complexity bounds

Let us review the best know algorithms (asymptotically speaking, and up to constant factors) for the multiplication of linear differential operators and for the evaluation of linear differential operators at vectors of polynomials. We will treat the cases and separately.

3.1.Large degrees

Theorem 4. If , then

Proof. Consider two operators . Then we may compute their operator product using the formula

(3)

attributed to Takayama, where

denotes the commutative product of and . Commutative products can be computed in time using Kronecker substitution [12, 9], whence the result follows.

In practice, it is often possible and best to compute the commutative products using bivariate FFT multiplication. In that case several of the FFT-transforms can be shared. For instance, if , then the most expensive step is to compute the transforms with respect to of the coefficients in of the first derivatives . For large , this optimization yields an algorithm of complexity .

Theorem 5. If , then

Proof. This is a direct consequence of theorems 3 and 4.

In practice, in the domain where FFT-multiplication is most efficient, it is better to use a more direct method to obtain this result. Given and , we use the following algorithm:

• Compute the FFT-transforms of with and the FFT-transforms of the coefficients of with respect to .

• From these values, deduce the FFT-transforms of the entries of using scalar matrix-vector multiplications.

• Recover using inverse transforms.

This algorithm has a complexity , for large .

If , then the following result becomes more efficient for the evaluation of linear differential operators at vectors of polynomials:

Theorem 6. If , then we have

Proof. We may cut both and into pieces in and . Hence . Here we repeatedly use the commutation rule , when considering and as operators. The twist can be computed in time , for [1].

If both , this yields the following more efficient algorithm for the multiplication of linear differential operators:

Theorem 7. If , then we have

Proof. Direct consequence of theorems 2 and 6.

We recall from [5] that . More generally, we have:

Proof. By the result from [5], the problem is equivalent to the computation of operators in with a fixed operator . Setting , we may compute in time . We may directly read off the products from the result.

Remark 9. An interesting open problem at the time of writing concerned the existence of a better bound for than the one given in theorem 7. In collaboration with Benoit and Bostan, we have recently been able to prove the sharper bound for the case when .

3.2.Large orders

Theorem 10. If , then

Proof. Let and consider the expansion

of in . Then we have

For each , both the Taylor shift and the product can be computed in time [1].

Theorem 11. If , then

Proof. Let and . We may compute in time , since this really amounts to the computation of matrix products of size . Writing for a constant matrix , we may thus compute in time .

Theorem 12. If , then

Proof. Let . By lemma 1, we may compute and in time . Since both of these matrices are band matrices of bandwidths , we may compute the product

in time . Again by lemma 1, we may reconstruct from in time .

4.Local solutions

From now on, we will assume that . We recall that an operator of order is said to be non singular at , if its leading coefficient does vanishes at . We will say that an operator of order is non singular (at the origin) if and is non singular as an operator in .

Given a non singular differential operator of order , the equation admits a canonical fundamental system of solutions in , with the property that and for all with . Conversely, given a -linearly independent vector of power series , there exists a unique monic operator of order with . Let us show how to convert efficiently between these two representations.

Theorem 13. Let be a differential operator of order , which is non singular at the origin, and let be its canonical fundamental system of solutions. Then we may compute up to order in time . In other words,

(4)

Proof. Modulo multiplying on the left by , we may assume without loss of generality that is monic. Since is non singular at the origin, we have . Rewritten in terms of , this means that is of the form

for certain . Setting , we observe that maps into . We now compute using the “recursive” formula

(5)

where

The equation (5) is a schoolbook example for applying the strategy of relaxed resolution of power series equations [16, 17]. Since operates coefficientwise, it can be computed in linear time. The main cost of the computation therefore reduces to the relaxed evaluation of . Using fast relaxed multiplication, this amounts to a cost

Using the monotonicity assumption and theorem 3, the result follows.

In what follows, given a non zero series in , we denote by its valuation. Given a vector of elements in a -vector space, we will also denote by the subvector space generated by the entries of , and

Theorem 14. Let be -linearly independent. Then there exists a unique monic operator with . Moreover, given the truncation of at order , we may compute at order in time . In other words,

(6)

Proof. Modulo a triangularization of , we may assume without loss of generality that . We define operators by

Then annihilates and for any other operator with , we would have , which is in contradiction with the fact that . Moreover, by induction over , we observe that the coefficient of in is given by and the coefficients of in can be expressed in terms of the coefficients of in . In particular, the truncation of at order is uniquely determined by the truncation of at order .

In order to explicitly compute up to a given order, it is more efficient to use a divide and conquer approach. More precisely, given we compute using the following method:

• If , then we take .

• Otherwise, let with .

• Compute .

• Evaluate .

• Compute .

• Return .

If , then it is easy to check that . For a fixed constant , we thus have

The result now follows from the monotonicity assumption.

Remark 15. If is increasing in for some , then the bound further simplifies to .

Remark 16. We notice that the operator in theorem 14 is singular if and only if , and if and only if .

Although a general operator can be singular at the origin, many operations on operators (such as division and greatest common divisors) commute with translations , and the following lemmas can be used in order to reduce to the case when is non singular at the origin.

Proof. In [15, 5], it is shown how to perform these rewritings using matrix products, so that the result follows from theorem 8.

Proof. Let be the leading coefficient of . Since , we have for some . Using fast multipoint evaluation [4], we may find such a point in time .

5.Division

From the formula (3) it is clear that both the degrees in and are additive for the multiplication of operators . In particular, if and is left or right divisible by , then the quotient is again in .

Proof. By lemmas 17 and 18, and modulo a shift , we may assume without loss of generality that and are non singular at the origin. We now use the following algorithm:

• We first compute the canonical fundamental system of solutions to up to order . By theorem 13, this can be done in time .

• We next evaluate and compute a -basis for at order . This can be done in time , by theorems 3 and 8, and using linear algebra. Since is non singular, we have for all . In particular, the elements of of valuations are mapped to set which spans a vector space of dimension . This shows that .

• We now compute the monic annihilator of at order . This can be done in time , by theorem 14.

• We return the truncation of at order , where .

Since each of the steps can be carried out in time , the result follows.

It is classical that euclidean division generalizes to the skew polynomial ring . In other words, given operators where , there exist unique operators and in with

and . If and is the leading term of with respect to , then left multiplication of by allows us to remain in the domain : there exist unique and in with

(7)

and . The operators and are usually called pseudo-quotients and pseudo-remainders. In some cases, a non trivial polynomial can be factored out in the relation (7). Let be monic, of maximal degree, such that . Then we call and the “simplified” pseudo-quotient and pseudo-remainder of and .

Proof. Let for each . Modulo a base change, we may assume without loss of generality that . Let be the operator with

and let denote the inverse operator. Let be the operator with

Writing and , we have

In other words, and its inverse operate coefficientwise and coefficients can be computed in time .

Putting with for each , we may rewrite the equation as

and we observe that the coefficient of in the righthand side of (8) only depends on earlier coefficients of in . In particular, we may solve the equation using a relaxed algorithm. Then the main cost is concentrated in the relaxed evaluation of . As in the proof of theorem 13, this evaluation can be done in time .

Theorem 21. Let with and . Skew pseudo-division of by and simplification yields a relation

where . If is such that , then and can be computed in time .

Proof. Modulo a shift , we may assume without loss of generality that and are non singular at the origin. We now use the following algorithm:

• We compute the canonical fundamental system of solutions to up to order . This requires a time .

• We compute with up to order . This requires a time .

• We determine the operator with up to order . The lemma shows that this can be done in time .

• By theorem 14, we have and is known up to order . Now are truncated rational functions, for which the degrees of the numerators and denominators are bounded by . Using rational function reconstruction [9], we may thus compute with in time . Taking , we find .

• Once and are known, we compute using the algorithm from theorem 19.

The total complexity of this algorithm is bounded by .

Remark 22. In the above proof, we have assumed that is known beforehand. In general, we may still apply the above algorithm for a trial value . Then the algorithm may either fail (for instance, if ), or return the triple under the assumption that . We may then check whether the triple is correct in time . Applying this procedure for successive guesses , the algorithm ultimately succeeds for an with . Using the monotonicity hypothesis, the total running time thus remains bounded by .

6.Euclidean operations

It is classical that greatest common divisors and least common multiples exist in the skew euclidean domain : given two operators , the greatest common divisor and the least common multiple are the unique monic operators with

Assume now that and let and be monic polynomials of minimal degrees, such that and are in . Then we call and the (simplified) pseudo-gcd and pseudo-lcm of and .

Proof. We compute using the following algorithm:

• We compute the canonical fundamental systems of solutions and to and at order . This can be done in time .

• Using linear algebra, we compute a basis for at order . This can be done in time . Since is non singular, we have . Hence, .

• We compute at order . By theorem 14, this can be done in time .

• We compute from using rational function reconstruction.

This algorithm requires a running time .

Remark 24. In the above proof, we have again assumed that is known beforehand. Below, we will discuss ways to check the correctness of the computed result for a trial value , after which a similar strategy as in remark 22 can be applied. During the relaxed computation of and , we may also check whether at each next coefficient. In the particular case when , the running time of the algorithm will then be bounded by , where is the smallest order at which common solutions no longer exist. This kind of early termination only works for this very special case.

Remark 25. Notice that might be singular at the origin, even if , and are not. This happens for instance when is the minimal annihilator of the vector and the minimal annihilator of the vector , so that .

Proof. Similar to the proof of theorem 23, by taking instead of .

Remark 27. The above algorithms can be generalized to gcds and lcms of more than two operands. This is usually more efficient than the repeated computation of gcds or lcms of pairs.

The assumption that should be non singular is still a bit unsatisfactory in theorems 23 and 26, even though the probability that a randomly chosen point is singular is infinitesimal. If we drop this assumption, then we still have in the proof of theorem 23. Consequently, “candidate” pseudo-gcds found by the algorithm are genuine pseudo-gcds whenever pseudo-divides both and . Using the division algorithms from the previous section, this can be checked in time in the case of gcds and in the case of lcms.

An alternative way to check whether candidate gcds and lcms are correct is to compute Bezout and Ore relations. More precisely, given with , there exist operators with

and . The matrix at the righthand side will be called the Euclidean matrix of and . In a similar way as above, we may define a (simplified) pseudo-Euclidean matrix with entries in , whenever . We will say that is non singular at , if the denominators of and do not vanish at .

Proof. Assuming known, we compute at order as follows:

• We compute the canonical fundamental systems of solutions and to and at order .

• We compute a basis for at order , together with bases and for the supplements of in resp. . We also compute at order .

• We solve the systems and in resp. at order , using lemma 20.

• We compute a basis for at order , as well as bases and for the vector spaces resp. at order .

• We compute and at order .

We finally compute from and using rational function reconstruction. The complexity analysis and the remainder of the proof is done in a similar way as in the proofs of theorems 21 and 23.

With the above techniques, we may at least verify whether computed pseudo-gcds or pseudo-lcms are correct. For a fully deterministic algorithm, we still need a way to find a point where is non singular. This can be done by brute force. Let us state the result for pseudo-gcds; similar deterministic results hold for pseudo-lcms and pseudo-Euclidean matrices.

Proof. Let , , and assume first that we know . Then, at distinct random points where and are non singular, we compute canonical fundamental systems of solutions and at order . This can be done in time . We now pick a point at which the dimension of is maximal and apply the algorithm from theorem 23 in order to find . If is unknown, then we use a sequence of guesses , as in the previous proofs.

Bibliography