Return to search

Efficient computation of shifted linear systems of equations with application to PDEs

Thesis (MSc)--Stellenbosch University, 2011. / ENGLISH ABSTRACT: In several numerical approaches to PDEs shifted linear systems of the form (zI - A)x = b, need to be solved for several values of the complex scalar z. Often, these linear systems
are large and sparse. This thesis investigates efficient numerical methods for these systems
that arise from a contour integral approximation to PDEs and compares these methods
with direct solvers.
In the first part, we present three model PDEs and discuss numerical approaches to solve
them. We use the first problem to demonstrate computations with a dense matrix, the
second problem to demonstrate computations with a sparse symmetric matrix and the
third problem for a sparse but nonsymmetric matrix. To solve the model PDEs numerically
we apply two space discrerization methods, namely the finite difference method and the
Chebyshev collocation method. The contour integral method mentioned above is used to
integrate with respect to the time variable.
In the second part, we study a Hessenberg reduction method for solving shifted linear
systems with a dense matrix and present numerical comparison of it with the built-in
direct linear system solver in SciPy. Since both are direct methods, in the absence of
roundoff errors, they give the same result. However, we find that the Hessenberg reduction
method is more efficient in CPU-time than the direct solver. As application we solve a
one-dimensional version of the heat equation.
In the third part, we present efficient techniques for solving shifted systems with a sparse
matrix by Krylov subspace methods. Because of their shift-invariance property, the Krylov
methods allow one to obtain approximate solutions for all values of the parameter, by generating a single approximation space. Krylov methods applied to the linear systems are
generally slowly convergent and hence preconditioning is necessary to improve the convergence.
The use of shift-invert preconditioning is discussed and numerical comparisons with
a direct sparse solver are presented. As an application we solve a two-dimensional version
of the heat equation with and without a convection term. Our numerical experiments
show that the preconditioned Krylov methods are efficient in both computational time and
memory space as compared to the direct sparse solver. / AFRIKAANSE OPSOMMING: In verskeie numeriese metodes vir PDVs moet geskuifde lineêre stelsels van die vorm (zI − A)x = b, opgelos word vir verskeie waardes van die komplekse skalaar z. Hierdie stelsels is dikwels
groot en yl. Hierdie tesis ondersoek numeriese metodes vir sulke stelsels wat voorkom in
kontoerintegraalbenaderings vir PDVs en vergelyk hierdie metodes met direkte metodes
vir oplossing.
In die eerste gedeelte beskou ons drie model PDVs en bespreek numeriese benaderings
om hulle op te los. Die eerste probleem word gebruik om berekenings met ’n vol matriks
te demonstreer, die tweede probleem word gebruik om berekenings met yl, simmetriese
matrikse te demonstreer en die derde probleem vir yl, onsimmetriese matrikse. Om die
model PDVs numeries op te los beskou ons twee ruimte-diskretisasie metodes, naamlik
die eindige-verskilmetode en die Chebyshev kollokasie-metode. Die kontoerintegraalmetode
waarna hierbo verwys is word gebruik om met betrekking tot die tydveranderlike te
integreer.
In die tweede gedeelte bestudeer ons ’n Hessenberg ontbindingsmetode om geskuifde lineêre
stelsels met ’n vol matriks op te los, en ons rapporteer numeriese vergelykings daarvan met
die ingeboude direkte oplosser vir lineêre stelsels in SciPy. Aangesien beide metodes direk
is lewer hulle dieselfde resultate in die afwesigheid van afrondingsfoute. Ons het egter
bevind dat die Hessenberg ontbindingsmetode meer effektief is in terme van rekenaartyd in
vergelyking met die direkte oplosser. As toepassing los ons ’n een-dimensionele weergawe
van die hittevergelyking op.
In die derde gedeelte beskou ons effektiewe tegnieke om geskuifde stelsels met ’n yl matriks op te los, met Krylov subruimte-metodes. As gevolg van hul skuifinvariansie eienskap,
laat die Krylov metodes mens toe om benaderde oplossings te verkry vir alle waardes van
die parameter, deur slegs een benaderingsruimte voort te bring. Krylov metodes toegepas
op lineêre stelsels is in die algemeen stadig konvergerend, en gevolglik is prekondisionering
nodig om die konvergensie te verbeter. Die gebruik van prekondisionering gebasseer
op skuif-en-omkeer word bespreek en numeriese vergelykings met direkte oplossers word
aangebied. As toepassing los ons ’n twee-dimensionele weergawe van die hittevergelyking
op, met ’n konveksie term en daarsonder. Ons numeriese eksperimente dui aan dat die
Krylov metodes met prekondisionering effektief is, beide in terme van berekeningstyd en
rekenaargeheue, in vergelyking met die direkte metodes.

Identiferoai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:sun/oai:scholar.sun.ac.za:10019.1/17827
Date12 1900
CreatorsEneyew, Eyaya Birara
ContributorsWeideman, J. A. C., Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences.
PublisherStellenbosch : Stellenbosch University
Source SetsSouth African National ETD Portal
Languageen_ZA
Detected LanguageEnglish
TypeThesis
Format67 p. : ill.
RightsStellenbosch University

Page generated in 0.0023 seconds