Component averaging: An efficient iterative parallel algorithm for large and sparse unstructured problems

Component averaging (CAV) is introduced as a new iterative parallel techniq ue suitable for large and sparse unstructured systems of linear equations. It simultaneously projects the current iterate onto all the system's hyperp lanes, and is thus inherently parallel. However, instead of orthogonal proj ections and scalar weights (as used, for example, in Cimmino's method), it uses oblique projections and diagonal weighting matrices, with weights rela ted to the sparsity of the system matrix. These features provide for a prac tical convergence rate which approaches that of algebraic reconstruction te chnique (ART) (Kaczmarz's row-action algorithm)- even on a single processor . Furthermore, the new algorithm also converges in the inconsistent case. A proof of convergence is provided for unit relaxation, and the fast converg ence is demonstrated on image reconstruction problems of the Herman head ph antom obtained within the SNARK93 image reconstruction software package. Bo th reconstructed images and convergence plots are presented. The practical consequences of the new technique are far reaching for real-world problems in which iterative algorithms are used for solving large, sparse, unstructu red and often inconsistent systems of linear equations. (C) 2001 Elsevier S cience B.V. All rights reserved.