Skip to main content

LUP Student Papers

LUND UNIVERSITY LIBRARIES

Smoothed Aggregation for Nonsymmetric Linear Systems

Correnty, Siobhan LU (2019) In Master's Theses in Mathematica Sciences NUMM11 20191
Mathematics (Faculty of Engineering)
Centre for Mathematical Sciences
Abstract
Smoothed Aggregation (SA) is a technique from algebraic multigrid methods (AMG) which
has shown very promising results when solving systems of linear equations with symmetric
system matrices, but suboptimal results for nonsymmetric system matrices. The purpose
of this thesis is to investigate the method EMIN(r) and a closely related method EMIN
proposed by Sala and Tuminaro. EMIN(r) and EMIN were built on the success of SA in
symmetric systems, but perform better in nonsymmetric systems. These methods have a
more costly set-up, but promising results were found, in particular when performing one
time-step of linear advection at extremely high CFL numbers.
Popular Abstract (Swedish)
I naturen förekommer många differentialekvationer, som man inte kan lösa exakt, men som
man önskar kunna lösa approximativt. Många verktyg har utvecklas för just detta, men
man måste diskretisera och lösa system av linjära ekvationer för att få igång metoden. Det
här är en väldigt omfattande uppgift när systemen är stora. I det här examensarbetet har
vi arbetat med en sorts iterativ method för att lösa de stora systemen av linjära ekvationer,
som kommer från diskretiseringen av partiella differentiella ekvationer (PDEs).

Methoden heter multigrid och bakgrunden till den är att man delar upp problemet i två
delar: ‘smooth’ och ‘oscillatory’. Först använder man en ‘smoother’ (t.ex. några iterationer
av Jacobi) som tar bort de... (More)
I naturen förekommer många differentialekvationer, som man inte kan lösa exakt, men som
man önskar kunna lösa approximativt. Många verktyg har utvecklas för just detta, men
man måste diskretisera och lösa system av linjära ekvationer för att få igång metoden. Det
här är en väldigt omfattande uppgift när systemen är stora. I det här examensarbetet har
vi arbetat med en sorts iterativ method för att lösa de stora systemen av linjära ekvationer,
som kommer från diskretiseringen av partiella differentiella ekvationer (PDEs).

Methoden heter multigrid och bakgrunden till den är att man delar upp problemet i två
delar: ‘smooth’ och ‘oscillatory’. Först använder man en ‘smoother’ (t.ex. några iterationer
av Jacobi) som tar bort de ‘oscillatory’ felvärdena. Sedan löser man ett system,
som är lika originalet men mindre, och därefter interpolerar man lösningen av det mindre
problemet för att få en bättre approximation till det stora. Att lösa ett mindre problem
tar bort ‘smooth’ felvärdena.

Om man bara använder del ett, är metoden för långsam. Om man bara använder del
två, konvergerar metoden inte. Men, om man använder båda tillsammans, blir metoden
kraftig och snabb.

I den här uppsatsen experimenterar vi med ‘smoothed aggregation’, som är en variant
av den traditionella multigridmetoden. Man använder lite extra ‘smoothing’ när man minskar
problemet och igen när man gör det stort igen. Det fungerar väldigt bra när man löser
ett system av linjära ekvationer med en symmetrisk positiv definit (SPD) systemmatris.
Tyvärr går det inte lika bra när systemmatrisen inte är SPD. Vi tittar också på en variant
av ‘smoothed aggregation’ som fungerar bra när systemmatrisen inte är SPD (EMIN(r)). (Less)
Please use this url to cite or link to this publication:
author
Correnty, Siobhan LU
supervisor
organization
course
NUMM11 20191
year
type
H2 - Master's Degree (Two Years)
subject
publication/series
Master's Theses in Mathematica Sciences
report number
LUNFNA-3029-2019
ISSN
1404-6342
other publication id
2019:E45
language
English
id
8997702
date added to LUP
2019-11-13 19:42:26
date last changed
2019-11-13 19:42:26
@misc{8997702,
  abstract     = {{Smoothed Aggregation (SA) is a technique from algebraic multigrid methods (AMG) which
has shown very promising results when solving systems of linear equations with symmetric
system matrices, but suboptimal results for nonsymmetric system matrices. The purpose
of this thesis is to investigate the method EMIN(r) and a closely related method EMIN
proposed by Sala and Tuminaro. EMIN(r) and EMIN were built on the success of SA in
symmetric systems, but perform better in nonsymmetric systems. These methods have a
more costly set-up, but promising results were found, in particular when performing one
time-step of linear advection at extremely high CFL numbers.}},
  author       = {{Correnty, Siobhan}},
  issn         = {{1404-6342}},
  language     = {{eng}},
  note         = {{Student Paper}},
  series       = {{Master's Theses in Mathematica Sciences}},
  title        = {{Smoothed Aggregation for Nonsymmetric Linear Systems}},
  year         = {{2019}},
}