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

Show more

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

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