Skip to main content

LUP Student Papers

LUND UNIVERSITY LIBRARIES

Parallelization Of The GMRES Method

Görtz, Morgan LU (2016) In Bachelor's Theses in Mathematical Sciences NUMK01 20161
Mathematics (Faculty of Engineering)
Abstract
In this thesis a GMRES method is constructed and tested. The method is implemented in a C++ program with the MPI protocol to make it parallel. The parallel parts of this program are discussed in detail, especially the communication and the partitioning of the data between the processes. In the tests that were conducted we come to three important conclusions: the method works as expected, a substantial improvement is observed when more processes are introduced, and the method seems to be stable for very large systems.
Popular Abstract (Swedish)
GMRES (Generalized Minimal RESidual) är en iterativ metod som löser linjära system, där matrisen är inverterbar. Metoden löser systemet genom att generera bättre approximationer i varje iteration. Detta tillvägagångssätt är intressant i de fall man redan har en bra approximation att utgå ifrån. Med tillräckligt bra approximation kan ett väldigt stort system lösas med få iterationer, med en given tolerans.

Moderna datorer har flera processorer (cores) för att hantera flera program parallellt, eller tillåta ett program att använda flera processorer samtidigt. I denna rapport har det senare gjorts, genom att implementera ett MPI-protokoll (Message Passing Interface). Detta protokoll gör kommunikationen mellan processorer möjlig. Med sådan... (More)
GMRES (Generalized Minimal RESidual) är en iterativ metod som löser linjära system, där matrisen är inverterbar. Metoden löser systemet genom att generera bättre approximationer i varje iteration. Detta tillvägagångssätt är intressant i de fall man redan har en bra approximation att utgå ifrån. Med tillräckligt bra approximation kan ett väldigt stort system lösas med få iterationer, med en given tolerans.

Moderna datorer har flera processorer (cores) för att hantera flera program parallellt, eller tillåta ett program att använda flera processorer samtidigt. I denna rapport har det senare gjorts, genom att implementera ett MPI-protokoll (Message Passing Interface). Detta protokoll gör kommunikationen mellan processorer möjlig. Med sådan kommunikation kan ett program skrivas, där flera processorer arbetar tillsammans för att göra programmet snabbare. Målet med det utförda arbetet har varit att accelerera en GMRES implementering genom att parallellisera den. Implementeringen av GMRES som användes i denna uppsats använder endast linjära transformationer och vektoroperationer. En parallelliserad vektorklass skapades för att hantera formatering och vektoroperationer. Detta tillvägagångssätt ledde till att metoden kan skrivas likt den icke parallelliserade GMRES-metoden. C++ har används som programmeringsspråk och MPICH har används för MPI implementering.
Den parallelliserade GMRES-metod testades genom tre steg. I det första steget jämfördes metodens egenskaper med bakomliggande teori. På så sätt kunde verifieras att metoden fungerade. Andra steget analyserades förbättringen när GMRES-metoden parallelliserats. Exekveringstider för diverse linjära system noterades med avseende på olika dimensioner och antal aktiva processorer. I det tredje och sista steget testades metodens stabilitet. Mycket stora, glesa system löstes för att jämföras med testresultaten från steg två.

I rapporten dras slutsatsen att metoden fungerar som förväntat, att metoden innebär en signifikant förbättring avseende exekveringstid samt att metoden är stabil även för större, glesa linjära system. (Less)
Please use this url to cite or link to this publication:
author
Görtz, Morgan LU
supervisor
organization
alternative title
Parallellisering Av GMRES-Metoden
course
NUMK01 20161
year
type
M2 - Bachelor Degree
subject
keywords
GMRES, MPI
publication/series
Bachelor's Theses in Mathematical Sciences
report number
LUNFNA-4010-2016
ISSN
1654-6229
other publication id
K11
language
English
id
8889583
date added to LUP
2018-12-28 14:21:09
date last changed
2019-07-12 09:48:13
@misc{8889583,
  abstract     = {In this thesis a GMRES method is constructed and tested. The method is implemented in a C++ program with the MPI protocol to make it parallel. The parallel parts of this program are discussed in detail, especially the communication and the partitioning of the data between the processes. In the tests that were conducted we come to three important conclusions: the method works as expected, a substantial improvement is observed when more processes are introduced, and the method seems to be stable for very large systems.},
  author       = {Görtz, Morgan},
  issn         = {1654-6229},
  keyword      = {GMRES,MPI},
  language     = {eng},
  note         = {Student Paper},
  series       = {Bachelor's Theses in Mathematical Sciences},
  title        = {Parallelization Of The GMRES Method},
  year         = {2016},
}