Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published January 1, 1982 | public
Report Open

Concurrent Algorithms for the Conjugate Gradient Method

Abstract

A few concurrent algorithms for the basic conjugate gradient method is devised and discussed. Most of the algorithms have a topology that is naturally determined by characteristic dimensions of the system and the operations of each step of the conjugate gradient method. The topologies map well onto buildable structures of sparsely interconnected processors while preserving unit communication distance. The topology of the algorithms are: 1) A binary tree 2) A composition of a binary tree and a ring the nodes of which forms the leaves of the tree. 3 ) A linear array with some additional processing elements. It is also discussed how these algorithms maps onto Boolean n-cubes. The algorithms all have the property that a communication operation is associated with each computation. No claim is made as to the optimality from a space-time complexity point of the algorithms presented here. However, the processor utilization for some algorithms and topologies are close to 100% and the space*time complexity of those algorithms are of the same order as the arithmetic complexity of common sequential machine algorithms.

Files

5040_TR_82.pdf
Files (4.5 MB)
Name Size Download all
md5:4f13c8100cb8d8ebca57567282d3e294
2.5 MB Download
md5:ccfc7f3bf80423ed4054a394eb5ca484
2.1 MB Preview Download

Additional details

Created:
August 19, 2023
Modified:
December 22, 2023