Generalizing smoothed aggregation-based algebraic multigrid

smoothed aggregation;algebraic multigrid;Helmholtz;indefinite;nonsymmetric;algebraic coarsening;discontinuous Galerkin;high-order;prolongation smoothing;strength-of-connection

Schroder, Jacob B.

关键词: smoothed aggregation;    algebraic multigrid;    Helmholtz;    indefinite;    nonsymmetric;    algebraic coarsening;    discontinuous Galerkin;    high-order;    prolongation smoothing;    strength-of-connection;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/17044/Schroder_Jacob.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

Smoothed aggregation-based (SA) algebraic multigrid (AMG) is a popular andeffective solver for systems of linear equations that arise from discretizedpartial differential equations.While SA has been effective over a broad classof problems, it has several limitations and weaknesses that this thesis isintended to address. This includes the development of a more robuststrength-of-connection measure which guides coarsening and thechoice of interpolation sparsity patterns. Unfortunately, the classic strengthmeasure is only well-founded for M-matrices, leading us to develop a newmeasure based on local knowledge of both algebraically smooth error and thebehavior of interpolation.Another limitation is that classic SA is only formallydefined for Hermitian positive definite problems.For non-Hermitianoperators, the operator-induced energy-norm does not exist, which impacts thecomplementary relationship between relaxation and interpolation.This requiresa redesign of SA, such that restriction and prolongation operators approximatethe left and right near null-spaces, respectively.As a result, we develop general SAsetup algorithms for both the Hermitian positive-definite and the non-Hermitiancases.To realize these algorithms, we develop general prolongation smoothingmethods so that restriction and prolongation target the left and right near null-spaces,respectively.Overall, the proposed methods do not assume any user-inputbeyond what standard SA does and the result is a new direction for multigridmethods for non-Hermitian systems.Several problem areas motivate ourdevelopment.For example, rotated anisotropic diffusion and linearizedelasticity problems using standard discretizations can easily generatenon-M-matrices that prove difficult for standard SA and AMG.High- andlow-order discontinuous Galerkin discretizations also generate difficult non-M-matrices for ellipticproblems.Target non-Hermitian problems include flow problems andwave-like problems, e.g., Helmholtz.Additionally for wave-likeproblems, there is a rich non-standard wave-like near null-space, which must be capturedby the coarse levels—a task beyond the scope of traditional AMGor SA coarsening techniques.