Multilevel Block Factorizations in Generalized Hierarchical Bases

Edmond Chow and Panayot S. Vassilevski
Lawrence Livermore National Laboratory
L-560, Box 808, Livermore, CA 94551


We propose a hierarchical basis (HB) method for unstructured problems where an exact or approximate hierarchical basis for the finite element space is not available or is difficult to find. Instead, a very simple generalized hierarchical basis is used, based on independent set coarsening and averaged piecewise constant interpolation. The possibly poorer A-orthogonality of the new basis vectors between different levels translates into a transformed matrix that is not as strongly block diagonal and is less well-conditioned than when a good HB transformation can be found. To compensate for this, we use a block factorization preconditioner instead of the usual block diagonal or block Gauss-Seidel preconditioners at each level of the transformed matrix. When the transformation is effective, the multilevel block factorization is economical to carry out; when it is less effective, the method relies more on the block factorization to compute an accurate preconditioning. The combination of the HB transformation with the approximate block factorization can be viewed as a modified block factorization in the sense that certain vectors that are in the near-nullspace of A remain in the near-nullspace of the approximate Schur complement. The factorization can be used as a preconditioner for the conjugate gradient method.

We further propose a multigrid method using the components set up by the approximate block factorization. In particular, the factorization constructs coarse grid operators as well as operators that act as prolongators. The multilevel block factorization that is recursively defined at each level may be used as a smoother, defining a type of W-cycle multigrid process.

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