kth.sePublikationer
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Numerical methods for parameterized linear systems
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Numerisk analys, NA. KTH, Centra, SeRC - Swedish e-Science Research Centre.ORCID-id: 0000-0002-1488-9379
2024 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
Abstract [en]

Solving linear systems of equations is a fundamental problem in engineering. Moreover, applications involving the solution to linear systems arise in the social sciences, business, and economics. Specifically, the research conducted in this dissertation explores solutions to linear systems where the system matrix depends nonlinearly on a parameter. The parameter can be a scalar or a vector, and a change in the parameter results in a change in the solution. Such a setting arises in the study of partial differential equations and time-delay systems, and we are interested in obtaining solutions corresponding to many values of the parameter simultaneously. The methods developed in this thesis can also be used to solve parameter estimation problems. Furthermore, software has been developed and is available online. 

This thesis consists of four papers and presents both algorithms and theoretical analysis. In Paper A, a linearization based on an infinite Taylor series expansion is considered. Specifically, the linearized system is a shifted parameterized system, and the parameter is a scalar. The GMRES method is used to solve the systems corresponding to many values of the parameter, and only one Krylov subspace basis matrix is required. Convergence analysis is based on solutions to a nonlinear eigenvalue problem and the magnitude of the parameter. Notably, the algorithm is carried out in a finite number of computations. 

The approach in Paper B is based on a preconditioned linearized system solved using the inexact GMRES method. In this setting, the linearization incorporates all terms in an infinite Taylor series expansion, and the preconditioner is applied approximately using iterative methods. Solutions corresponding to many values of the scalar parameter are generated from one subspace, and this is done in a finite number of linear algebra operations. Theoretical analysis, based on the error in the application of the preconditioner and the magnitude of the parameter, leads to a bound on the residual. 

Paper C proposes a short recurrence Krylov subspace method for solving linear systems that depend on a scalar parameter. In particular, a Chebyshev approximation is used to construct a linearization, and the linearized system is solved in a Bi-CG setting. Additionally, shift-and-invert preconditioning leads to fast convergence of the Krylov method for many different values of the parameter. An inexact variant of the method is also derived and analyzed. 

In Paper D, a reduced order model is constructed from snapshots to solve parameterized linear systems. Specifically, the parameter is a vector of dimension 2, and the sampling is performed on a sparse grid using the method proposed in Paper C. A tensor decomposition is utilized to build the model. Approaches of this kind are not always successful, and it is not known a priori if a decomposition will converge on a given set of snapshots. This work offers a novel way to generate a new set of snapshots in the same parameter space, to be used if the decomposition does not converge, with little extra computation. 

Abstract [sv]

Att lösa linjära ekvationssystem är ett grundläggande tekniskt problem. Dessutom uppstår tillämpningar som involverar lösningen av linjära system inom samhällsvetenskap och ekonomi. Specifikt utforskar denna avhandling lösningar till linjära system där systemmatrisen beror olinjärt på en parameter. Parametern kan vara en skalär eller en vektor, och en förändring i parametern resulterar i en förändring i lösningen. En sådant scenario uppstår vid studiet av partiella differentialekvationer och tidsfördröjningssystem, och vi är intresserade av att erhålla lösningar som motsvarar många värden på parametern samtidigt. De metoder som utvecklats i denna avhandling kan också användas för att lösa problem med parameteruppskattning. Ytterligare har programvara utvecklats och är tillgänglig online.

Denna avhandling består av fyra artiklar och presenterar både algoritmer och teoretisk analys. I artikel A behandlas en linjärisering baserad på en oändlig Taylor-serieexpansion. Specifikt är det linjäriserade systemet ett skiftat parametriserat system, och parametern är en skalär. Systemet löses med GMRES-metoden, och endast en Krylov-basmatris krävs. Konvergensanalys baseras på lösningar till ett olinjärt egenvärdesproblem och parameterns storlek. Noterbart är att algoritmen utförs i ett ändligt antal beräkningar.

