Abstract

In previous work, we have introduced the technique of relaxed power series computations. With this technique, it is possible to solve implicit equations almost as quickly as doing the operations which occur in the implicit equation. In this paper, we present a new relaxed multiplication algorithm for the resolution of linear equations. The algorithm has the same asymptotic time complexity as our previous algorithms, but we improve the space overhead in the divide and conquer model and the constant factor in the F.F.T. model.

1Introduction

Let be an effective ring and consider two power series and in . In this paper we will be concerned with the efficient computation of the first coefficients of the product .

If the first coefficients of and are known beforehand, then we may use any fast multiplication for polynomials in order to achieve this goal, such as divide and conquer multiplication [KO63, Knu97], which has a time complexity , or F.F.T. multiplication [CT65, SS71, CK91, vdH02], which has a time complexity .

For simplicity, “time complexity” stands for the required number of operations in . Similarly, “space complexity” will stand for the number of elements of which need to be stored. The required number of multiplications in the divide and conquer algorithm satisfies the following recurrence relations:

When performing computing only the product truncated at order , then the number of multiplications needed by the divide and conquer algorithm becomes

For certain computations, and most importantly the resolution of implicit equations, it is interesting to have so called “relaxed algorithms” which output the first coefficients of as soon as the first coefficients of and are known for each . This allows for instance the computation of the exponential of a series with using the formula

(1)

In [vdH97, vdH02], we proved the following two theorems:

Theorem 1. There exists a relaxed multiplication algorithm of time complexity and space complexity , and which uses multiplications.

Theorem 2. There exists a relaxed multiplication algorithm of time complexity and space complexity .

Although these theorems are satisfactory from a theoretical point of view, they can be improved in two directions: by removing the logarithmic space overhead in the divide and conquer model and by improving the constant factor in the F.F.T. model.

In this paper, we will present such an improved algorithm in the case of relaxed multiplication with a fixed series. More precisely, let and be power series, such that is known up to order . Then our algorithm will compute the product up to order and output as soon as are known, for all . We will prove the following:

Theorem 3. There exists a relaxed multiplication algorithm with fixed series of time complexity , of space complexity , and which uses multiplications.

We also obtain a better constant factor in the asymptotic complexity in the F.F.T. model, but this result is harder to state in a precise theorem.

The algorithm is useful for the relaxed resolution of linear differential or difference equations. For instance, the exponential of a series can be computed using multiplications in . Moreover, the new algorithm is very simple to implement, so it is likely to require less overhead than the algorithm from theorem 1.

Our algorithm is based on the recent middle product algorithm [HQZ00, HQZ02], which is recalled in section 2. In section 3 we present our new algorithm and in section 5 we give some applications.

In our algorithms we will use the following notations: the data type stands for truncated power series of order , like . Given and , we will denote . Given and , we also denote . We will denote by the type, whose elements are references to elements of type . If and , then we assume that .

2The middle product

Let and be two truncated power series at orders resp. . The middle product and is defined to be the truncated power series of order , such that for all . In figure 1, corresponds to the colored region.

Figure 1. Illustration of the middle product.

The middle product of and can be computed using only three multiplications, using the following trick:

This trick may be applied recursively in order to yield an algorithm which needs exactly the same number of multiplications as the divide and conquer algorithm for the computation of the product of two polynomials of degree . More precisely, the following recursive algorithm comes from [HQZ00, HQZ02].

if then return

if is even

return

In [HQZ02] it is also shown that, in the F.F.T. model, the middle product can still be computed in essentially the same time as the product of two polynomials.

3Relaxed multiplication with a fixed series

Let and be power series, such that is known up to order . In this section, we present an algorithm which computes the product up to order . For each , the algorithm outputs as soon as are known.

The idea of our algorithm is similar to the idea behind fast relaxed multiplication in [vdH97, vdH02] and based on a subdivision of the triangular area which corresponds to the computation of the truncated power series product. This subdivision is shown in figures 2 and 3, where each parallelogram corresponds to the computation of a middle product.

Figure 2. The subdivision used for the new relaxed multiplication algorithm.

More precisely, let and assume that are known. Then the contribution of to may be computed using the middle product algorithm from the previous section. The relaxed truncated products and may be computed recursively.

In order to implement this idea, we will use an in-place algorithm, which adds the result of to a reference to an element of . Denote by the initial value of . Then the in-place algorithm should be called successively for . After the last call, we have . Taking , the algorithm computes .

if then and return

if then

if then

if then

The number of multiplications used by is determined by the relations

By induction, it follows that . The overall time complexity satisfies

so . The algorithm being in-place, its space complexity is clearly . This proves theorem 3.

In it is also interesting to use the above algorithm in the F.F.T. model. We then have the estimation

for the asymptotic complexity . If , this yields

