Deep Multigrid: learning prolongation and restriction matrices

Alexandr Katrutsa, Talgat Daulbaev, Ivan Oseledets

Abstract

This paper proposes a method to optimize restriction and prolongation operators in the two-grid method, which is straightforwardly extended to the geometric multigrid method (GMM). GMM is used in solving discretized partial differential equations (PDEs) and relies on these operators for fast convergence. Since optimal operators are often unknown for complex problems, we reformulate the two-grid method as a deep neural network where each operation corresponds to a layer. The parameters of these layers are the restriction and prolongation operators. By stating an optimization problem with respect to these operators and using backpropagation, we obtain optimal solvers. Experiments on Laplace, Helmholtz, and convection-diffusion equations demonstrate that this approach yields operators with significantly faster convergence rates.

Introduction

Solving large-scale systems of linear equations is fundamental to scientific computing, particularly for simulations involving Partial Differential Equations (PDEs). Multigrid methods are among the most efficient algorithms for this task, utilizing a hierarchy of grids to eliminate errors at different scales. They "smooth" high-frequency errors on a fine grid and "restrict" low-frequency errors to a coarser grid for easier resolution.

The efficiency of these methods hinges on two key operators: Restriction ($R$), which moves data from fine to coarse grids, and Prolongation ($P$), which interpolates from coarse to fine. While standard linear interpolation suffices for simple problems like the Poisson equation, complex physics—such as high-frequency wave equations (Helmholtz) or convection-diffusion—often cause standard operators to fail. Historically, designing these operators required deep mathematical expertise. This paper introduces Deep Multigrid (DMG) to automatically learn optimal operators through a deep learning framework.

Methodology: Multigrid as a Neural Network

The core innovation of DMG is the mapping of the two-grid iteration steps into a specific deep neural network architecture. In this framework, the entries of the $R$ and $P$ matrices are treated as trainable weights.

Flowchart of the two-grid iteration reformulated as a sequence of operations, where restriction (R) and prolongation (P) act as trainable parameters.

Architecture and Loss Function

As shown in the figure above, the iteration includes presmoothing, residual calculation, restriction, coarse-grid solving, prolongation, and postsmoothing. To optimize this "network," the authors target the minimization of the spectral radius ($\rho$) of the iteration matrix, which determines the error reduction per step. Because the spectral radius is non-smooth, they utilize an approximation based on Gelfand’s formula and a stochastic trace estimator to handle large-scale matrices without explicit formation.

Optimization Strategy

For challenging problems like high-frequency waves, the optimization landscape is highly non-convex. The authors employ a homotopy approach, starting with a simple Poisson problem and gradually evolving the system toward the target Helmholtz problem. This "curriculum learning" strategy helps the optimizer find effective local minima that standard initialization would miss.

Experimental Evaluation

The method was evaluated on three classic 1D PDE benchmarks: the Poisson equation, the Helmholtz equation, and the singularly perturbed convection-diffusion equation.

Key Results

  • Superior Convergence: In nearly all cases, DMG outperformed standard linear interpolation and Algebraic Multigrid (AMG) by producing operators with smaller spectral radii.
  • Handling High Frequencies: For the high-frequency Helmholtz equation ($k=1000$), where standard methods typically diverge (spectral radius $> 4000$), DMG learned operators achieving a spectral radius of 0.11. This represents a nearly 90% error reduction per iteration.
  • Robustness to Discontinuities: DMG successfully learned effective operators for problems with piecewise constant coefficients and non-symmetric matrices, areas where traditional heuristics often struggle.

Conclusion and Future Directions

Deep Multigrid demonstrates that numerical iterations can be viewed as structured neural networks. This perspective allows the application of modern optimization tools (like Adam and Autograd) to classical numerical analysis. While currently demonstrated on 1D problems, the framework is theoretically extensible to higher dimensions. Future work aims to develop "feed-forward" models that can predict optimal $R$ and $P$ operators directly from PDE coefficients, reducing the training overhead for new problems.

Summary updated

Abstract

This paper proposes the method to optimize restriction and prolongation operators in the two-grid method. The proposed method is straightforwardly extended to the geometric multigrid method (GMM). GMM is used in solving discretized partial differential equation (PDE) and based on the restriction and prolongation operators. The operators are crucial for fast convergence of GMM, but they are unknown. To find them we propose a reformulation of the two-grid method in terms of a deep neural network with a specific architecture. This architecture is based on the idea that every operation in the two-grid method can be considered as a layer of a deep neural network. The parameters of layers correspond to the restriction and prolongation operators. Therefore, we state an optimization problem with respect to these operators and get optimal ones through backpropagation approach. To illustrate the performance of the proposed approach, we carry out experiments on the discretized Laplace equation, Helmholtz equation and singularly perturbed convection-diffusion equation and demonstrate that proposed approach gives operators, which lead to faster convergence.
BibTeX
@misc{katrutsa2017deep,
  author = {Alexandr Katrutsa and Talgat Daulbaev and Ivan Oseledets},
  title = {{Deep Multigrid: learning prolongation and restriction matrices}},
  year = {2017},
  eprint = {1711.03825},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1711.03825},
}
Figure