×

The efficient parallel iterative solution of large sparse linear systems. (English) Zbl 0797.65035

George, Alan (ed.) et al., Graph theory and sparse matrix computation. Proceedings of a workshop that was an integral part of the 1991-92 IMA program on “Applied linear algebra”, Minneapolis, MN (USA). New York: Springer-Verlag. IMA Vol. Math. Appl. 56, 229-245 (1993).
The authors propose a new approach to the iterative solution of sparse linear systems on a MIMD machine in a manner that ensures scalable performance (i.e. that for fixed problem size per processor, the performance per processor is essentially independent of the number of processors used). Central to the method is a reordering of the matrix based on a coloring of the symmetric graph corresponding to the nonzero structure of the matrix.
To determine this ordering, the authors use (alternatively) two recently developed graph coloring heuristics suitable for asynchronous parallel computers, based on Monte Carlo steps for which expected running time is known. The first one, a synchronous PRAM heuristics is developed by M. Luby [SIAM J. Comput. 15, 1036-1053 (1986; Zbl 0619.68058)]. The second one, an asynchronous heuristic was recently presented by the authors [SIAM J. Sci. Comput. 14, No. 3, 654-669 (1993; Zbl 0772.68046)].
The authors present several possible graph reductions that can be employed to greatly improve the performance of an implementation on high- performance RISC processors, including the clique partitions that allow for the use of high-level Basic linear Algebra Subprograms (BLAS) in the software.
They also consider a general framework that can incorporate these ideas into efficient triangular systems solvers. The implementations considered are standard general-purpose iterative methods, for example conjugate gradient preconditioned with an incomplete matrix factorization.
Finally, some experimental results for two large-scale applications are presented (a piezoelectric crystal finite element modeling problem and a nonlinear optimization problem to determine minimum energy configuration of a three-dimensional superconductor model).
For the entire collection see [Zbl 0785.00030].
Reviewer: S.Zabek (Lublin)

MSC:

65F10 Iterative numerical methods for linear systems
65F50 Computational methods for sparse matrices
65Y05 Parallel numerical computation
65Y20 Complexity and performance of numerical algorithms
68R10 Graph theory (including graph drawing) in computer science
05C15 Coloring of graphs and hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
05C90 Applications of graph theory
PDFBibTeX XMLCite