Mathematical Problems in Engineering
Volume 2010 (2010), Article ID 268093, 17 pages
Research Article

A Novel Parallel Algorithm Based on the Gram-Schmidt Method for Tridiagonal Linear Systems of Equations

Mechanical and Aerospace Engineering Department, Science and Research Branch, Islamic Azad University (IAU), Tehran 1477-893855, Iran

Received 8 June 2010; Revised 19 September 2010; Accepted 6 December 2010

Academic Editor: David Chelidze

Copyright © 2010 Seyed Roholah Ghodsi and Mohammad Taeibi-Rahni. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


This paper introduces a new parallel algorithm based on the Gram-Schmidt orthogonalization method. This parallel algorithm can find almost exact solutions of tridiagonal linear systems of equations in an efficient way. The system of equations is partitioned proportional to number of processors, and each partition is solved by a processor with a minimum request from the other partitions' data. The considerable reduction in data communication between processors causes interesting speedup. The relationships between partitions approximately disappear if some columns are switched. Hence, the speed of computation increases, and the computational cost decreases. Consequently, obtained results show that the suggested algorithm is considerably scalable. In addition, this method of partitioning can significantly decrease the computational cost on a single processor and make it possible to solve greater systems of equations. To evaluate the performance of the parallel algorithm, speedup and efficiency are presented. The results reveal that the proposed algorithm is practical and efficient.