Parallelization Of The GMRES Method
(2016) In Bachelor's Theses in Mathematical Sciences NUMK01 20161Mathematics (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:
http://lup.lub.lu.se/student-papers/record/8889583
- author
- Görtz, Morgan LU
- supervisor
- organization
- alternative title
- Parallellisering Av GMRES-Metoden
- course
- NUMK01 20161
- year
- 2016
- 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}}, language = {{eng}}, note = {{Student Paper}}, series = {{Bachelor's Theses in Mathematical Sciences}}, title = {{Parallelization Of The GMRES Method}}, year = {{2016}}, }