Arioli M., Duff I., Noailles J., Ruiz D. A block projection method for sparse matrices. Internal note IEI-B4-49, 1990. |

Abstract (English) |
We describe a block version of Cimmino's algorithm for solving general sets of consistent sparse linear equations. We emphasize the case of matrices in block tridiagonal form because we assume that the general case can be reduced to this form by permutations. We show how the basic method can be accelerated by using the conjugate gradient algorithm. This acceleration is very dependent on a partitioning of the original system and we discuss several possible partitionings. 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 us to consider rather unusual and novel scalings of the matrix that alter the spectrum of the iteration matrix to reduce the number of CG iterations. Wc have tested the various aspects of our algorithm by runs on an eight processor Alliant FX/80 on four block trėdiagonal systems, two from fluid dynarnics simulations and two from the literaturc. The efTect of panitioning and scaling on the number of ėterations and overall elapsed time for solutiol1 is studied. In al! cases, we can gel an accurate solution with rapid convergence. | |

Subject | Sparse matrices Block iterative methods Projection methods Partitioning Augmented system Parallel processing Block Cimmino method Conjugate gradient preconditioning |

1) Download Document PDF |

Open access Restricted Private