Research ArticleOpen AccessGoogle Scholar indexed
Parallel Implementation of the Gauss-Seidel Algorithm on <i>k</i>-Ary <i>n</i>-Cube Machine
Jordan University of Science and Technology, Department of Mathematics and Statistics, Irbid, Jordan
- 1 Jordan University of Science and Technology, Department of Mathematics and Statistics, Irbid, Jordan
Applied Mathematics·Volume 04 (2013)·Pages 177–182·Published 30 January 2013·DOI10.4236/am.2013.41A028
Copy link · social · email
Abstract
In this paper, we present parallel implementation of the Gauss-Seidel (GS) iterative algorithm for the solution of linear systems of equations on a k -ary n -cube parallel machine using Open MPI as a parallel programming environment. The proposed algorithm is of O ( N 3 / k n ) computational complexity and uses O ( nN ) communication time to decompose a matrix of order N on the a k -ary n -cube provided N ≥ k n- 1 . The incurred communication time is better than the best known results for hypercube, O ( N log n !), and the mesh, O ( N n !), each with approximately n ! nodes. The numerical results show that speedup improves as number of processors increased and the proposed algorithm has approximately 80% parallel efficiency.
KeywordsCluster ComputingParallel ComputingLinear Systems of EquationsDirect MethodsIterative Methods
- L. Adams and D. Xie, “New Parallel SOR Method by Domain Partitioning,” SIAM Journal on Scientific Computing, Vol. 20, No. 22, 1999, pp. 2261-2281.
- M. F. Adams. “A Distributed Memory Unstructured Gauss-Seidel Algorithm for Multigrid Smoothers,” Proceedings of 2001 ACM/IEEE Conference on Supercomputing, Donver, 10-16 November 2001, p. 4.
- C. J. Hu, J. L. Zang, J. Wang, J. J. Li and L. Ding, “A New Parallel Gauss-Seidel Method by Iterative Space Alternate Tiling,” 16th International Conference on Parallel Architecture and Compilation Techniques, Brasov, 15-19 September 2007, p. 410.
- M. Murugan, S. Sridhar and Sunil Arvindam “A Parallel Implementation of the Gauss-Seidel Method on the Flosolver,” Technical Report, National Aeronautical Labaratory, Bangalor, 24 July 2006.
- L. Olszewski. “A Timing Comparison of the Conjugate Gradient and Gauss-Siedel Parallel Algorithms in a One-Dimensional Flow Equation Using PVM,” Proceedings of the 33rd Annual on Southeast Regional Conference, Clemson, March 1995, pp. 205-212.
- U. Thongkrajay and T. Kulworawanichpong. “Convergence Improvement of Gauss-Seidel Power Flow Solution Using Load Transfer Technique,” Proceedings of Modelling, Identification, and Control, Innsbruck, 11-13 February 2008,
- D. Wallin, H. Lof, E. Hagersten and S. Holmgren, “Multigrid and Gauss-Seidel Smoothers Revisited: Parallelization on Chip Multiprocessors,” Proceedings of ICS06 Conference, Cairns, 28-30 June 2006.
- T. Kim and C.-O. Lee. “A Parallel Gauss-Seidel Method Using NR Data Flow Ordering,” Journal of Applied Mathematics and Computation, Vol. 99, No. 2-3, 1999, pp. 209-220. doi:10.1016/S0096-3003(98)00008-3
- M. Adams, M. Brezina, J. Hu and R. Tuminara, “Parallel Multigrid Smoothing: Polynomial versus Gauass-Seidel,” Journal of Computational Physics, Vol. 188, No. 2, 2003, pp. 593-610.
- G. Fox, M. Johnson, G. Lyzanga, S. Otto, J. Salmon and D. Walker, “Solving Problems on Concurrent Processors,” Printice Hall, Upper Saddle River, 1988.
- G. Golub and J. M. Ortega, “Scintific Computing with an Introduction to Parallel Computing,” Academic Press, Boston, 1993.
- R. A. Saleh, K. A. Gallivan, M. Chang, I. N. Hajj, D. Smart and T. N. Trich, “Parallel Circuit Simulation on Supercomputers,” Proceedings of the IEEE, Vol. 77, No. 12, 1989, pp. 1915-1930. doi:10.1109/5.48832
- Y. Wallch, “Calculations and Programs for Power System Networks,” Printice Hall, Upper Saddle River, 1986.