Parallel algorithms for solving linear equations on mimd computers
Swarn P. Kumar · 1982
The objective of this study was to investigate the problem of solving systems of linear algebraic equations on MIMD (Multiple Instruction Multiple Data) parallel computers. Three practical parallel algorithms, two direct and one iterative, are designed and analyzed. Two of them are also implemented. These algorithms are developed for two cases of the coefficient matrix of the linear system: (i) when the matrix is real, nonsingular, and dense and (ii) when the matrix is real, symmetric, and positive definite. For the first case, the method proposed is the parallel fast Givens transformations method. For the second case, the direct methods are the parallel Cholesky decomposition and the parallel Gaussian elimination and the iterative one is the parallel conjugate gradient method. It is shown that for a positive definite matrix the parallel Gaussian elimination is more efficient than the parallel Cholesky decomposition method. The methods are numerically stable and are analyzed for different values of the number of processors. The speedup and efficiency of the parallel algorithms are compared with their serial counterparts. The parallel fast Givens method and the parallel conjugate gradient method are tested on the MIMD computer, the HEP (Heterogeneous Element Processor), manufactured by Denelcor Inc., and the obtained results support our theoretical analysis.