scientific article; zbMATH DE number 3915502
[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).
- Parallelism and fast solution of linear systems
- Parallel conjugate gradient-like algorithms for solving sparse nonsymmetric linear systems on a vector multiprocessor
- scientific article; zbMATH DE number 3917546
- Scalable iterative solution of sparse linear systems
- The behavior of conjugate gradient algorithms on a multivector processor with a hierarchical memory
- Algorithms and experiments for structural mechanics on high-performance architectures
- Highly concurrent algorithm for the solution of \(\rho\)-Toeplitz system of equations
- Concurrent cooperating solvers over reals
- The numerical stability analysis of pipelined conjugate gradient methods: historical context and methodology
- On the cost of iterative computations
- Predict-and-Recompute Conjugate Gradient Variants
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)