TY - JOUR
T1 - Compact fourier analysis for multigrid methods based on block symbols
AU - Huckle, Thomas K.
AU - Kravvaritis, Christos
PY - 2012
Y1 - 2012
N2 - The notion of compact Fourier analysis (CFA) is discussed. CFA allows description of multigrid (MG) in a nutshell and offers a clear overview on all MG components. The principal idea of CFA is to model the MG mechanisms by means of scalar generating functions and matrix functions (block symbols). The formalism of the CFA approach is presented by describing the symbols of the fine and coarse grid problems, the prolongation and restriction, the smoother, and the coarse grid correction, resp., smoothing corrections. CFA uses matrix functions and their features (e.g., product, inverse, adjugate, norm, spectral radius, eigenvectors, eigenvalues of multilevel ?-circulant matrices), and scalar functions and their roots. This leads to an elementary description and allows for an easy analysis of MG algorithms. A first application is to utilize CFA for deriving MG as a direct solver, i.e., an MG cycle that will converge in just one iteration step. Necessary and sufficient conditions that have to be fulfilled by the MG components are given for obtaining MG functioning as a direct solver. Furthermore, new general and practical smoothers and transfer operators that lead to efficient MG methods are introduced. In addition, we study sparse approximations of the Galerkin coarse grid operator yielding efficient and practicable MG algorithms (approximately direct solvers). Numerical experiments demonstrate the theoretical results.
AB - The notion of compact Fourier analysis (CFA) is discussed. CFA allows description of multigrid (MG) in a nutshell and offers a clear overview on all MG components. The principal idea of CFA is to model the MG mechanisms by means of scalar generating functions and matrix functions (block symbols). The formalism of the CFA approach is presented by describing the symbols of the fine and coarse grid problems, the prolongation and restriction, the smoother, and the coarse grid correction, resp., smoothing corrections. CFA uses matrix functions and their features (e.g., product, inverse, adjugate, norm, spectral radius, eigenvectors, eigenvalues of multilevel ?-circulant matrices), and scalar functions and their roots. This leads to an elementary description and allows for an easy analysis of MG algorithms. A first application is to utilize CFA for deriving MG as a direct solver, i.e., an MG cycle that will converge in just one iteration step. Necessary and sufficient conditions that have to be fulfilled by the MG components are given for obtaining MG functioning as a direct solver. Furthermore, new general and practical smoothers and transfer operators that lead to efficient MG methods are introduced. In addition, we study sparse approximations of the Galerkin coarse grid operator yielding efficient and practicable MG algorithms (approximately direct solvers). Numerical experiments demonstrate the theoretical results.
KW - Block symbol
KW - Fourier analysis
KW - Generating function
KW - Multigrid
KW - Toeplitz matrices
UR - http://www.scopus.com/inward/record.url?scp=84861610408&partnerID=8YFLogxK
U2 - 10.1137/110829854
DO - 10.1137/110829854
M3 - Article
AN - SCOPUS:84861610408
SN - 0895-4798
VL - 33
SP - 73
EP - 96
JO - SIAM Journal on Matrix Analysis and Applications
JF - SIAM Journal on Matrix Analysis and Applications
IS - 1
ER -