# Presentation: 242702

## Robert D. FalgoutLawrence Livermore National LaboratorySeventh European Multigrid ConferenceHohenwart Forum, GermanyOctober, 2002

**Robert D. Falgout*****Lawrence Livermore National Laboratory*****Seventh European Multigrid Conference*****Hohenwart Forum, Germany******October, 2002***

**Adaptive Algebraic Multigrid**

## Outline

**AMG/AMGe Background**
**The basic Adaptive AMG (*****AdAMG*****) method**
**The “wrong approach” (and *****PCG*****)**
**Based on Ruge-Stüben (*****AdAMG-RS*****)**
**Based on Smoothed Aggregation (*****AdAMG-SA*****)**
**Future work / compatible relaxation**

## AMG Background

**AMG assumes only information about the underlying matrix structure**
**There is no single AMG algorithm**
**AMG automatically coarsens “grids”**

***Accurate characterization of smooth error is crucial***

***algebraically smooth error***

**Notes:**
Remind people of DYNA3D
This is a hot topic

## Good local characterizations of smooth error is key to robust algebraic multigrid

**Traditional AMG uses the following heuristic, based on properties of M-matrices: **smooth error varies slowest in the direction of “large” coefficients
**New heuristic based on multigrid theory:**** **interpolation must be able to reproduce a mode up to the same accuracy as the size of the associated eigenvalue

**Stretched quad example (             ):**
**Direction of smoothest error is not readily apparent**

## AMGe uses local finite element stiffness matrices to characterize smooth error

**AMGe heuristic is based on multigrid theory:**** ***interpolation must be able to reproduce a mode up to the same accuracy as the size of the associated eigenvalue*
**Use local measure to construct AMGe components:**

**Basic method & theory in *****SISC paper*****, 2000**
**Agglomeration approach to appear in *****SISC***
**Element-free variant to appear in *****SISC***

## AMGe uses finite element stiffness matrices to localize new heuristic

**Global measure:**
**Local measure:****where       is a canonical basis vector,        is a row of interpolation, and       is a sum of local stiffness matrices**

## Interpolation is defined by the arg min ofwhere we restrict the structure of iterpolation to “nearest neighbors” by

This is easily computed in practice

**This is easily computed in practice**

**Using local measure to define interpolation**

## Computing interpolation in practice 

**Partition local matrix by *****F***** and *****C*****-pts:**
**Interpolation to point***** i *****is defined by**

## Using local measure to define interp. is equivalent to fitting local eigenmodes 

**Assume the eigen-decomposition:**
**Finding the *****arg min ***** is equivalent to solving the following constrained least-squares problem**

## Adaptive AMG (AdAMG)

## Adaptive AMG employs the idea of: using the method to improve the method

**Main idea:**** **to uncover the slowly-converging error components (the so-called *bad guys*)* *by applying the “current method” to the systemand using them to adapt (improve) the method
**Achi Brandt’s *****Bootstrap AMG***** is an example**
**Notation: Consider solving the system**

## Basic AdAMG cycle (relaxation pass)

**The columns of          are the iteration vectors**
**The columns of          are the bad guys**

**We now have the components of a multigrid method**

## Basic AdAMG cycle (V-cycle pass)

**We can apply the previously constructed MG method to improve the MG method**

**We now have new multigrid components**

## Can imagine many variations for constructing AdAMG methods

**Even the basic cycle could be different**

## Several approaches for defining P

**Prolongation must interpolate well all components not eliminated by relaxation**
**Two basic approaches:**

**Construct bad-guy space rich in all smooth modes, and construct *****P***** using only this space**
***BAMG***** does this**

**Construct bad-guy space rich in only smoothest modes, and construct *****P***** using this space plus additional matrix information**
**Order number-of-kernel-components bad guys**
**Our methods use this approach**

## The “wrong approach” for AdAMG

**Consider the following iterative method**
**With                                , can rewrite as**
**Error propagation is**

## The “wrong approach” for AdAMG

**Consider a 2-level *****V(j,0)***** cycle with error propagation**
**The Setup Algorithm:**

## The “wrong approach” for AdAMG

**Easy to show that        is just an *****A*****-orthogonal projection onto the space**

**This looks like a Krylov space!**
**In fact, it is just *****PCG***** with our baseline iterative method as the preconditioner**

