9.2 FormalPowerSeries

This domain implements the ring R[[x]] of formal power series over a ring R.

For a greater range of applicability, our Aldor implementation only requires that R provides ring-like operations, i. e., R must only satisfy ArithmeticType.

A formal power series f is an infinite formal sum of the form:

(81)

A series is basically a stream of elements of R. However, we want to be able to deal with code like the following.

Note that the series equation actually is s = x + s² which, in fact, has two solutions.

s1	= = x + x2 + 2x3 + 5x4 + 14x5 + O(x6)	(82)
s2	= = 1 − x − x2 − 2x3 − 5x4 − 14x5 + O(x6)	(83)

In fact, such an approach is reasonable in order to help prevent infinite recursion. Note that in our design we never see the whole defining series equation. All that we can build on are data structures and the local operators + and *. So we cannot invoke a solver that returns the radical expression and from there generate the series.

We do not want to invoke any solver at all, not even one that works on elements of R in order to solve for the first few coefficients of the series. Thus we first try to figure out from the local data what the biggest possible order would be so that the series still fulfils the equation.

To do that algorithmically, we first assume an unknown order an try to adjust it at the operator places. In fact, to break recursion, it is sufficient to work with an approximate order. An approximate order of a series is either unknown or it is smaller or equal to the true order of the series.⁴ So internally, we store an approximate order and the true order of the series. Initially, (except for certain series like 0 or 1) these values are set to unknown. If the first coefficient needs to be accessed, the approximate order is computed (and not earlier). The true order is then figured out starting from the approximate order and checking already accessed elements.

Another example that we want to be able to deal with is given by the following code.

Note that from this example it becomes clear that our implementation must be fully lazy, since at the time we define s in the program, there is no information about t. Every compuation has to be postponed until the series is asked to reveal one of its coefficients.

Type Constructor

FormalPowerSeries

Usage

macro R == Integer;
f: FormalPowerSeries R := 1 + monom + term(-1, 2);

Description

Series with integer coefficients.

FormalPowerSeries is the domain that represents series with integer coefficients, i. e., formal series f of the form

(86)

with f_i ∈ R for all i ≥ 0.

Our implementation, in fact, creates a new series for every operation. So for

Similarly, for

That seems to be a waste of memory, but it basically saves intermediate results, that would have to be recomputed otherwise.

If any improvement with respect to memory consumption is started later, one should take care not to remove the structure that stores the approximate order of these auxiliary series.

The approximate order is heavily used to avoid recursion in the above examples. Basically, before any coefficient is accessed, an approximate order is computed for every series involved in the expression.

If we abbreviate x = monom, we can write the second example as:

Now if s₀ is to be computed, we have to compute 1₀ + v₀. We know that 1₀ = 1. Since we have precomputed the approximate order of v, we know that v₀ = 0, so we can skip its actual computation without recursing through u and s.

9.2.1 Representation

Note that if the following data structure is changed, the function set! must be changed appropriately.

A value of unknown stored in approximateOrder should trigger computation of an approximate order. But it should trigger the computation only if it is necessary to get the real value of a coefficient of the series.

The value unknown is returned from the function order to the user if it is not yet known what the (true) order of the series is. If an approximate order has been computed then each invocation of the function coefficient triggers an attempt to improve the approximate order until the true order has been found.

If for a series f the value for approximateOrder is a non-negative number n, then it is assured that the series coefficients are zero for all indicies smaller than n, in other words the series can be written in the form

(89)

The entry stored in order is either unknown or equal to what is stored in approximateOrder.

An unknown order corresponds (nearly⁵ ) to ∞ with respect to arithmetic, but there is only one series for which ∞ would, in fact, be the correct value, that is the 0 series.

Note that we do not say that the value stored in approximateOrder is the true order of the series f. It is still possible that f_n = 0. For our purpose the computation of a sufficiently big n is, however, enough.

In fact, if we know the approximate order of two non-zero series s and t then the approximate order of operations on s and t is given by the following equations. (We abbreviate approximateOrder by ord.)

Note that in general, for the sum of series it only holds the inequality with a ≥ sign in (90). We are, however, completely satisfied with taking (90) as the definition of an approximate order of the sum of two series, since all we need is to prevent infinite recursion.

For integration we actually take also a non-zero integration constant into account.

9.2.2 Initialization of the Representation

Recall Convention 2. Operations on series like + or * do not trigger the computation of the (approximate) order of the resulting series. In fact, such operations must not do any series compuation at all, since for series which are recursively defined by an equation system, we might not have enough information to do the order computation correctly. Only when a coefficient is needed the computation is triggered and the full computation is never done twice.

