Scientific Research

An Academic Publisher

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

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.

Share and Cite:

*k*-Ary

*n*-Cube Machine,"

*Applied Mathematics*, Vol. 4 No. 1A, 2013, pp. 177-182. doi: 10.4236/am.2013.41A028.

Conflicts of Interest

The authors declare no conflicts of interest.

[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 |

Copyright © 2020 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.