## AdAMG and PCG

**Error propagation for PCG has the form****where         is an *****A*****-orthogonal projection onto**
**But                                                   implies**
**Clear that *****AdAMG***** and *****PCG***** have same basic properties**
**In fact, the “right choice” of initial guesses will produce exactly the same iterates, analytically**

## AdAMG / PCG relationship underscores the true role of the bad guy

**The role of the bad guy is to be a ****representative**** or “****straw man****” for constructing what it means to be locally smooth**
**The key word here is “****locally****”**
**This “wrong approach” example deals with the bad guys globally, and as such, has sub-optimal convergence properties**

## AdAMG-RS

## AdAMG-RS is an adaptive method based on standard Ruge-Stüben heuristics

**In *****AdAMG-RS***** we will generate only ****one bad guy**** to represent the smoothest component (thinking of scalar problems for now)**
**Note that more information is needed in order to construct good interpolation operators**
**e.g., piecewise constant interpolation fits the constant kernel function exactly, but not good**
**use bad guy plus M-matrix assumption**
**We will use an *****Element-free AMGe***** framework to describe this method**
**More about that next...**

## Element-Free AMGe builds local element matrices directly from the global matrix

**Partition local neighborhood about point *****i***** into**** **
**Define an extension map of the form**
**Then, the needed local operators are defined by**

## E-Free AMGe can be used to produce the R-S AMG interpolation formulas

**Let               , the point to which we are interpolating**
**Define the extension map as follows (where *****e***** is any vector and *****j***** is a point in the extension set):**
***RS-AMG***** interpolation is defined by setting the residual at point *****i***** to zero:**

## AdAMG-RS: Deriving interpolation

**Assume extension map to point *****j***** of the form**
**Want to extend the bad guy ***x*** exactly:**
**This gives the following:**

## AdAMG-RS: Some Comments

**Note that the *****RS-AMG***** heuristic (also notions of “strong” and “weak” connections) changes in this more general setting: **smooth error varies most like the bad guy in the direction of “large” coefficients
**Note that this new method can solve systems that have been arbitrarily diagonally scaled**
**Note also that this is really all the current method extends *****RS-AMG***** to be able to solve**
**need to consider alternative approaches not based on M-matrix assumption**

## AdAMG-RS: Results

**Geometric choice of coarse grids**
**Bad guy generated by 2 cycles of the multilevel setup algorithm**

## AdAMG-RS: Results (Laplace)

**Nice scalability**

## AdAMG-RS: Results (piecewise constant)

**Geometric coarsening may be influencing D1 results**

## AdAMG-RS: Results (scaled)

**Scaled results are similar to the unscaled results**

**Scale by the following function**

## AdAMG-SA

## AdAMG-SA is an adaptive method based on Smoothed Aggregation

**In *****AdAMG-SA***** we will generate ****several bad guys**** to represent the smoothest components**
**As with *****AdAMG-RS***** more information is needed in order to construct good interpolation operators**
**We will get this information from the matrix indirectly through the prolongator smoother**
**More about that next...**

## Smoothed Aggretation basics

**Points are aggregated**
**Tentative prolongator is constructed from aggregates and local basis functions**
**Prolongation is built by “smoothing” the tentative prolongator**

## AdAMG-SA: Tentative prolongation is defined by “chopping up” the bad guys

**Local QR factorization is used to orthonormalize**
**Can have arbitrary numbers of DOFs per aggregate**

## AdAMG-SA: Results (Poisson)

**Scaled version is scaled by diagonal with entries given by                           random**

## AdAMG-SA: Results (2D Elasticity)

**Same scaling as before**

## Future Directions for AdAMG

**Come up with a better name!**
***AdAMG-RS*****:**
**other approaches for using the matrix entries**
**systems version**
**compatible relaxation to choose coarse grids**
**Improve efficiency of setup phase**
**Apply to harder problems (e.g., Maxwell, Helmholtz)**
**Theory**

## Compatible Relaxation (CR)

## CR and AMGe: Preliminaries

**Consider solving the SPD system**
**Reorder the equations**
**Define the global measure**

## CR and AMGe: Measuring the quality of the coarse grid

