Jones, Mark T.; Plassmann, Paul E. 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) Cited in 1 Document 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 Keywords:sparse matrices; iterative methods; preconditioned conjugate gradients; parallel algorithms; MIMD computers; graph coloring heuristics; sparse linear systems; performance; reordering; parallel computers; graph reductions; experimental results; large-scale applications; piezoelectric crystal; superconductor Citations:Zbl 0619.68058; Zbl 0772.68046 PDFBibTeX XMLCite \textit{M. T. Jones} and \textit{P. E. Plassmann}, IMA Vol. Math. Appl. 56, 229--245 (1993; Zbl 0797.65035)