Tillvägagångssättet i artikel B är baserat på ett förkonditionerat linjäriserat system löst med den inexakta GMRES-metoden. I den här kontexten innehåller linjäriseringen alla termer i en oändlig Taylor-serieexpansion, och förkonditioneringen appliceras på ett approximativt sätt med iterativa metoder. Lösningar som motsvarar många värden på den skalära parametern genereras från ett delrum, och detta görs i ett ändligt antal linjära algebraoperationer. Teoretisk analys, baserad på felet i appliceringen av förkonditioneraren och storleken på parametern, leder till en övre begränsning på residualens storlek.

Artikel C föreslår en Krylovbaserad rekursionsmetod med få termer för att lösa linjära system som är beroende av en skalär parameter. Specifikt används en Chebyshev-approximation för att konstruera en linjärisering, och det linjäriserade systemet löses med den bikonjugerade gradient-metoden. Dessutom leder förkonditionering med skifte och invertering till snabb konvergens av Krylov-metoden för många olika värden på parametern. En inexakt variant av metoden härleds och analyseras också.

I artikel D konstrueras en reducerad ordningsmodell från sampel av modellen för att lösa parametriserade linjära system. Specifikt är parametern en vektor med dimensionen 2, och samplingen utförs på ett glest rutnät med den metod som föreslås i artikel C. En tensorfaktorisering används för att bygga modellen. Tillvägagångssätt av denna typ är inte alltid framgångsrika, och det är inte känt på förhand om en tensorfaktorisering kommer att konvergera för en given uppsättning av sampel. Detta arbete presenterar ett nytt sätt att generera en ny uppsättning sampel i samma parameterrum till en låg extra kostnad. De nya lösningar kan användas om tensorfaktoriseringen misslyckas. 

Ort, förlag, år, upplaga, sidor
Stockholm: KTH Royal Institute of Technology, 2024.
Serie
TRITA-SCI-FOU ; 2024:08
Nyckelord [en]
Parameterized linear systems, Krylov subspace methods, preconditioning, tensor decompositions, shifted linear systems, parameterized partial differential equations, time-delay systems, transfer functions, parameter estimation problems
Nyckelord [sv]
Parameteriserade linjära system, Krylov-metoder, förkonditionering, tensordekomposition, skiftade linjära system, parametriserade partiella differentialekvationer, tidsfördröjningssystem, överföringsfunktioner, parameteruppskattningsproblem
Nationell ämneskategori
Beräkningsmatematik
Forskningsämne
Tillämpad matematik och beräkningsmatematik, Numerisk analys
Identifikatorer
URN: urn:nbn:se:kth:diva-344999ISBN: 978-91-8040-845-5 (tryckt)OAI: oai:DiVA.org:kth-344999DiVA, id: diva2:1849078
Disputation
2024-05-07, F3, Lindstedtsvägen 26, 14:00 (Engelska)
Opponent
Handledare
Anmärkning

QC 2024-04-08

Tillgänglig från: 2024-04-08 Skapad: 2024-04-05 Senast uppdaterad: 2024-04-15Bibliografiskt granskad
Delarbeten
1. Infinite GMRES for Parameterized Linear Systems
Öppna denna publikation i ny flik eller fönster >>Infinite GMRES for Parameterized Linear Systems
2022 (Engelska)Ingår i: SIAM Journal on Matrix Analysis and Applications, ISSN 0895-4798, E-ISSN 1095-7162, Vol. 43, nr 3, s. 1382-1405Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We consider linear parameterized systems A(mu)x(mu) = b for many different mu, where A is large and sparse and depends nonlinearly on mu. Solving such systems individually for each mu would require great computational effort. In this work we propose to compute a partial parameterization (x) over tilde approximate to x(mu), where (x) over tilde(mu) is cheap to evaluate for many mu. Our methods are based on the observation that a companion linearization can be formed where the dependence on mu is only linear. In particular, methods are presented that combine the well-established Krylov subspace method for linear systems, GMRES, with algorithms for nonlinear eigenvalue problems (NEPs) to generate a basis for the Krylov subspace. Within this new approach, the basis matrix is constructed in three different ways, using a tensor structure and exploiting that certain problems have low-rank properties. The methods are analyzed analogously to the standard convergence theory for the method GMRES for linear systems. More specifically, the error is estimated based on the magnitude of the parameter mu and the spectrum of the linear companion matrix, which corresponds to the reciprocal solutions to the corresponding NEP. Numerical experiments illustrate the competitiveness of the methods for large-scale problems. The simulations are reproducible and publicly available online.

