Linsolv

Linsolv is a linear equation solver, and a typical example of a parallel symbolic program. It uses the multiple homomorphic images approach which is often used in computer algebra algorithms [Lauer, 1982]: first the elements of the input matrix and vector are mapped from Z into several images Z_p (where each p is a prime number); then the system is solved in each of these images, and finally the overall result is constructed by combining these solutions using the Chinese Remainder Algorithm. This divide-and-conquer structure is depicted by Figure .

Detailed Structure of Lolita

Strategic code for the matrix determinant part of the solver is given in Section * (the whole algorithm is discussed in [Loidl et al., 1995]). Precise control of the dynamic behaviour is required at two critical places in the program. This behaviour can be described by combining generic strategies.

• The algorithm is described in terms of an infinite list of all solutions in the homomorphic images. An initial segment of the list is computed in parallel, based on an educated guess as to how many homomorphic solutions are needed. Depending on the solutions in the initial segment, a small number of additional solutions are then computed.
• The algorithm only computes the solutions that can actually be used in the combination step. This is achieved by initially only evaluating the first two elements of the result list, then checking if the result is useful and if so computing the remainder.