ABSTRACT. Multilevel techniques are often the most efficient approaches for solving the very large linear systems that arise from discretized PDEs and other problems. While geometric multigrid requires detailed knowledge about the underlying PDE and its discretization, algebraic multigrid aims to be less intrusive, requiring less knowledge about the origin of the linear system. A key step in AMG is the choice of the coarse/fine partitioning, aiming to balance the convergence of the iteration with its cost. In past work (MacLachlan and Saad, SISC 2007), a constrained combinatorial optimization problem was used to define the ``best'' coarse grid within the setting of two-level reduction-based AMG and was shown to be NP-complete. Here, we develop a new coarsening algorithm based on simulated annealing to solve this problem, giving better results than the greedy algorithm developed previously. We present numerical results for test problems on both structured and unstructured meshes, demonstrating the ability to exploit knowledge about the underlying grid structure if it is available.

ABSTRACT. The strength-of-connection algorithm of smoothed aggregation algebraic multigrid (SA) generally consists of comparing some function of a matrix row (of either the problem matrix or some auxiliary matrix like the distance Laplacian) against a single, fixed, user-chosen threshold. Choose the threshold well, and SA converges rapidly. Choose it poorly and SA converges poorly, or not at all.

We propose an alternative approach based on cutting/clustering ideas, rather than a comparison against a fixed threshold. We will present results on a series of stretched mesh problems in 2D and 3D. We will demonstrate that this approach has certain theoretical advantages on simple stretched problems and also show that it works well in practice on more complicated distorted meshes.

ABSTRACT. We address the numerical solution of linear systems arising from the hybrid discretization of second-order elliptic partial differential equations (PDEs). Such discretizations hinge on a hybrid set of degrees of freedom (DoFs), namely cell- and face-defined, which naturally gives rise to a global hybrid system of linear equations. Assuming that the cell unknowns are only locally coupled, they can be eliminated from the system, leaving only face unknowns in the resulting Schur complement, also called statically condensed matrix. We propose in this work an algebraic multigrid preconditioner specifically targeting condensed systems corresponding to the lowest order discretization (piecewise constant). Like usual algebraic multigrid methods, we retrieve geometric information on the coupling of the DoFs from algebraic data. However, as the condensed matrix only gives information on the faces, we use the uncondensed version to reconstruct the connectivity graph between elements and faces. An aggregation-based coarsening strategy mimicking a geometric coarsening or semi-coarsening can then be set up to build coarse levels. Numerical experiments are performed on diffusion problems discretized by the Hybrid High Order (HHO) method at the lowest order on unstructured meshes. Our approach uses a K-cycle to precondition an outer flexible Krylov method. The results demonstrate the good convergence and the scalable behaviour of the proposed algebraic solver.

ABSTRACT. We consider the numerical solution of discrete Oseen problems. These problems are important in their own right, but also naturally arise when linearizing Navier-Stokes problems with the Picard method. Discrete Oseen problems are challenging to solve: as far as we know, no linear-time method can robustly solve them in a number of iterations bounded independently of the mesh size and of the Reynolds number, especially for variable convective flows. In particular, algebraic multigrid (AMG) methdos often struggle with such problems because of the small or null pressure block.

Here, we focus on an approach based on a simple algebraic transformation of the corresponding linear system. In this setting, our contribution is twofold. First, we present a norm-based algebraic convergence theory for the two-grid method applied to the transformed system. For constant coefficient problems discretized by finite difference on staggered grids and coarsening based on unsmoothed aggregation, the analysis of the constants involved in the theory shows that these are indeed bounded uniformly with respect to both the mesh size, the Reynolds number and the orientation of the convection flow. To obtain this result, essentially the same aggregates should be formed separately for each pressure or velocity component unknowns (as in point-based AMG coarsening), and aggregates should be aligned in the direction of the convective flow.

Our second contribution is a semi-algebraic multigrid method which is applied to the transformed system. This method is intended for problems with variable convective flow. Information is used from the discretization to group pressure and velocity unknowns into "points", the aggregation of which is driving the aggregation of each pressure or velocity component. Discretization data are also used to build an auxiliary matrix on the "point space", which is the used to produce "point" aggregates in an algebraic fashion. Numerical results show that the two-grid method converges independently of the mesh size and of the Reynolds number for constant convective flows, an almost independently of the Reynolds number for variable flows.

