Numerical Implementations of the Generalized Minimal Residual Method (GMRES)
(2015) In Master's Theses in Mathematical Sciences NUMK01 20151Mathematics (Faculty of Engineering)
- Abstract
- The generalized minimal residual method (GMRES) is an iterative method used to find numerical solutions to non-symmetric linear systems of equations. The method relies on constructing an orthonormal basis of the Krylov space and is thus vulnerable to an imperfect basis caused by computational errors. There have been attempts to address this issue by devising variations of the method that are less sensitive to poorly conditioned problems. The GMRES algorithm is typically used when the dimensions of the problem are very large, thus it is of interest to investigate ways in which the computational and memory cost of running it can be reduced. One method for doing so involves replacing the matrix-vector multiplications with an approximating... (More)
- The generalized minimal residual method (GMRES) is an iterative method used to find numerical solutions to non-symmetric linear systems of equations. The method relies on constructing an orthonormal basis of the Krylov space and is thus vulnerable to an imperfect basis caused by computational errors. There have been attempts to address this issue by devising variations of the method that are less sensitive to poorly conditioned problems. The GMRES algorithm is typically used when the dimensions of the problem are very large, thus it is of interest to investigate ways in which the computational and memory cost of running it can be reduced. One method for doing so involves replacing the matrix-vector multiplications with an approximating function.
This work compares variations of the GMRES algorithm against each other by using it as a solver in simulations mirroring real-world applications. (Less) - Popular Abstract (Swedish)
- Numeriska implementeringar av GMRES-metoden för minimering av residualer:
För att förstå exakt vad som händer när, till exempel, luft strömmar över en flygplansvinge eller när vatten flyter kring ett fartygsskrov, behövs omfattande datorberäkningar. Eftersom storheter som vindhastighet, lufttryck eller temperatur kan variera redan över små avstånd, måste beräkningarna göras i små steg, vilket kräver ett mycket stort antal punkter. Redan för enklare system behövs tusentals beräkningspunkter medan de mer komplicerade kan kräva bortåt en miljon eller ännu fler.
Många problem inom fysiken och den numeriska vetenskapen kan reduceras till system av linjära ekvationer. Dessa system kan ofta bli väldigt stora, så stora att traditionella... (More) - Numeriska implementeringar av GMRES-metoden för minimering av residualer:
För att förstå exakt vad som händer när, till exempel, luft strömmar över en flygplansvinge eller när vatten flyter kring ett fartygsskrov, behövs omfattande datorberäkningar. Eftersom storheter som vindhastighet, lufttryck eller temperatur kan variera redan över små avstånd, måste beräkningarna göras i små steg, vilket kräver ett mycket stort antal punkter. Redan för enklare system behövs tusentals beräkningspunkter medan de mer komplicerade kan kräva bortåt en miljon eller ännu fler.
Många problem inom fysiken och den numeriska vetenskapen kan reduceras till system av linjära ekvationer. Dessa system kan ofta bli väldigt stora, så stora att traditionella metoder för att lösa dem blir opraktiska, till exempel för att tiden för att lösa dem blir för lång, eller för att de kräver väldigt mycket datorminne. Vidare är traditionella metoder i regel så kallade ”direkta lösare”. Detta innebär att de direkt räknar ut den bästa lösningen till problemet som metoden i fråga kan ge. I praktisk användning, till exempel simulering av hur luften strömmar kring en flygplansvinge, är användandet av direkta lösare ofta inte motiverat då det räcker med att hitta en lösning som ligger ”nära nog” den riktiga. Måttet för detta brukar kallas tolerans. I motsats till direkta lösare finns så kallade iterativa lösare vilka arbetar i successiva steg, så kallade iterationer, och approximerar lösningen i varje iteration.
Detta arbete undersöker skillnader mellan olika varianter av en iterativ metod som medger att lösa system av linjära ekvationer till en förutbestämd tolerans. Det är en metod som mycket väl lämpar sig för väldigt stora system, där traditionella metoder är opraktiska. Efter sitt engelska namn kallas metoden för GMRES, ”The Generalized Minimal Residual Method”.
I arbetet undersöktes skillnaderna mellan olika varianter av GMRES, bland annat genom att införa en approximation som avsåg att avsevärt minska kraven på datorminnet. I just detta avseende erhölls ett tydligt negativt resultat då denna verkar försämra lösningens noggrannhet så pass mycket att den blir otillförlitlig. Detta innebär dock inte att denna typ av approximation inte alls skulle kunna användas, utan arbetet avslutas med rekommendationer på ändringar som skulle kunna bidra till att approximationen ger goda resultat. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/student-papers/record/8303042
- author
- Dravins, Ivo LU
- supervisor
- organization
- course
- NUMK01 20151
- year
- 2015
- type
- M2 - Bachelor Degree
- subject
- keywords
- Generalized Minimal Residual Method, Jacobian-free, GMRES, Householder, Givens rotations, Gram-Schmidt
- publication/series
- Master's Theses in Mathematical Sciences
- report number
- LUNFMA-4008-2015
- ISSN
- 1654-6229
- other publication id
- 2015:K18
- language
- English
- id
- 8303042
- date added to LUP
- 2016-04-12 17:01:07
- date last changed
- 2016-04-12 17:01:07
@misc{8303042,
abstract = {{The generalized minimal residual method (GMRES) is an iterative method used to find numerical solutions to non-symmetric linear systems of equations. The method relies on constructing an orthonormal basis of the Krylov space and is thus vulnerable to an imperfect basis caused by computational errors. There have been attempts to address this issue by devising variations of the method that are less sensitive to poorly conditioned problems. The GMRES algorithm is typically used when the dimensions of the problem are very large, thus it is of interest to investigate ways in which the computational and memory cost of running it can be reduced. One method for doing so involves replacing the matrix-vector multiplications with an approximating function.
This work compares variations of the GMRES algorithm against each other by using it as a solver in simulations mirroring real-world applications.}},
author = {{Dravins, Ivo}},
issn = {{1654-6229}},
language = {{eng}},
note = {{Student Paper}},
series = {{Master's Theses in Mathematical Sciences}},
title = {{Numerical Implementations of the Generalized Minimal Residual Method (GMRES)}},
year = {{2015}},
}