UNITED STATES
A Parallel implementation of Gram-Schmidt Algorithm for Dense Linear System of Equations
|
10.5120/927-1079 |
Mohammad Taeibi-Rahni, Bahman Mehri and Roholah S Ghodsi. Article: A Parallel implementation of Gram-Schmidt Algorithm for Dense Linear System of Equations. International Journal of Computer Applications 5(7):16–20, August 2010. Published By Foundation of Computer Science. BibTeX
@article{key:article,
author = {Mohammad Taeibi-Rahni and Bahman Mehri and S. Roholah Ghodsi},
title = {Article: A Parallel implementation of Gram-Schmidt Algorithm for Dense Linear System of Equations},
journal = {International Journal of Computer Applications},
year = {2010},
volume = {5},
number = {7},
pages = {16--20},
month = {August},
note = {Published By Foundation of Computer Science}
}
Abstract
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 MIMD 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.
Reference
- Demmel, J. 1995. LAPACK Users' Guide. Society for Industrial and Applied Mathematic, 2nd Sub edition.
- Blackford, L.S., Choi, J., Cleary, A., DAzevedo, E., Demmel, J., Dhillon, I., Dongarra, J., Hammarling, S., Henry, G., Petitet, A., Stanley, K., Walker, D., and Whaley, R.C. 1987. ScaLAPACK user's guide. Society for Industrial Mathematics.
- Körfgen, B., Gutheil, I. 2006. Parallel Linear Algebra Methods. Comp. Nanoscience: Do It Yourself, NIC Series, Vol.31, 507-522.
- Heller, D. 1978. A Survey of Parallel Algorithms in Numerical Linear Algebra. SIAM Review, Vol.20, No.4, 740-777.
- Saad, Y. 2003. Iterative Methods for Sparse Linear Systems. SIAM press, Philadelphia, 2nd edition.
- Fernando, G., Tinetti, D., Giusti, A. 2004. Parallel Linear Algebra on Clusters. 3rd International workshop on Parallel Matrix Algorithms and Applications (PMAA'04), CIRM, Marseille, France.
- Wilkinson, J.H., and Reinsch, C. 1986. Handbook for Automatic Computation. Vol. 2: Linear Algebra. Springer press, Berlin.
- Dunn, I.N., and Meyer, G.L. 2002. QR factorization for shared memory and message passing, Parallel Comp. Vol.28, No.11, 1507–1530.
- Trefethen, L.N., and Bau, D. 1997. Numerical Linear Algebra. SIAM press, Philadelphia.
- Meyer, C.D. 2000. Matrix Analysis and Applied Linear Algebra. SIAM, Philadelphia.
- Wittwer, T. 2006. An Introduction to Parallel Programming. VSSD uitgeverij, Netherlands.
- Snir, M., and Gropp, W. 1998. MPI: the Complete Reference. The MIT Press, Cambridge, 2nd edition.
- Hogben, L. 2006. Handbook of Linear Algebra (Discrete Mathematics and its Application), Chapman & Hall/CRC, Boca Raton, 1st edition.
- Golub, G.H., and Van Loan, C.F. 1996. Matrix Computations. The Johns Hopkins University Press, Maryland, 3rd edition.
- Lioen, W.M., and Winter, D.T. 1992. Solving Large Dense Systems of Linear Equations on Systems with Virtual Memory and with Cache. Applied Numerical Mathematics, Vol.10, No.1, 73-85.
