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.