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(N3/kn) computational complexity and uses O(nN) communication time to decompose a matrix of order N on the a k-ary n-cube provided N ≥ kn-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.
 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.
 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
 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
 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.
 James, “Demmel Home Page, Applications of Parallel Computers,” 1999. www.cs.brekeley.edu/~demmel/
 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.
 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.