The initialization process works in two phases.

1. Build the representation record with some uninitialized data.
2. Right before the first coefficient is accessed, the approximate order is computed and the coefficient stream is initialized.

In fact, we delay not only the order computation until a coefficient is needed, but even the computation of the stream of coefficients is delayed. Since we have to put something in the representation at the place where the coefficient stream is stored, we decided to put the empty stream.

The following function initialize! is an auxiliary function that is called at the beginning of the function zero? (cf. Section 9.2.4) and (through the call to zero? also in the function coefficient) in order to compute an approximate order of the series, to improve a previously computed order, and to set the true order if it can be verified that the approximate order is the true order of the series. In fact, the function is called any time before a coefficient is accessed in order to make sure everything is properly set.

The initialization roughly works as follows.

1. If the order of the series is known, then nothing has to be done since in that case it is assumed that the coefficient stream has already been initialized. In that case also the approximate order must be known. Nothing must be done.
2. If the approximate order is known, then (at the time initialize! is called) also the coefficient stream must already have been initialized. In that case we can try to improve the approximate order and possibly set the true order of the series.
3. If nothing is known, the actual initialization is started. It first computes an approximate order and then initializes the coefficient stream.

   All this is done via the function computeApproximateOrder!(x)⁶ .

   250⟨implementation: FormalPowerSeries: auxiliary functions 249a⟩+≡   (242)  ⊲249b  251 ⊳
   local computeApproximateOrder!(x: %): () == {
           (X.computeApproximateOrder!)(x);
           assert(X.approximateOrder ~= unknown);
   }
   
   Defines:
   computeApproximateOrder!, used in chunks 251, 257, 258, 262–65, and 270a.
   
   With the help of the functions approximateOrder!, new, and set! a recursive approximation of the order can be done. A very important fact is that for the function computeApproximateOrder! it can happen that the approximate order is set to something different than unknown and at the same time the coefficient stream is uninitialized. In particular that happens for recursive definitions of streams like the following.

   s: FormalPowerSeries Integer := new();
   set!(s, 1 + monom * s);

Before we come to the function computeApproximateOrder!, let us deal with the case where an approximate order is known and we need to verify whether the approximate order is, in fact, the true order of the series. The code below does this by testing whether the entry in the position given by the approximate order is really non-zero. If that is the case, it changes the order entry in the representation from unknown to the approximate order. If it is not the case, the approximate order can be increased by 1 and another check is done. According to Convention 2, this iteration can only be done for the finitely many elements of the series that have already been accessed. If this iteration does not recognize the true order of the series, we wait for the next call to initialize! to improve the approximate order further.

We have chosen such a stepwise approach since x might be the zero series coming, for example, from

To check the true order, we must access elements of the given series without violating Convention 2. The computation of the order should in no case start the generator that is stored inside the stream of the series, order computation is, however, allowed to access elements of the stream that are already computed, i. e., for a series x and

Note that, in case we have realized that the series is the zero series, the order and the approximate order have been set to infinity. Thus if we know that the order is unknown then we also know that the approximate order is not infinity.

To recognize the zero series is only possible if we detect that the underlying stream is constant. If that is the case and the last computed value is 0, then we know we have the zero series, since we only run the following code if all values at entries less than the current approximate order are 0.

9.2.3 Computation of an Approximate Order

Let us describe how to compute an approximate order if it has not yet been done.

Our representation data structure (see Section 9.2.1) contains an entry

Let us now describe functions that could be stored in the representation data structure at computeApproximateOrder!. We allow the following functions.

doNothing:

The function does nothing at all. It is a dummy function for cases where an (approximate) order is known at creation time of the series.

uninitialized:

The function is an auxiliary function for the definition of an uninitialized power series through the function new. This function raises an exception when called.

approximateOrder!:

This function (or rather these functions, since there is a nullary, unary, and binary version) computes a new approximate order from approximate orders of its arguments. It should be understood as a wrapper function around the functions such as + and * from SeriesOrder which takes care of recursively defined series.

For some series there is no need to do an order computation at all, since the order is already known at creation time. Examples are given by the implementation of the series 0, 1, monom, and term in Section 9.2.5.

Now we consider the complicated part of the order computation of the function initialize!, namely the function approximateOrder!. There is a nullary, unary, and binary version of that function. Since their implementation is very similar, we only describe the binary version.

This function computes a new approximate order from approximate orders of its arguments. It should be understood as a wrapper function around the functions such as + and * from SeriesOrder which takes care of recursively defined series. Functions such as + and * appear as the argument newOrder in the function declaration below. For understanding of how the function approximateOrder! is used, look, for example, into the definition of + in Section 9.2.8 and at the implementation of new.

