โ Scribed by P. Tervola; W. Yeung
No coin nor oath required. For personal study only.
Tervola, P. and W. Yeung, Parallel Jacobi algorithm for matrix diagonalisation on transputer networks, Parallel Computing 17 (1991) 155-163 We present a parallel algorithm for the determination of the eigenvalues and eigenvectors of a real symmetric matrix. The algorithm allocates a certain number of columns to each of the transputers. The Jacobi cycle of annihilating the off diagonal elements consists of letting all the transputers perform Jacobi rotations concurrently, correcting for overlapping transformations and shuffling the sets of columns among the transputers. We develop formulae for the speedup and efficiency. Using Occam 2 we implement the algorithm on several transputer networks and compare the actual timings with our calculated results. We discuss the merits of this particular implementation.
๐ SIMILAR VOLUMES
Huang, Y. and Y Paker, A parallel FFT algorithm for transputer networks, Parallel Computing 17 (1991) 895-906 This paper presents a parallel FFT algorithm suitable for MIMD machines\_ It has the properties of uniform granularity, the dominance of computation, and suitability to large data matrices T
The implementation of three parallel sorting algorithms, namely binary sort, odd-even transposition sort and bitonic sort, on a network of transputers is analysedin the paper. The variation in the performance of these algorithms as the number of processors and sort size are changed is investigated.
In this paper we give evidence to show that in one-sided Jacobi SVD computation the sorting of column norms in each sweep is very important. An efficient parallel ring Jacobi ordering for computing singular value decomposition is described. This ordering can generate n(n -1)/2 different index pairs