Parallel Implementation of the Gauss-Seidel Algorithm on k-Ary n-Cube Machine

Mohammad H. Al-Towaiq

Jordan University of Science and Technology, Department of Mathematics and Statistics, Irbid, Jordan.

DOI: 10.4236/am.2013.41A028                

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³/kⁿ) 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.

Keywords

Cluster Computing; Parallel Computing; Linear Systems of Equations; Direct Methods; Iterative Methods

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	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.
[2]	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.
[3]	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.
[4]	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.
[5]	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.
[6]	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,
[7]	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.
[8]	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
[9]	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.
[10]	G. Fox, M. Johnson, G. Lyzanga, S. Otto, J. Salmon and D. Walker, “Solving Problems on Concurrent Processors,” Printice Hall, Upper Saddle River, 1988.
[11]	G. Golub and J. M. Ortega, “Scintific Computing with an Introduction to Parallel Computing,” Academic Press, Boston, 1993.
[12]	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
[13]	Y. Wallch, “Calculations and Programs for Power System Networks,” Printice Hall, Upper Saddle River, 1986.
[14]	H. Courtecuisse and J. Allard, “Parallel Dense Gauss-Seidel Algorithm on Many-Core Processors,” High Performance Computation Conference (HPCC), Seoul, 25-27 June 2009, pp. 139-147.
[15]	F. Wang and J. Xu, “A Crosswind Block Iterative Method for Convection-Dominated Problems,” SIAM Journal on Scientific Computing, Vol. 21, No. 2, 1999, pp. 620-645. doi:10.1137/S106482759631192X
[16]	J. Grabel, B. Land and P. Uebertholz, “Performance Optimization for the Parallel Gauss-Seidel Smoother,” Proceedings in Applied Mathematics and Mechanics, Vol. 5, No. 1, 2005, pp. 831-832.
[17]	O. Nobuhiko, M. Takeshi, I. Takeshi and S. Masaaki, “A Parallel Block Gauss-Seidel Smoother for Algebraic Multigrid Method in Edge-Element Analysis,” IEE Japan Papers of Technical Meeting on Static Apparatus, Vol. 6, No. 58-61, 63-75, 2006, pp. 55-60.
[18]	P. Kongetira, K. Aingaran and K. Olukotun. “Niagra: A 32-Way Multithreaded SPARC Processor,” IEEE Micro, Vol. 25, No. 2, 2005, pp. 21-29. doi:10.1109/MM.2005.35
[19]	M. Al-Towaiq, “Clustered Gauss-Huard Algorithm for the Solution of Ax = b,” Journal of Applied Mathematics and Computation, Vol. 184, No. 2, 2007, pp. 485-595.
[20]	James, “Demmel Home Page, Applications of Parallel Computers,” 1999. www.cs.brekeley.edu/~demmel/
[21]	W. Lichtenstein and S. L. Johnsson, “Block Cyclic Dense Linear Algebra,”SIAM Journal on Scientific Computing, Vol. 14, No. 6, 1993, pp. 1257-1286. doi:10.1137/0914075
[22]	M. Al-Towaiq, F. Masoud, A. B. Mnaour and K. Day, “An Implementation of a Parallel Iterative Algorithm for the Solution of Large Banded Systems on a Cluster of Workstations,” International Journal of Modeling and Simulation, Vol. 28, No. 4, 2008, pp. 378-386.
[23]	M. Al-Towaiq and H., Al-Aamri, “A Parallel Implementation of GESPP on a Cluster of Silicon Graphics Workstations,” Proceedings of the 9th IEEE International Conference on Parallel and Distributed Systems, Hsinchu, 17-20 December 2002, pp. 226-230.
[24]	K. Day, “Optical Transpose k-Ary n-Cube Networks,” Journal of Systems Architecture, Vol. 50, No. 11, 2004, pp. 697-705. doi:10.1016/j.sysarc.2004.05.002
[25]	K. Day and A. E. Al-Ayyoub, “Fault Diameter of k-Ary n-Cube Networks,” IEEE Transactions on Parallel and Distributed Systems, Vol. 8, No. 9, 1997, pp. 903-907. doi:10.1109/71.615436