Abstract

The Hierarchical Basis Multigrid Method was originally developed for sequences of refined meshes. In recent years, we have generalized such bases to completely unstructured meshes, not just those arising from some refinement process. This is done by recognizing the strong connection between the Hierarchical Basis Multigrid Method and an Incomplete LU factorization of the nodal stiffness matrix. Once this connection is made, it is fairly easy to make a symbolic ILU algorithm for unstructured meshes which mimics the ILU process on a structured mesh leading to the classical hierarchical basis. This symbolic elimination process essentially defines the supports of the hierarchical basis functions (or the sparsity structure of the hierarchical basis stiffness matrix). In the classical case, certain linear combinations of fine grid basis functions are formed, with the combination coefficients derived from the geometry of the mesh. For these special choices, the linear combinations simplify to coarse grid nodal basis functions. In the case of completely unstructured meshes, the coefficients for the linear combinations can also be specified in a natural way using the geometry of the mesh. In terms of ILU, the expansion coefficients are just the multipliers in the ILU decomposition. This leads one to consider the possibility of defining these expansion coefficients in a more algebraic fashion. For example, one can choose these coefficients to eliminate certain off diagonal elements of the hierarchical basis stiffness matrix, as is done in the case of classical ILU. While geometry based coefficients seem adequate for isotropic, self-adjoint problems, we have found that our algebraic choices can greatly improve the robustness of the HBMG iteration for other types of equations, notably convection dominated convection-diffusion equations.