Ort, förlag, år, upplaga, sidor
Society for Industrial & Applied Mathematics (SIAM), 2022
Nyckelord
parameterized linear systems, Krylov methods, companion linearization, shifted linear systems, infinite Arnoldi, low-rank matrices
Nationell ämneskategori
Beräkningsmatematik
Identifikatorer
urn:nbn:se:kth:diva-320420 (URN)10.1137/21M1410324 (DOI)000861196300015 ()2-s2.0-85138468029 (Scopus ID)
Anmärkning

QC 20221107

Tillgänglig från: 2022-11-07 Skapad: 2022-11-07 Senast uppdaterad: 2024-04-05Bibliografiskt granskad
2. Preconditioned Infinite GMRES for Parameterized Linear Systems
Öppna denna publikation i ny flik eller fönster >>Preconditioned Infinite GMRES for Parameterized Linear Systems
2024 (Engelska)Ingår i: SIAM Journal on Scientific Computing, ISSN 1064-8275, E-ISSN 1095-7197, Vol. 46, nr 2, s. S120-S141Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We are interested in obtaining solutions to parameterized linear systems of the form A(mu)x(mu) = b for many values of the parameter mu. Here A(mu) is large, sparse, and nonsingular with a nonlinear, analytic dependence on mu. Our approach approximates the solution to a linearized system in a flexible GMRES setting [Y. Saad, SIAM J. Sci. Comput., 14 (1993), pp. 461-469], where the linearization is based on a companion matrix similar to the operator in the infinite Arnoldi method [E. Jarlebring, W. Michiels, and K. Meerbergen, Numer. Math., 122 (2012), pp. 169-195]. This novel approach applies the action of a preconditioner inexactly, providing performance improvement over the method infinite GMRES [Jarlebring and Correnty, SIAM J. Matrix Anal. Appl., 43 (2022), pp. 1382-1405] without a loss of accuracy in general. The method returns a function (x) over tilde(mu) which is cheap to evaluate for different mu. We show that the error of our method is estimated based on the magnitude of the parameter mu, the inexactness of the preconditioning, and the spectrum of the companion matrix. Numerical examples from a finite element discretization of a Helmholtz equation with a parameterized material coefficient illustrate the competitiveness of our approach. The software used in the simulations is publicly available online, and all the experiments are reproducible. 

Ort, förlag, år, upplaga, sidor
Society for Industrial & Applied Mathematics (SIAM), 2024
Nyckelord
inexact preconditioning, parameterized linear systems, Krylov methods, companion linearization, shifted linear systems, infinite Arnoldi, inner stopping criteria
Nationell ämneskategori
Beräkningsmatematik
Forskningsämne
Tillämpad matematik och beräkningsmatematik, Numerisk analys
Identifikatorer
urn:nbn:se:kth:diva-344990 (URN)10.1137/22M1502380 (DOI)2-s2.0-85192672679 (Scopus ID)
Anmärkning

QC 20240409

Tillgänglig från: 2024-04-05 Skapad: 2024-04-05 Senast uppdaterad: 2024-05-24Bibliografiskt granskad
3. Preconditioned Chebyshev BiCG method for parameterized linear systems
Öppna denna publikation i ny flik eller fönster >>Preconditioned Chebyshev BiCG method for parameterized linear systems
2023 (Engelska)Ingår i: Electronic Transactions on Numerical Analysis, E-ISSN 1068-9613, Vol. 58, s. 629-656Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We consider the problem of approximating the solution to A(μ)x(μ) = b for many different values of the parameter μ. Here, A(μ) is large, sparse, and nonsingular with a nonlinear dependence on μ. Our method is based on a companion linearization derived from an accurate Chebyshev interpolation of A(μ) on the interval [-a; a], a 2 R+, inspired by Effenberger and Kressner [BIT, 52 (2012), pp. 933-951]. The solution to the linearization is approximated in a preconditioned BiCG setting for shifted systems, as proposed in Ahmad et al. [SIAM J. Matrix Anal. Appl., 38 (2017), pp. 401-424], where the Krylov basis matrix is formed once. This process leads to a short-term recurrence method, where one execution of the algorithm produces the approximation of x(μ) for many different values of the parameter μ ∈ [-a; a] simultaneously. In particular, this work proposes one algorithm which applies a shift-and-invert preconditioner exactly as well as an algorithm which applies the preconditioner inexactly based on the work by Vogel [Appl. Math. Comput., 188 (2007), pp. 226-233]. The competitiveness of the algorithms is illustrated with large-scale problems arising from a finite element discretization of a Helmholtz equation with a parameterized material coefficient. The software used in the simulations is publicly available online, and thus all our experiments are reproducible.

