Talks

In their seminal 1952 paper on the conjugate gradient (CG) method Hestenes and Stiefel pointed out that their method, which is applicable to linear systems of equations with symmetric positive definite matrix only, is closely related to certain orthogonal polynomials, the corresponding Gauss quadrature formulas, certain continued fractions, and their convergents (or `partial sums'). The latter can be seen to be Padé approximants of a function that involves the resolvent of the matrix.

Around the same time, in 1950 and 1952, Cornelius Lanczos published two related articles, of which the second one introduced a precursor of the biconjugate gradient (BCG or BiCG) method, which generalizes CG to the case of a nonsymmetric system. Here, the residual polynomials are formal orthogonal polynomials only, but the connections to continued fractions and Padé approximants persist. Moreover, there is a relation to the qd algorithm of Rutishauser (1954). The understanding of all these connections became probably the key to Rutishauser's discovery of the LR algorithm (1955, 1958), which was later enhanced by John G.F. Francis to the ubiquitous QR algorithm (1961/62).

The IDR(s) method is a family of fast algorithms for iteratively solving large nonsymmetric linear systems. In the talk we will discuss an IDR(s) variant that is specifically tuned for parallel and grid computing. In particular in grid computing the inner product is a bottleneck operation. We will discuss three techniques that we have used to alleviate this bottleneck in IDR(s). Firstly, the efficient and stable IDR(s)-biortho method is reformulated in such a way that it has a single global synchronisation point per iteration step. Secondly, the so-called test matrix is chosen so that the work, communication, and storage involving this matrix is minimised in multi-cluster environments. Finally, a methodology is presented for a-priori estimation of the optimal value of s using only problem and machine--based parameters. We will also discuss a preconditioned version of IDR(s) that is particularly suited for grid computing. We will illustrate our results with numerical experiments on the DAS--3 Grid computer, which consists of five cluster computers located at geographically separated places in the Netherlands.

This is joint work with Tijmen Collignon.