Implementation in ScaLAPACK of Divide-and-Conquer Algorithms forBanded and Tridiagonal Linear Systems
Andy Cleary, Jack J. Dongarra · 1997
Described here are the design and implementation of a family of algorithms for a variety of classes of narrowly banded linear systems. The classes of matrices include symmetric and positive definite, nonsymmetric but diagonally dominant, and general nonsymmetric; and, all these types are addressed for both general band and tridiagonal matrices. The family of algorithms captures the general flavor of existing divide-and-conquer algorithms for banded matrices in that they have three distinct phases, the first and last of which are completely parallel, and the second of which is the parallel bottleneck. The algorithms have been modified so that they have the desirable property that they are the same mathematically as existing factorizations (Cholesky, Gaussian elimination) of suitably reordered matrices. This approach represents a departure in the nonsymmetric case from existing methods, but has the practical benefits of a smaller and more easily handled reduced system. All codes implemen...