ABSTRACT. Highly scalable and robust Newton-Krylov domain decomposition approaches are widely used for the solution of nonlinear implicit problems, for example, in structural mechanics. In general, in these methods, the nonlinear problem is first linearized and afterwards decomposed into subdomains. By changing this order, and thus first decomposing the nonlinear problem, many nonlinear domain decomposition methods have been designed in the last two decades. These methods often show a higher robustness compared with classical Newton-Krylov variants due to a better resolution of local nonlinear effects by nonlinear subdomain problems. Additionally, the balance between local work, communication, and synchronization is usually more favorable for modern computer architectures. In all our nonlinear FETI-DP methods, we introduce a nonlinear right-preconditioner that can be interpreted as a (partial) nonlinear elimination of variables, where the choice of the elimination set as well as of the coarse space have a huge impact on the nonlinear convergence behavior. In order to design a nonlinear FETI-DP method that is optimally tailored to arbitrary problems, we introduce a strategy adapted from a paper by Shihua Gong and Xiao-Chuan Cai to choose problem-dependent elimination sets based on the residual of the nonlinear saddle point system.

ABSTRACT. Nonlinear FETI-DP (Finite Element Tearing and Interconnecting − Dual-Primal) methods are domain decomposition methods for the solution of nonlinear problems from the discretization of PDEs. In these methods, before linearization, the global problem is decomposed into concurrent nonlinear problems. Then, different local elimination strategies can be used, in the sense of nonlinear preconditioning. This talk discusses the globalization of Nonlinear FETI-DP methods with an exact differentiable penalty method, which is closely related to the standard augmented Lagrange method, but can use the solution of Lagrange-Newton equation for a Newton-like search direction. The nonlinear elimination can be explicitly used in this penalty method.

ABSTRACT. In this work we devise multigrid preconditioners for the reduced Hessian of linear- quadratic, space-time distributed, parabolic optimal control problems. While the idea of the preconditioner design is rooted in earlier work on distributed elliptic control, the presence of the temporal dimension in the controls poses multiple challenges, both in terms of potential problem size, as well as algorithm design and quality. To arrive at the linear system under scrutiny we first discretize the parabolic equation using space-time finite elements involving functions that are continuous in space and discontinuous in time, then we eliminate the state to produce a reduced unconstrained problem. We construct and analyse two kinds of multigrid preconditioners: the first is based on full coarsening in space and time, while the second is based on semi-coarsening in space only. Our analysis, in conjunction with numerical experiments, shows that both preconditioners are of optimal order with respect to the discretization. We prove that, under certain conditions, the preconditioner using full space-time coarsening is more efficient than the one involving semi-coarsening in space, a phenomenon that has not been observed previously. Our numerical results confirm the theoretical findings.

ABSTRACT. In this talk we present multigrid methods for linear-quadratic elliptic distributed optimal control problems. For optimal control problems constrained by general second order elliptic partial differential equations, we design and analyze a P_1 finite element method based on a saddle point formulation. We construct a W-cycle algorithm for the discrete problem and show that it is uniformly convergent in the energy norm for convex domains. Moreover, the contraction number decays at the optimal rate of m^{-1}, where m is the number of smoothing steps. We also prove that the convergence is robust with respect to a regularization parameter. The robust convergence of V-cycle and W-cycle algorithms on general domains are demonstrated by numerical results. For optimal control problems constrained by general second order elliptic partial differential equations together with pointwise constraints on the state variable, we design and analyze symmetric positive definite P_1 finite element methods based on a reformulation of the optimal control problem as a fourth order variational inequality. We develop a multigrid algorithm for the reduced systems that appear in a primal-dual active set method for the discrete variational inequalities. The performance of the algorithm is demonstrated by numerical results.

ABSTRACT. Deep neural networks (DNNs) exhibit excellent performance for many machine learning tasks, e.g., image classification, natural language processing, and game playing. One important class of DNNs is residual neural networks (ResNets), where the forward network evaluation can be viewed as a discretization of a time-dependent ordinary differential equation (ODE) and each network layer is associated with a time-step. Also, the backpropagation phase now corresponds to the classic adjoint-based optimization approach, where the time-dependent control variables are the network weights and biases. Thus from this perspective, one can apply parallel-in-time method(s) to ResNet deep learning problems by using parallel-in-time for both the forwards and backwards (backpropagation) phases. In this talk, we consider the parallel-in-time method, multigrid-reduction-in-time (MGRIT), and its corresponding implementation in XBraid. We will explore the application of MGRIT to DNNs in the context of these three potential benefits: (i) speedup of the training process through parallel-in-time (layer-parallel training), (ii) nested iteration approaches to training, where coarser networks are used to intelligently initialize finer networks, and (iii) connections between local learning and MGRIT for DNNs. Supporting numerical results are provided.

ABSTRACT. Can we learn a practical method to perform grid coarsening for multigrid methods? In its general form, this question is extremely hard to solve. There are numerous parameters that can affect the difficulty of this problem such as uniformity, grid structure, anisotropy, to name but a handful. In this paper, a simplified version of the problem is approached using Reinforcement Learning (RL). Utilizing Deep Q Learning (DQN), an RL framework, an agent is trained to optimally coarsen a small structured grid. Subsequently, the trained agent is employed to coarsen considerably larger structured grids. Two different network architectures, namely Convolutional Neural Network (CNN) and Graph Neural Network (GNN), have been implemented for the DQN agent neural network. In CNN architecture, multiple centralized agents work on the test grid and cooperate to achieve the global optimization goal. In the GNN architecture, a single trained agent works on different regions of the test grid, which are generated using Lloyd aggregation. Moreover, a post proceeding technique, utilizing the same agent, is used to improve the results further.