This should be compared with the complexity of the previously best algorithm and with the complexity of the standard fast relaxed multiplication algorithm.

Notice that we rarely obtain the complexity in practice. In the range where , we obtain

4A worked example

Let us consider the computation of up till order using our algorithm and the formula

with and . We start with in and perform the following computations at successive calls for :

1. We set , so that

   

   and .

2. We recursively apply to , , and . This requires the computation of . We thus increase , so that

   

   and .

3. The two nested recursive calls to now lead to the increase of by , so that

   

   and .

4. We now both have and . So we first compute and set . We next recursively apply to , , and , which leads to an increase of by . Alltogether, we obtain

   

   and .

5. We recursively apply to , , and . This leads to the increase , so that

   

   and .

6. The two nested recursive calls lead to the increase , so that

   

   and .

The entire computation is represented schematically in figure 3.

Figure 3. Illustration of an order relaxed multiplication.

5Applications

First of all, let us consider the problem of relaxed division by a fixed power series. In other words, we are given two power series and , where is known up to order and . We want an algorithm for the computation of up to order , such that is computed as soon as are known for each . Now we have

where . We may thus compute in a relaxed way using the algorithm from the previous section. Computing up till terms will then necessitate multiplications in .

Let us next consider a linear differential equation

(2)

with and . Given initial conditions for , there exists a unique solution to this equation. We may compute this solution using the relaxed algorithm from the previous section, the above algorithm for relaxed division, and the formula

In order to compute coefficients, we need to perform multiplications in and multiplications and divisions by integers. If , then we only need multiplications.

For instance, the exponential of a series with satisfies the equation

so can be computed using multiplications, using the formula (1).

More generally, consider the solution to (2) with the prescribed initial conditions, and let be another series with . Then the composition again satisfies a linear differential equation. Indeed, we have the relations

Postcomposing (2) with and using these relations, we obtain a linear differential equation for .

In fact, our algorithm may be used to solve far more general linear equations, such as linear partial differential equations, or linear differential-difference equations. In the case of difference equations, we notice that the relaxed multiplications in the algorithms from [vdH02] for relaxed right composition with a fixed series all have one fixed argument. So we may indeed apply the algorithm from section 3.

We finally notice that our algorithm can even be used in a non-linear context. Indeed, after computing coefficients of a truncated relaxed product, the computation of the remaining products reduces to the computation of two truncated relaxed products with one fixed argument. Actually, this corresponds to an implicit application of Newton's method.

6Conclusion and open questions

We have presented a new algorithm for relaxed multiplication. Although the new algorithm does not yield a significant improvement from the asymptotic complexity point of view, we do expect it to be very useful for practical applications, such as the exponentiation of power series.

First of all, the algorithm is easy to implement. Secondly, it only needs a linear amount of memory in the range where divide and conquer multiplication is appropriate. In combination with F.F.T. multiplication, the algorithm yields a better constant factor in the asymptotic complexity.

When implementing a library for power series computations, it is interesting to incorporate a mechanism to automatically detect relaxed and fixed multiplicands in a complex computation. This is possible by examining the dependency graph. With such a mechanism, one may use the new algorithm whenever possible.

Some interesting questions remain open in the divide and conquer model: can we apply Mulders' trick [Mul00, HZ02] for the computation of “short products” in our setting while maintaining the linear space complexity (see figure 4)? In that case, we might improve the number of multiplications in theorem 3 to .

Figure 4. Using Mulders' trick in combination with the middle product.

In a similar vein, does there exist a relaxed multiplication algorithm of time complexity and linear space complexity? This would be so, if the middle product algorithm could be made relaxed in an in-place way (the algorithm is already “essentially relaxed” in the sense of [vdH97, vdH02] in the divide and conquer model).

As it stands now, with the above questions still unanswered, the original relaxed multiplication algorithm from theorem 1 remains best from the time complexity point of view in the divide and conquer model. Moreover, Mulders' trick can be applied in this setting, so as to yield a short relaxed multiplication algorithm of complexity , or even better [HZ02].

This has surprising consequences for the complexities of several operations like short division and square roots: we obtain algorithms of time complexities and when using space, while the best known algorithms which use linear space have time complexities and . In order to obtain the complexity of in the case of square roots, one should use a relaxed version of the fast squaring algorithm from [HQZ02], which is based on middle products.

We finally remark that this relaxed version of squaring using middle products is also interesting in the F.F.T. model. In this case, the relaxed middle product corresponds to a full relaxed product with one fixed argument. Such products can be computed in time , so that we obtain a relaxed squaring algorithm of time complexity . This is twice as good as general relaxed multiplication. In the non-relaxed setting, squares can be computed in a time between and , depending on whether most time is spent on inner multiplications or fast Fourier transforms respectively.

Bibliography