scientific article; zbMATH DE number 3915502

From MaRDI portal
Publication:3690949





[For the entire collection see Zbl 0557.00009.] Highly concurrent architectures, such as systolic architectures, are becoming economically feasible with the rapidly developing VLSI technology. In this paper we survey recent developments in highly concurrent algorithms for the solution of linear systems of equations by Gaussian elimination with or without pivoting, by its symmetric versions according to Cholesky, Crout and Doolittle, and by the numerically stable methods of Householder and Givens. We present concurrent algorithms for the conjugate gradient method, and the preconditioned conjugate gradient method. The computational model assumes that the storage is distributed among the processors. Particular attention is given to the communication cost, and the data structures are chosen such that the communication cost is minimized. Model configurations are one- and two-dimensional meshes, complete binary trees, and hypercubes. It is shown that if the communication is accounted for, then the lower bound complexity of the conjugate gradient method is O(N log N), the same as that of Gaussian elimination with partial pivoting, and Householder transformation. A binary tree algorithm of this complexity is presented. Preconditioning may increase the order of the parallel complexity per iterative step to order O(N).











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3690949)