A distributed memory unstructured gauss-seidel algorithm for multigrid smoothers

ABSTRACT

Gauss-Seidel is a popular multigrid smoother as it is provably optimal on structured grids and exhibits superior performance on unstructured grids. Gauss-Seidel is not used to our knowledge on distributed memory machines as it is not obvious how to parallelize it effectively. We, among others, have found that Krylov solvers preconditioned with Jacobi, block Jacobi or overlapped Schwarz are effective on unstructured problems. Gauss-Seidel does however have some attractive properties, namely: fast convergence, no global communication (ie, no dot products) and fewer flops per iteration as one can incorporate an initial guess naturally. This paper discusses an algorithm for parallelizing Gauss-Seidel for distributed memory computers for use as a multigrid smoother and compares its performance with preconditioned conjugate gradients on unstructured linear elasticity problems with up to 76 million degrees of freedom.

REFERENCES

• 1: Loyce M. Adams and Harry F. Jordan. Is SOR color-blind? SIAM J. Sci. Statist. Comput., 7(2):490-506, 1986.
• 2: M. F. Adams. A parallel maximal independent set algorithm. In Proceedings 5th copper mountain conference on iterative methods, 1998.
• 3: Mark F. Adams, Evaluation of Three Unstructured Multigrid Methods on 3D Finite Element, University of California at Berkeley, Berkeley, CA, 2000
• 4: M. F. Adams. Parallel multigrid solvers for 3D unstructured finite element problems in large deformation elasticity and plasticity. International Journal for Numerical Methods in Engineering, 48(8):1241-1262, 2000.
• 5: S. Balay, W. D. Gropp, L. C. McInnes, and B. F. Smith. PETSc 2.0 users manual. Technical report, Argonne National Laboratory, 1996.
• 6: V. E. Bulgakov and G. Kuhn. High-performance multilevel iterative aggregation solver for large finite-element structural analysis problems. International Journal for Numerical Methods in Engineering, 38:3529-3544, 1995.
• 7: James W. Demmel, Applied numerical linear algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
• 8: C. C. Douglas, J. Hu, M. Iskandarani, M. Kowarschik, U. Rüde, and C. Weiss. Maximizing cache memory usage for multigrid algorithms. In Multiphase Flows and Transport in Porous Media: State of the Art, pages 124-137. Springer, Berlin, 2000.
• 9: FEAP. www.ce.berkeley.edu/~rlt.
• 10: Y. T. Feng, D Peric, and D. R. J. Owen. A non-nested multi-grid method for solving linear and nonlinear solid mechanics problems. Compute. Meth. Mech. Engng., 144:307-325, 1997.
• 11: J. Fish, V. Belsky, and S. Gomma. Unstructured multigrid method for shells. International Journal for Numerical Methods in Engineering, 39:1181-1197, 1996.
• 12: Van Emden Henson , Ulrike Meier Yang, BoomerAMG: a parallel algebraic multigrid solver and preconditioner, Applied Numerical Mathematics, v.41 n.1, p.155-177, April 2002 [doi>10.1016/S0168-9274(01)00115-5]
• 13: http://www.pallas.de/pages/vampir.htm. Vampir 2.5 --- visualization and analysis of mpi programs.
• 14: George Karypis , Vipin Kumar, Parallel multilevel k-way partitioning scheme for irregular graphs, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.35-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States [doi>10.1145/369028.369103]
• 15: MGNet. www.mgnet.org.
• 16: Prometheus. www.cs.berkeley.edu/~madams.
• 17: B. Smith, P. Bjorstad, and W. Gropp. Domain Decomposition. Cambridge University Press, 1996.
• 18: P. Vanek, J. Mandel, and M. Brezina. Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems. In 7th Copper Mountain Conference on Multigrid Methods, 1995.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Distributed memories

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures
          Subjects: Distributed architectures

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.8 Partial Differential Equations
          Subjects: Multigrid and multilevel methods

General Terms:
Algorithms, Design, Experimentation

Keywords:
algebraic multigrid, parallel gauss-seidel, parallel graph algorithms, unstructured multigrid