Optimizing multigrid smoothers using GLT theory
(2020) In Master's Theses in Mathematical Sciences NUMM11 20201Mathematics (Faculty of Engineering)
Centre for Mathematical Sciences
- Abstract
- Multigrid algorithms are algorithms used to find numerical solutions to differential equations using a hierarchy of grids of different coarseness. This exploits the fact that short-wavelength components of the solutions converges at a faster rate than the long-wavelength components when using some basic iterative methods, such as the Jacobi method or the Gauss-Seidel method. These iterative methods are also called smoothers since they have the effect of smoothing out the errors.
In this thesis, two classes of smoothers based on time integration methods are studied using the one dimensional linear advection equation as model problem. The first class is a class based on explicit Runge-Kutta methods, and the other class is derived from... (More) - Multigrid algorithms are algorithms used to find numerical solutions to differential equations using a hierarchy of grids of different coarseness. This exploits the fact that short-wavelength components of the solutions converges at a faster rate than the long-wavelength components when using some basic iterative methods, such as the Jacobi method or the Gauss-Seidel method. These iterative methods are also called smoothers since they have the effect of smoothing out the errors.
In this thesis, two classes of smoothers based on time integration methods are studied using the one dimensional linear advection equation as model problem. The first class is a class based on explicit Runge-Kutta methods, and the other class is derived from considering implicit Runge-Kutta methods. For both classes it is possible to derive a matrix M, dependent on the coefficient function in the linear advection problem and the parameters of the smoother, which describes the evolution of the error. To optimize the smoothers parameters are chosen so that the eigenvalues of M are optimized.
If the coefficient function is constant it is possible to derive a closed form expression for the eigenvalues of the resulting matrix M. However, in the variable coefficient case it is not possible, and for large matrices it is impractical to compute the eigenvalues using iterative methods. Therefore, the theory of Generalized Locally Toeplitz (GLT) sequences is used to instead approximate the distribution of the eigenvalues. This results in an approximate optimization problem. The results show that this is an effective method for obtaining parameters for the smoothers in the variable coefficient case. (Less) - Popular Abstract (Swedish)
- Många fysiska problem, så som väderprognoser, luftflöden runt en flygplansvinge och vattenvågor, kan modelleras av differentialekvationer. Dessa kan inte alltid lösas analytiskt, men idag är våra datorer kraftfulla nog att lösa många av dessa modeller numeriskt, dvs. genom att diskretisera problemet och approximera lösningen på ett rutnät. Lösningarna för modellerna kan beskrivas som summor av vågor med långa och korta våglängder. När man använder simpla iterativa lösare, också kallade för smoothers, så konvergerar de korta våglängderna fortare än de långa. Problemet med dessa lösare är just den långsamma konvergensen av de långa våglängderna. Dessa konvergerar snabbare om man använder grövre nät. I multigrid-algoritmer använder man sig... (More)
- Många fysiska problem, så som väderprognoser, luftflöden runt en flygplansvinge och vattenvågor, kan modelleras av differentialekvationer. Dessa kan inte alltid lösas analytiskt, men idag är våra datorer kraftfulla nog att lösa många av dessa modeller numeriskt, dvs. genom att diskretisera problemet och approximera lösningen på ett rutnät. Lösningarna för modellerna kan beskrivas som summor av vågor med långa och korta våglängder. När man använder simpla iterativa lösare, också kallade för smoothers, så konvergerar de korta våglängderna fortare än de långa. Problemet med dessa lösare är just den långsamma konvergensen av de långa våglängderna. Dessa konvergerar snabbare om man använder grövre nät. I multigrid-algoritmer använder man sig därför av flera rutnät av olika täthet för att få snabb konvergens av både korta och långa våglängder av lösningen. Syftet med det här arbetet är att studera hur parametrar kan väljas för två andra typer av smoothers med hjälp av något kallat GLT-teori (Generalized Locally Toeplitz theory). (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/student-papers/record/9024508
- author
- Huynh, Denhanh LU
- supervisor
- organization
- course
- NUMM11 20201
- year
- 2020
- type
- H2 - Master's Degree (Two Years)
- subject
- keywords
- multigrid, smoothers, GLT
- publication/series
- Master's Theses in Mathematical Sciences
- report number
- LUNFNA-3032-2020
- ISSN
- 1404-6342
- other publication id
- 2020:E64
- language
- English
- id
- 9024508
- date added to LUP
- 2020-12-07 13:19:02
- date last changed
- 2020-12-07 13:19:02
@misc{9024508,
abstract = {{Multigrid algorithms are algorithms used to find numerical solutions to differential equations using a hierarchy of grids of different coarseness. This exploits the fact that short-wavelength components of the solutions converges at a faster rate than the long-wavelength components when using some basic iterative methods, such as the Jacobi method or the Gauss-Seidel method. These iterative methods are also called smoothers since they have the effect of smoothing out the errors.
In this thesis, two classes of smoothers based on time integration methods are studied using the one dimensional linear advection equation as model problem. The first class is a class based on explicit Runge-Kutta methods, and the other class is derived from considering implicit Runge-Kutta methods. For both classes it is possible to derive a matrix M, dependent on the coefficient function in the linear advection problem and the parameters of the smoother, which describes the evolution of the error. To optimize the smoothers parameters are chosen so that the eigenvalues of M are optimized.
If the coefficient function is constant it is possible to derive a closed form expression for the eigenvalues of the resulting matrix M. However, in the variable coefficient case it is not possible, and for large matrices it is impractical to compute the eigenvalues using iterative methods. Therefore, the theory of Generalized Locally Toeplitz (GLT) sequences is used to instead approximate the distribution of the eigenvalues. This results in an approximate optimization problem. The results show that this is an effective method for obtaining parameters for the smoothers in the variable coefficient case.}},
author = {{Huynh, Denhanh}},
issn = {{1404-6342}},
language = {{eng}},
note = {{Student Paper}},
series = {{Master's Theses in Mathematical Sciences}},
title = {{Optimizing multigrid smoothers using GLT theory}},
year = {{2020}},
}