Johnsson, Lennart (1982) Concurrent Algorithms for the Conjugate Gradient Method. California Institute of Technology . (Unpublished) http://resolver.caltech.edu/CaltechCSTR:1982.5040-tr-82
Other (Adobe PDF (2MB))
See Usage Policy.
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechCSTR:1982.5040-tr-82
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.
|Item Type:||Report or Paper (Technical Report)|
|Group:||Computer Science Technical Reports|
|Usage Policy:||You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.|
|Deposited By:||Imported from CaltechCSTR|
|Deposited On:||09 Aug 2002|
|Last Modified:||26 Dec 2012 14:12|
Repository Staff Only: item control page