For some series we can compute the approximate order according to equations (90) and (91). That holds in particular for the sum and product of series, cf. Sections 9.2.8 and 9.2.11, respectively.

The basic idea for approximateOrder! is that initially it sets all unknown approximate orders (of series involved in the definition of the series in question) to infinity and then (according to the structure of the equation that defines the series) tries to improve that initial guess by drawing conclusions from the guess and equations such as given by (90) and (91) until a stabilized situation is achieved.

We should add a note here about the fact that approximateOrder! does not only compute an approximate order, but (in case at invocation time the approximate order was unknown) it also initializes the coefficient stream. Thus, if the coefficient stream is known to be initialized, then there is no need to do the computation of the approximate order again. The follwing are invariants of approximateOrder!.

T.approximateOrder = unknown	not initialized? t	(95)
T.approximateOrder = unknown	T.order = unknown	(96)

We have a similar function for operations that just need one argument.

And finally, we have a version where we assume that the computation of the approximate order is given by some function that does not involve (through recursion) the approximat order or t.

Note that through the following function we only initialize the data structure of x, but do not actually compute any coefficient in accordance with Convention 2.

The function setApproximateOrder! returns true if the approximate order has been changed and false otherwise. It sets the approximateOrderChanged? entry in the representation of its first argument to this return value.

9.2.4 Zero Recognition

There are cases where we can tell whether an infinite series is zero.

1. The series is explicitly created as the zero series. Then it is the constant stream consisting of entries that are all 0 and the order is explicitly set to infinity.
2. The series was computed from other series and after computing the order, it still is infinity. That happens, for example, if two zero series are added or a zero series is multiplied by another series.

Note that we fail to recognize, for example, that a sum of an infinite series and its negation is zero. The function zero? is only a partial zero test.

9.2.5 Series Constructors

The simplest way to create a series is by giving an explicit stream s or a generator g. Since no other information is given, the only reasonable guess is that the approximate order is zero. See Section 9.2.1 for the fields in the representation.

Note that the function initialize! takes care of improving the approximate order so we do not need to do anything to compute an approximate order. It is for this reason that here and for the following few cases the function doNothing is the right choice.

Next let us define the the constant series 0, 1, monom, and term. The order of those series is known in advance. Thus we can use a special auxiliary function new to shorten the code. See Section 9.2.1 for the fields in the representation.

The function new is used for recursive definitions in conjunction with set! below. Both functions are described in FormalPowerSeriesCategory. Actually, it is completely irrelevant what is put into the data structure, because before any stream that is created by new is used it must be filled with proper data by using the set! function.

However, instead of using doNothing, we are a bit more careful to signal an error if the (uninitialized) stream created by new is accidentially asked to reveal coefficients.

The function set! must always be in accordance with the actual representation, see Section 9.2.1.

9.2.6 Series Selector Functions

For the ordinary generating series

(97)

Note that the computation of the order and the approximate order has to obey Convention 2. Thus, we can only check the coefficients that have already been computed. This is taken care of by the function initialize!.

9.2.7 Creating New Series for Recursive Use

Convention 2 forbids to do any costly computation. In order to prevent computations from happening, we create a new series by giving appropriate functions as arguments which encode how the coefficients of the new series are computed. Additionally, we also require a function that returns an approximate order from the given approximate order(s).

There is a nullary, univariate and a bivariate version. The univariate version is used for univariate operations like, for example, differentiate, integrate, and exponentiate. The bivariate version is invoked for +, *, and compose. For use of the nullary version see the implementation of coerce in CycleIndexSeries.

Note that the functions approximateOrder! just forms a function closure, but does not actually compute any order during the call to one of the following functions.

The macros NEW1 and NEW2 are only relevant for tracing the computation.

Let us start with the binary version.

The unary version is very similar.

The nullary version works in a similar fashion, too.

All three versions above use the following function to build the data structure.

9.2.8 Series Addition

According to the example code given in Section 9.2, we must be very careful while adding two series. With a series definition of the form s = x + s², the computation of a coefficient should only be done if the memory has been reserved for the data structure. Similarly, the computation of an approximate order has to be delayed until all the data structures (of the series that are involved) are created. For this reason the addition operation of series cannot check for zero of one of its arguments at creation time, since zero? starts a computation of an approximate order.

The last two arguments of new give a way to compute the coefficients of x + y and an approximate order from the orders of x and y.

Generating the coefficients of a sum of two series is a simple task. The third parameter give a lower approximation on the order of the series.

The following code takes eventually constant streams into account. In other words, for series with finite support we do not produce much overhead.