ABSTRACT. Graph Convolutional Networks (GCNs) have shown to be effective in handling unordered data like point clouds and meshes. In this work we propose novel approaches for graph convolution, pooling and unpooling, inspired from finite differences and algebraic multigrid frameworks. We form a parameterized convolution kernel based on discretized differential operators, leveraging the graph mass, gradient and Laplacian. This way, the parameterization does not depend on the graph structure, only on the meaning of the network convolutions as differential operators. To allow hierarchical representations of the input, we propose pooling and unpooling operations that are based on algebraic multigrid methods, which are mainly used to solve partial differential equations on unstructured grids. To motivate and explain our method, we compare it to standard convolutional neural networks, and show their similarities and relations in the case of a regular grid. Our proposed method is demonstrated in various experiments like classification and part-segmentation, achieving on par or better than state of the art results. We also analyze the computational cost of our method compared to other GCNs.

ABSTRACT. Classical AMG solvers often require careful parameter tuning to achieve optimal convergence, and the way these parameters affect performance can be unpredictable in practice. Evidence is presented that supervised learning techniques are able to learn certain characteristics of two-level multigrid solvers, particularly the rate of convergence and optimal relaxation weight for a given coarse/fine mesh splitting. Random perturbations of C/F splittings are generated and evaluated in a multigrid solver to train a convolutional neural network (CNN) in order to predict convergence and a relaxation weight for the 1D variable coefficient Poisson equation, and to predict the convergence rate for a specific 2D convection-diffusion problem. Additionally for the 2D problem, the use of graph nets is explored for use on general finite-element meshes.

ABSTRACT. We present a hybrid GPU-CPU version of the AGMG software, which implements an aggregation-based algebraic multigrid method. The original AGMG software is designed to run on CPU, and is known to be both fast and robust when compared to traditional AMG methods. With the new GPU-CPU implementation, the solution stage runs on GPU, except for operations on the coarsest grids, which are executed on CPU. We shall discuss some of the distinctive features of the new implementation, including weighted (polynomial) $\ell_1$-Jacobi smoothing and relaxed W multigrid cycle. We demonstrate that the resulting GPU-CPU implementation inherits the robustness of the original AGMG software, while bringing significant speedups with respect to the original CPU version. A comparison is also provided with AMGX solver from NVIDIA, showing that AGMG-GPU is more robust and significantly faster in the solution stage.

ABSTRACT. We propose a stencil-CSR matrix format to exploit the matrix structure of discretized partial differential equations (PDEs) with piecewise-constant coefficients. The format uses stencil representation for some rows of the matrix, typically belonging to a region with constant coefficients. The stencil representation saves memory and is suitable for SIMD-like parallelism, e.g. using vector instruction sets or on GPUs. Other rows are encoded in the general Compressed Sparse Row (CSR) format.

Further, we present a proof-of-concept GPU-accelerated algebraic multigrid (AMG) solver for systems with matrices in this stencil-CSR format. The considered AMG method is of aggregation type, meaning that the hierarchy of grids is constructed by grouping unknowns into aggregates. Within the regions described by a 2-dimensional (2D) or 3-dimensional (3D) stencil, periodic aggregation patterns are used in order to preserve the stencil structure on coarser grids. For the iterative solve phase, the stencil-structured block of the matrix is separated into tiles (in 2D) or bricks (in 3D) of unknowns which are assigned to GPU thread blocks for processing.

This solver is compared with the CSR-based solver AMGX from NVIDIA on a number of 2D and 3D model problems. We show that for large enough systems (typically >10^6 unknowns), our solver significantly outperforms AMGX in terms of both run time and memory usage.

ABSTRACT. Algebraic multigrid (AMG) is a widely used scalable solver and preconditioner for large-scale linear systems resulting from the discretization of a wide class of elliptic PDEs. While AMG has optimal computational complexity, the cost of communication has become a significant bottleneck that limits its scalability on modern machines with ever increasing parallelism and heterogeneous architectures. This talk examines the design, implementation, and parallel performance of a novel algorithm, Algebraic Multigrid Domain Decomposition (AMG-DD), designed specifically to limit communication. The goal of AMG-DD is to provide a low-communication alternative to standard AMG V-cycles by trading some additional computational overhead for a significant reduction in communication cost. Numerical results show that AMG-DD achieves superior accuracy per communication cost compared to AMG, and speedup over AMG is demonstrated on a large GPU cluster.