Reducing Operator Complexity in Algebraic Multigrid with Machine Learning Approaches Open Access
Chang, Kai (Spring 2023)
Abstract
Large-scale sparse linear systems arisen from discretizing partial differential equations (PDEs) appear ubiquitously in science and engineering. Algebraic multigrid methods (AMG) are among the most efficient algorithms for numerically solving such systems. However, AMG often suffers from the problem of increasing density (i.e., increased number of non-zero entries in the linear operator) as a parallel solver, which induces an excessively high computational cost for tasks, such as data communications, other than the actual computations. How to alleviate this issue to improve the efficiency and scalability of AMG remains challenging and crucial.
In this thesis, we try to tackle this problem by leveraging modern data-driven methods. We propose a multilevel deep learning method to sparsify all the discretized coarse-grid operators in the hierarchy of multigrid methods when solving parametric PDEs, i.e. PDEs dependent on some parameters. The method succeeds in reducing the number of non-zero entries in all the discretized operators by at least 44%. Strictly following the multigrid convergence theory, the method does not trade sparsity with the convergence behaviour of multigrid methods. Another key feature of the method is its capability of generalizing to not only problems of larger sizes, but also PDEs with different parameters from those in the training set. This allows the trained sparsifiers to be used in various settings aside from the training instances, thereby enhancing the practical utility of the algorithm. We provide extensive numerical experiments on challenging anisotropic rotated Laplacian problems and linear elasticity problems to illustrate its superior performance.
Table of Contents
1 Introduction.......................... 1
2 Preliminaries.......................... 5
2.1 Discretizations of PDEs and Stencil Representations . . . . . . . . . . 5
2.2 Deep Neural Networks .......................... 8
2.3 A Multi-Headed Neural Network..................... 10
3 Iterative Methods for Solving Linear Systems 12
3.1 Relaxation Methods ........................... 13
3.1.1 The Basic Form.......................... 13
3.1.2 Examples of Relaxation Methods ................ 13
3.2 Krylov Subspace Methods and the Generalized Minimal Residual (GMRES) Method............................... 15
3.3 The Multigrid V-Cycle .......................... 17
4 The Issue of Increasing Operator Density in Multigrid.......................... 21
5 Sparsification of Coarse-Grid Operators via Machine Learning.......................... 24
5.1 Spectral Equivalence and Multigrid Convergence . . . . . . . . . . . . 24
5.2 The Algorithmic Pipeline......................... 28
5.3 Training, Testing, and Generalization.................. 31
6 Numerical Experiments.................. 38
6.1 The Evaluation Metrics.......................... 38
6.2 Circulant Stencils............................. 39
6.3 The 2-D Rotated Laplacian Problem .................. 41
6.4 The 2-Dimensional Linear Elasticity Problem . . . . . . . . . . . . . 44
6.5 Comparison with the Sparsified Smooth Aggregation Method . . . . . 47
7 Discussion and Future Work 50
8 Conclusion 51
Bibliography 52
About this Honors Thesis
| School | |
|---|---|
| Department | |
| Degree | |
| Submission | |
| Language |
|
| Research Field | |
| Keyword | |
| Committee Chair / Thesis Advisor | |
| Committee Members |
Primary PDF
| Thumbnail | Title | Date Uploaded | Actions |
|---|---|---|---|
|
|
Reducing Operator Complexity in Algebraic Multigrid with Machine Learning Approaches () | 2023-04-25 15:22:20 -0400 |
|
Supplemental Files
| Thumbnail | Title | Date Uploaded | Actions |
|---|