Parallel Algebraic Multilevel Iteration Methods

Michael Jung
Fakultät f\"ur Mathematik, Technische Universität Chemnitz, Germany

Abstract

In recent years, highly efficient iterative solvers have been developed for large scale systems of linear equations resulting from finite element discretizations of elliptic boundary value problems. Examples for such solvers are the multigrid methods and the preconditioned conjugate gradient (PCG) method with additive multilevel preconditioners, with algebraic multilevel iteration preconditioners, or with preconditioners based on multigrid methods.

In the talk we will discuss some variants of algebraic multilevel iteration (AMLI) methods for elliptic boundary value problems in two- and three-dimensional domains. Numbering first the nodes of the mesh ${\cal T}_{l-1}$ and then the nodes of the finer mesh ${\cal T}_l$, the finite element stiffness matrix $A_l$ has the block structure

\begin{displaymath}
      \left( \!\! \begin{array}{cc}
              A_{l,vv}^{\phantom{1}} & A_{l,vm}^{\phantom{1}} \\[1ex]
              A_{l,vm}^T & A_{l,mm}^{\phantom{1}}
             \end{array}
      \!\! \right) = 
      \left( \!\! \begin{array}{cc}
               A_{l,vv}^{\phantom{1}} - 
               A_{l,vm}^{\phantom{1}} A_{l,mm}^{-1} A_{l,vm}^T & 
               A_{l,vm}^{\phantom{1}} \\[1ex]
               0 & A_{l,mm}^{\phantom{1}}
             \end{array}
      \!\! \right) \!
      \left( \!\! \begin{array}{cc}
               I_{l,v} & 0 \\[1ex]
               A_{l,mm}^{-1} A_{l,vm}^T & I_{l,m}^{\phantom{1}}
             \end{array}
      \!\! \right) \, .
\end{displaymath}
An AMLI preconditioner derived from this factorization of the stiffness matrix has the block structure
\begin{displaymath}
C_l =
\left( 
   \begin{array}{cc}
    {\tilde C}_{l-1}^{\rm C}  & {\tilde C}_{l,vm}^{\phantom{1}} \\[1ex]
    0 & C_{l,mm}
   \end{array}
\right) 
\left( 
   \begin{array}{cc}
    I_{l,v}^{\phantom{1}}             & 0       \\[1ex]
    C_{l,mm}^{-1} {\tilde C}_{l,vm}^T & I_{l,m}
   \end{array}
\right) \, ,
\end{displaymath}
where ${\tilde C}_{l,vm}^{\phantom{1}} = A_{l,vm}^{\phantom{1}} + J_{l,mv}^T (A_{l,mm}^{\phantom{1}} - C_{l,mm}^{\phantom{1}})$, $({\tilde C}_{l-1}^{\rm C})^{-1}$ is defined by $({\tilde C}_{l-1}^{\rm C})^{-1} = (I_{l-1}^{\phantom{1}} - P_\mu(C_{l-1}^{-1} A_{l-1}^{\phantom{1}})) A_{l-1}^{-1}$ ($P_\mu$ being a polynomial of degree $\mu$), and $C_{l,mm}$ approximates the block $A_{l,mm}$ of the stiffness matrix $A_l$. $C_{l-1}$ is defined analogously to $C_l$, and $C_1 = A_1$ (see, e.g., {\sc Axelsson} and {\sc Vassilevski} 1989, 1990, 1992).

The main ingredients of the AMLI preconditioner $C_l$ are the matrix $C_{l,mm}$ and the polynomial $P_\mu(t)$. We define the matrix $C_{l,mm}$ implicitly by the application of iterative solvers, e.g.~the Jacobi method or the symmetric Gauss-Seidel method. Polynomials of the type $P_{\mu}(t) = (1 - t)^{\mu}$ or polynomials derived from shifted Chebyshev polynomials will be used for the definition of $({\tilde C}_{l-1}^{\rm C})^{-1}$.

We discuss convergence properties of the AMLI-PCG methods and the implementation of these methods on parallel computers with MIMD architecture. Finally, we compare multigrid preconditioners, additive multilevel preconditioners and AMLI preconditioners on numerical examples.