**Assume we are given a coarse grid.  ****Then, the following measures the ability of the coarse grid to represent algebraically smooth error.**
**Note that we have not restricted interpolation to be local here, but for PDE problems, we should be able to approximate *****Q***** with local interpolation.**
**We have that**

## CR and AMGe: Convergence of CR

**Compatible relaxation (Brandt, ETNA, 2000) is in general a modified relaxation scheme that keeps the coarse-level variables invariant**
**In general, the coarse-level variables are defined to be some linear combination of fine-level variables:**
**A general measure for the quality of the set of coarse variables is the convergence rate of *****CR***
**General idea: ***If CR is slow to converge, either increase the size of the coarse grid or do more relaxation*
**F-relaxation is a specific instance of *****CR***

## CR and AMGe: Convergence of CR

**Consider weighted pointwise Jacobi *****F*****-relaxation****then **
**For appropriate choice of weight: ***Jacobi F-relaxation is fast to converge iff the AMGe measure is small*

## Using CR to Define Coarse Variables

**To check convergence of *****CR*****, relax on the equation****and monitor pointwise convergence to *****0***
***CR***** coarsening algorithm:**

**Notes:**
Add graphics here.

## Using CR to Define Coarse Variables

**Initialize U-pts**
**Do *****CR***** and redefine U-pts as points slow to converge**
**Select new C-pts as indep. set over U**

## Using CR to Define Coarse Variables

**Initialize U-pts**
**Do *****CR***** and redefine U-pts as points slow to converge**
**Select new C-pts as indep. set over U**

## Using CR to Define Coarse Variables

**Initialize U-pts**
**Do *****CR***** and redefine U-pts as points slow to converge**
**Select new C-pts as indep. set over U**

## Using CR to Define Coarse Variables

**Initialize U-pts**
**Do *****CR***** and redefine U-pts as points slow to converge**
**Select new C-pts as indep. set over U**

## Using CR to Define Coarse Variables

**Initialize U-pts**
**Do *****CR***** and redefine U-pts as points slow to converge**
**Select new C-pts as indep. set over U**

## CR and AMGe: The Future

**Have (very) recently generalized the *****AMGe***** measure and theory to handle the more general *****CR***** setting**
**Thinking about how we might apply these ideas to automatically adapt to harder problem settings**

## Some Relevent Publications(see http://www.llnl.gov/casc/linear_solvers)

**Some Relevent Publications**(see http://www.llnl.gov/casc/linear_solvers)

- M. Brezina, A.J. Cleary, R.D. Falgout, V.E. Henson, J.E. Jones, T.A. Manteuffel, S.F. McCormick, and J.W. Ruge, “**Algebraic Multigrid Based on Element Interpolation (AMGe)**,” *SIAM J. Sci. Comput. *, **22** (2000), pp. 1570–1592.
- A.J. Cleary, R.D. Falgout, V.E. Henson, J.E. Jones, T.A. Manteuffel, S.F. McCormick, G.N. Miranda, and J.W. Ruge, “**Robustness and Scalability of Algebraic Multigrid**,” *SIAM J. Sci. Comput. *, **21** (2000), pp. 1886–1908.
- V.E. Henson and P. S. Vassilevski, “**Element-Free AMGe: General Algorithms for Computing Interpolation Weights in AMG**", *SIAM J. Sci. Comput. *, **23** (2001), pp. 629–650.
- J. Jones and P. Vassilevski, “**AMGe Based on Element Agglomeration**,” *SIAM J. Sci. Comput. *, **23** (2001), pp. 109–133.
- T. Chartier, R.D. Falgout, J.E. Jones, T.A. Manteuffel, S.F. McCormick, J.W. Ruge, and P.S. Vassilevski, “**Spectral AMGe**”, submitted.
- T. Chartier, R.D. Falgout, J.E. Jones, T.A. Manteuffel, S.F. McCormick, J.W. Ruge, and P.S. Vassilevski, “**Spectral Agglomeration AMGe**”, in preparation.
- M. Brezina, R.D. Falgout, S. MacLachlan, T.A. Manteuffel, S.F. McCormick, and J.W. Ruge, “**Self-Correcting Smoothed Aggregation (scSA)**,” in preparation.

## This work was performed under the auspices of the U.S. Department of Energy by Lawrence Livermore National Laboratory under contract no. W-7405-Eng-48.

- UCRL-PRES-149422