A Parallel implementation of Gram-Schmidt Algorithm for Dense Linear System of Equations

The linear system of equations with dense coefficient matrix is very common in science and engineering. In this paper, a parallel algorithm based on Gram-Schmidt QR factorization method for the exact solution of dense system of linear equations is presented. Although several parallel approaches have been proposed to solve the system of linear equations until now, the aim of this paper is to show the ability and limitation of this parallel algorithm in comparison with the sequential one. The suggested parallel algorithm is executed on M IM D architecture and distributed memory. In order to specify the efficiency of this algorithm, the amounts of speedup and FLOPs in executions with different size of matrix (from 2000 to 12000 equations) on up to 5 processors are compared together. The results show that the achieved speedup is significant, and also the performance of this practical parallel algorithm increases as the number of equations grows.