A Block Projection Method for Sparse Matrices
Mario Arioli, Iain Duff, Joseph Noailles, Daniel Ruiz · SIAM Journal on Scientific and Statistical Computing · 1992
A block version of Cimmino’s algorithm for solving general sets of consistent sparse linear equations is described. The case of matrices in block tridiagonal form is emphasized because it is assumed that the general case can be reduced to this form by permutations. It is shown how the basic method can be accelerated by using the conjugate gradient (CG) algorithm. This acceleration is very dependent on a partitioning of the original system and several possible partitionings are discussed. Underdetermined systems corresponding to the subproblems of the partitioned system are solved using the Harwell sparse symmetric indefinite solver MA27 on an augmented system. These systems are independent and can be solved in parallel. An analysis of the iteration matrix for the conjugate gradient acceleration leads to the consideration of rather unusual and novel scalings of the matrix that alter the spectrum of the iteration matrix to reduce the number of CG iterations. The various aspects of this algorithm have been tested by runs on an eight-processor Alliant FX/80 on four block tridiagonal systems, two from fluid dynamics simulations and two from the literature. The effect of partitioning and scaling on the number of iterations and overall elapsed time for solution is studied. In all cases, an accurate solution with rapid convergence can be obtained.