CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

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

by Mohammad Taeibi-Rahni, Bahman Mehri, S. Roholah Ghodsi
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 5 - Number 7
Year of Publication: 2010
Authors: Mohammad Taeibi-Rahni, Bahman Mehri, S. Roholah Ghodsi
10.5120/927-1079

Mohammad Taeibi-Rahni, Bahman Mehri, S. Roholah Ghodsi . A Parallel implementation of Gram-Schmidt Algorithm for Dense Linear System of Equations. International Journal of Computer Applications. 5, 7 ( August 2010), 16-20. DOI=10.5120/927-1079

@article{ 10.5120/927-1079,
author = { Mohammad Taeibi-Rahni, Bahman Mehri, S. Roholah Ghodsi },
title = { A Parallel implementation of Gram-Schmidt Algorithm for Dense Linear System of Equations },
journal = { International Journal of Computer Applications },
issue_date = { August 2010 },
volume = { 5 },
number = { 7 },
month = { August },
year = { 2010 },
issn = { 0975-8887 },
pages = { 16-20 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume5/number7/927-1079/ },
doi = { 10.5120/927-1079 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T19:53:37.676765+05:30
%A Mohammad Taeibi-Rahni
%A Bahman Mehri
%A S. Roholah Ghodsi
%T A Parallel implementation of Gram-Schmidt Algorithm for Dense Linear System of Equations
%J International Journal of Computer Applications
%@ 0975-8887
%V 5
%N 7
%P 16-20
%D 2010
%I Foundation of Computer Science (FCS), NY, USA
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.

References
  1. Demmel, J. 1995. LAPACK Users' Guide. Society for Industrial and Applied Mathematic, 2nd Sub edition.
  2. 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.
  3. Körfgen, B., Gutheil, I. 2006. Parallel Linear Algebra Methods. Comp. Nanoscience: Do It Yourself, NIC Series, Vol.31, 507-522.
  4. Heller, D. 1978. A Survey of Parallel Algorithms in Numerical Linear Algebra. SIAM Review, Vol.20, No.4, 740-777.
  5. Saad, Y. 2003. Iterative Methods for Sparse Linear Systems. SIAM press, Philadelphia, 2nd edition.
  6. 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.
  7. Wilkinson, J.H., and Reinsch, C. 1986. Handbook for Automatic Computation. Vol. 2: Linear Algebra. Springer press, Berlin.
  8. Dunn, I.N., and Meyer, G.L. 2002. QR factorization for shared memory and message passing, Parallel Comp. Vol.28, No.11, 1507–1530.
  9. Trefethen, L.N., and Bau, D. 1997. Numerical Linear Algebra. SIAM press, Philadelphia.
  10. Meyer, C.D. 2000. Matrix Analysis and Applied Linear Algebra. SIAM, Philadelphia.
  11. Wittwer, T. 2006. An Introduction to Parallel Programming. VSSD uitgeverij, Netherlands.
  12. Snir, M., and Gropp, W. 1998. MPI: the Complete Reference. The MIT Press, Cambridge, 2nd edition.
  13. Hogben, L. 2006. Handbook of Linear Algebra (Discrete Mathematics and its Application), Chapman & Hall/CRC, Boca Raton, 1st edition.
  14. Golub, G.H., and Van Loan, C.F. 1996. Matrix Computations. The Johns Hopkins University Press, Maryland, 3rd edition.
  15. 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.
Index Terms

Computer Science
Information Sciences

Keywords

Gram-Schmidt Method QR Factorization Parallel Processing Dense Matrix Linear system of equations

Powered by PhDFocusTM