Least angle regression, relaxed lasso, and elastic net for algebraic multigrid of systems of elliptic partial differential equations

Abstract In a sequence of papers, the author examined several statistical affinity measures for selecting the coarse degrees of freedom (CDOFs) or coarse nodes (Cnodes) in algebraic multigrid (AMG) for systems of elliptic partial differential equations (PDEs). These measures were applied to a set of relaxed vectors that exposes the problematic error components. Once the CDOFs are determined using any one of these measures, the interpolation operator is constructed in a bootstrap AMG (BAMG) procedure. However, in a recent paper of Kahl and Rottmann, the statistical least angle regression (LARS) method was utilized in the coarsening procedure and shown to be promising in the CDOF selection. This method is generally used in the statistics community to select the most relevant variables in constructing a parsimonious model for a very complicated and high‐dimensional model or data set (i.e., variable selection for a “reduced” model). As pointed out by Kahl and Rottmann, the LARS procedure has the ability to detect group relations between variables, which can be more useful than binary relations that are derived from strength‐of‐connection, or affinity measures, between pairs of variables. Moreover, by using an updated Cholesky factorization approach in the regression computation, the LARS procedure can be performed efficiently even when the original set of variables is large; and due to the LARS formulation itself (i.e., its ‐norm constraint), sparse interpolation operators can be generated. In this article, we extend the LARS coarsening approach to systems of PDEs. Furthermore, we incorporate some modifications to the LARS approach based on the so‐called elastic net and relaxed lasso methods, which are well known and thoroughly analyzed in the statistics community for ameliorating several major issues with LARS as a variable selection procedure. We note that the original LARS coarsening approach may have addressed some of these issues in similar or other ways but due to the limited details provided there, it is difficult to determine the extent of their similarities. Incorporating these modifications (or effecting them in similar ways) leads to improved robustness in the LARS coarsening procedure, and numerical experiments indicate that the changes lead to faster convergence in the multigrid method. Moreover, the relaxed lasso modification permits an indirect BAMG (iBAMG) extension to the interpolation operator. This iBAMG extension applied in an intra‐ or inter‐variable interpolation setting (i.e., nodal‐based coarsening), as well as in variable‐based coarsening, which will not preserve the nodal structure of a finest‐level discretization on the lower levels of the multilevel hierarchy, will be examined. For the variable‐based coarsening, because of the parsimonious feature of LARS, the performance is reasonably good when applied to systems of PDEs albeit at a substantial additional cost over a nodal‐based procedure.