No label defined (Q3690949)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3915502
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3915502 |
Statements
1984
0 references
parallel computing
0 references
VLSI algorithms
0 references
systolic architectures
0 references
Gaussian elimination
0 references
Cholesky
0 references
Crout
0 references
Doolittle
0 references
Householder
0 references
Givens
0 references
conjugate gradient method
0 references
binary tree algorithm
0 references
Preconditioning
0 references
0.8491712212562561
0 references
0.8228136897087097
0 references
0.8050172924995422
0 references
[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).
0 references