Seminar Details:

LANS Informal Seminar
"Communication Reducing Data Models and Asynchronous Algorithms"

DATE: December 2, 2011

TIME: 10:30:00 - 11:30:00
SPEAKER: Mark F. Adams, Columbia University
LOCATION: Building 240, 4301, Argonne National Laboratory

This talk will consider multigrid methods in the context of the scales of problems and computer architectures that are foreseen in the next 5-10 years. This includes issues of communication reducing data models and asynchronous algorithms. I will start by establishing what is probably a lower bound on work and memory complexity, and perhaps data movement complexity, for solving the algebraic equations that arise from discretized elliptic PDEs. Rigorous proofs will be omitted but an analysis is presented that suggests practical methods to extend this "textbook multigrid efficiency" to operators where rigorous theory is silent. An example of fast solvers for fully implicit eight field resistive compressible magnetohydrodynamics is presented. Algebraic multigrid (AMG) methods are introduced and application from science and industry are presented, including a Gordon Bell prize winning application from 2004. Parallel data models and asynchronous algorithms for Gauss-Seidel are presented that exploit special characteristics of discretized PDE graphs and are much faster than generic coloring approaches. Though Gauss-Seidel smoothers are largely eclipsed in practice by additive methods they are potentially useful for very unsymmetric operators and these algorithms lead to ideas that are useful in optimizing performance of coarse grid work in large scale multigrid solves. These ideas have been used in the previous work presented here and are used in recent work in developing unstructured geometric and AMG methods as native PETSc solvers using PETSc's common parallel primitives. Strong and weak scaling results are presented for a 3D elasticity model problem and a unstructured FEM 2D Poisson solver on an ITER mesh from the fusion gyrokinetic PIC code XGC1.


Please send questions or suggestions to Charlotte Haley: haley at anl dot gov.