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

      0 references
      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
      [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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references