An official website of the United States government
Abstract Problems arising in Earth's mantle convection involve finding the solution to Stokes systems with large viscosity contrasts. These systems contain localized features which, even with adaptive mesh refinement, result in linear systems that can be on the order of 109or more unknowns. One common approach for preconditioning to the velocity block of these systems is to apply an Algebraic Multigrid (AMG) V‐cycle (as is done in the ASPECT software, for example), however, we find that AMG is lacking robustness with respect to problem size and number of parallel processes. Additionally, we see an increase in iteration counts with refinement when using AMG. In contrast, the Geometric Multigrid (GMG) method, by using information about the geometry of the problem, should offer a more robust option.Here we present a matrix‐free GMG V‐cycle which works on adaptively refined, distributed meshes, and we will compare it against the current AMG preconditioner (Trilinos ML) used in theASPECT1software. We will demonstrate the robustness of GMG with respect to problem size and show scaling up to 114,688 cores and 217 billion unknowns. All computations are run using the open‐source, finite element librarydeal.II.2
more »
« less
Algebraic multigrid preconditioning of the Hessian in optimization constrained by a partial differential equation
Summary We construct an algebraic multigrid (AMG) based preconditioner for the reduced Hessian of a linear‐quadratic optimization problem constrained by an elliptic partial differential equation. While the preconditioner generalizes a geometric multigrid preconditioner introduced in earlier works, its construction relies entirely on a standard AMG infrastructure built for solving the forward elliptic equation, thus allowing for it to be implemented using a variety of AMG methods and standard packages. Our analysis establishes a clear connection between the quality of the preconditioner and the AMG method used. The proposed strategy has a broad and robust applicability to problems with unstructured grids, complex geometry, and varying coefficients. The method is implemented using the Hypre package and several numerical examples are presented.
more »
« less
- Award ID(s):
- 1913201
- PAR ID:
- 10455562
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Numerical Linear Algebra with Applications
- Volume:
- 28
- Issue:
- 1
- ISSN:
- 1070-5325
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Algebraic Multigrid (AMG) is an extremely popular linear system solver and/or preconditioner approach for matrices obtained from the discretization of elliptic operators. However, its performance and scalability for large systems obtained from unstructured discretizations seem less consistent than for geometric multigrid (GMG). To a large extent, this is due to loss of sparsity at the coarser grids and the resulting increased cost and poor scalability of the matrix-vector multiplication. While there have been attempts to address this concern by designing sparsification algorithms, these affect the overall convergence. In this work, we focus on designing a specialized matrix-vector multiplication (matvec) that achieves high performance and scalability for a large variation in the levels of sparsity. We evaluate distributed and shared memory implementations of our matvec operator and demonstrate the improvements to its scalability and performance in AMG hierarchy and finally, we compare it with PETSc.more » « less
-
Vassilevski, Panayot (Ed.)Abstract In a recent paper, the author examined a correlation affinity measure for selecting the coarse degrees of freedom (CDOFs) or coarse nodes (C nodes) in systems of elliptic partial differential equations (PDEs). This measure was applied to a set of relaxed vectors, which exposed the near‐nullspace components of the PDE operator. Selecting the CDOFs using this affinity measure and constructing the interpolation operators using a least‐squares procedure, an algebraic multigrid (AMG) method was developed. However, there are several noted issues with this AMG solver. First, to capture strong anisotropies, a large number of test vectors may be needed; and second, the solver's performance can be sensitive to the initial set of random test vectors. Both issues reflect the sensitive statistical nature of the measure. In this article, we derive several other statistical measures that ameliorate these issues and lead to better AMG performance. These measures are related to a Markov process, which the PDE itself may model. Specifically, the measures are based on the diffusion distance/effective resistance for such process, and hence, these measures incorporate physics into the CDOF selection. Moreover, because the diffusion distance/effective resistance can be used to analyze graph networks, these measures also provide a very economical scheme for analyzing large‐scale networks. In this article, the derivations of these measures are given, and numerical experiments for analyzing networks and for AMG performance on weighted‐graph Laplacians and systems of elliptic boundary‐value problems are presented.more » « less
-
Summary This article develops an algebraic multigrid (AMG) method for solving systems of elliptic boundary‐value problems. It is well known that multigrid for systems of elliptic equations faces many challenges that do not arise for most scalar equations. These challenges include strong intervariable couplings, multidimensional and possibly large near‐nullspaces, analytically unknown near‐nullspaces, delicate selection of coarse degrees of freedom (CDOFs), and complex construction of intergrid operators. In this article, we consider only the selection of CDOFs and the construction of the interpolation operator. The selection is an extension of the Ruge–Stuben algorithm using a new strength of connection measure taken between nodal degrees of freedom, that is, between all degrees of freedom located at a gridpoint to all degrees of freedom at another gridpoint. This measure is based on a local correlation matrix generated for a set of smoothed test vectors derived from a relaxation‐based procedure. With this measure, selection of the CDOFs is then determined by the number of strongly correlated connections at each node, with the selection processed by a Ruge–Stuben coloring scheme. Having selected the CDOFs, the interpolation operator is constructed using a bootstrap AMG (BAMG) procedure. We apply the BAMG procedure either over the smoothed test vectors to obtain an intervariable interpolation scheme or over the like‐variable components of the smoothed test vectors to obtain an intravariable interpolation scheme. Moreover, comparing the correlation measured between the intravariable couplings with the correlation between all couplings, a mixed intravariable and intervariable interpolation scheme is developed. We further examine an indirect BAMG method that explicitly uses the coefficients of the system operator in constructing the interpolation weights. Finally, based on a weak approximation criterion, we consider a simple scheme to adapt the order of the interpolation (i.e., adapt the caliber or maximum number of coarse‐grid points that a fine‐grid point can interpolate from) over the computational domain.more » « less
-
Abstract Discretization of flow in fractured porous media commonly lead to large systems of linear equations that require dedicated solvers. In this work, we develop an efficient linear solver and its practical implementation for mixed‐dimensional scalar elliptic problems. We design an effective preconditioner based on approximate block factorization and algebraic multigrid techniques. Numerical results on benchmarks with complex fracture structures demonstrate the effectiveness of the proposed linear solver and its robustness with respect to different physical and discretization parameters.more » « less