Ort, förlag, år, upplaga, sidor
Osterreichische Akademie der Wissenschaften, Verlag, 2023
Nyckelord
Chebyshev interpolation, companion linearization, inexact preconditioning, Krylov subspace methods, parameterized Helmholtz equation, parameterized linear systems, shifted linear systems, short-term recurrence methods, time-delay systems
Nationell ämneskategori
Beräkningsmatematik Datavetenskap (datalogi)
Identifikatorer
urn:nbn:se:kth:diva-341929 (URN)10.1553/etna_vol58s629 (DOI)2-s2.0-85180534256 (Scopus ID)
Anmärkning

QC 20240108

Tillgänglig från: 2024-01-08 Skapad: 2024-01-08 Senast uppdaterad: 2024-04-05Bibliografiskt granskad
4. Chebyshev HOPGD with sparse grid sampling for parameterized linear systems
Öppna denna publikation i ny flik eller fönster >>Chebyshev HOPGD with sparse grid sampling for parameterized linear systems
(Engelska)Manuskript (preprint) (Övrigt vetenskapligt)
Abstract [en]

We consider approximating solutions to parameterized linear systems of the form A(μ1, μ2)x(μ1, μ2) = b, where (μ1, μ2) ∈ R2. Here the matrix A(μ1, μ2) ∈ Rnxn is nonsingular, large, and sparse and depends nonlinearly on the parameters μ1 and μ2. Specifically, the system arises from a discretization of a partial differential equation and x(μ1,μ2) ∈ Rn, b ∈ Rn. This work combines companion linearization with the Krylov subspace method preconditioned bi-conjugate gradient (BiCG) and a decomposition of a tensor matrix of precomputed solutions, called snapshots. As a result, a reduced order model of x(μ1,μ2) is constructed, and this model can be evaluated in a cheap way for many values of the parameters. Tensor decompositions performed on a set of snapshots can fail to reach a certain level of accuracy, and it is not known a priori if a decomposition will be successful. Moreover, the selection of snapshots can affect both the quality of the produced model and the computation time required for its construction. This new method offers a way to generate a new set of solutions on the same parameter space at little additional cost. An interpolation of the model is used to produce approximations on the entire parameter space, and this method can be used to solve a parameter estimation problem. Numerical examples of a parameterized Helmholtz equation show the competitiveness of our approach. The simulations are reproducible, and the software is available online. 

Nyckelord
Krylov methods, companion linearization, shifted linear systems, reduced order model, tensor decomposition, parameter estimation
Nationell ämneskategori
Beräkningsmatematik
Forskningsämne
Tillämpad matematik och beräkningsmatematik, Numerisk analys
Identifikatorer
urn:nbn:se:kth:diva-344994 (URN)
Anmärkning

QC 20240409

Tillgänglig från: 2024-04-05 Skapad: 2024-04-05 Senast uppdaterad: 2024-04-09Bibliografiskt granskad

Open Access i DiVA

kappa(1019 kB)172 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 1019 kBChecksumma SHA-512
c1c8e083ac35a090aed8016bda10eacb104fdef8f6041a1b31d86f949e01ad016ac987740f6937c49466e27d17312d83a06210b31fa3b0fb034da55b5ea1499f
Typ fulltextMimetyp application/pdf

Person

Correnty, Siobhán

Sök vidare i DiVA

Av författaren/redaktören
Correnty, Siobhán
Av organisationen
Numerisk analys, NASeRC - Swedish e-Science Research Centre
Beräkningsmatematik

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 172 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

isbn
urn-nbn

Altmetricpoäng

isbn
urn-nbn
Totalt: 1599 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf