Digitala Vetenskapliga Arkivet

Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
The waveguide eigenvalue problem and the tensor infinite Arnoldi method
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Numerisk analys, NA. KTH, Centra, SeRC - Swedish e-Science Research Centre.ORCID-id: 0000-0001-9443-8772
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Numerisk analys, NA. KTH, Centra, SeRC - Swedish e-Science Research Centre.ORCID-id: 0000-0002-6990-445X
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Numerisk analys, NA. KTH, Centra, SeRC - Swedish e-Science Research Centre.ORCID-id: 0000-0002-6321-8619
2017 (engelsk)Inngår i: SIAM Journal on Scientific Computing, ISSN 1064-8275, E-ISSN 1095-7197, Vol. 39, nr 3, s. A1062-A1088Artikkel i tidsskrift (Fagfellevurdert) Published
Abstract [en]

We present a new computational approach for a class of large-scale nonlinear eigenvalue problems (NEPs) that are nonlinear in the eigenvalue. The contribution of this paper is two fold. We derive a new iterative algorithm for NEPs, the tensor infinite Arnoldi method (TIAR), which is applicable to a general class of NEPs, and we show how to specialize the algorithm to a specific NEP: the waveguide eigenvalue problem. The waveguide eigenvalue problem arises from a finite-element discretization of a partial differential equation used in the study waves propagating in a periodic medium. The algorithm is successfully applied to accurately solve benchmark problems as well as complicated waveguides. We study the complexity of the specialized algorithm with respect to the number of iterations "m" and the size of the problem "n", both from a theoretical perspective and in practice. For the waveguide eigenvalue problem, we establish that the computationally dominating part of the algorithm has complexity O(nm^2+sqrt(n)m^3). Hence, the asymptotic complexity of TIAR applied to the waveguide eigenvalue problem, for n→ ∞, is the same as for Arnoldi’s method for standard eigenvalue problems.

sted, utgiver, år, opplag, sider
2017. Vol. 39, nr 3, s. A1062-A1088
Emneord [en]
nonlinear eigenvalue problems, iterative methods, Krylov methods, Helmholtz equation, Arnoldi’s method
HSV kategori
Forskningsprogram
Tillämpad matematik och beräkningsmatematik, Numerisk analys
Identifikatorer
URN: urn:nbn:se:kth:diva-263719DOI: 10.1137/15M1044667ISI: 000404763200024Scopus ID: 2-s2.0-85020429543OAI: oai:DiVA.org:kth-263719DiVA, id: diva2:1369184
Forskningsfinansiär
Swedish Research Council, 621-2013-4640
Merknad

QC 20191111

Tilgjengelig fra: 2019-11-11 Laget: 2019-11-11 Sist oppdatert: 2024-03-18bibliografisk kontrollert
Inngår i avhandling
1. Krylov methods for nonlinear eigenvalue problems and matrix equations
Åpne denne publikasjonen i ny fane eller vindu >>Krylov methods for nonlinear eigenvalue problems and matrix equations
2020 (engelsk)Doktoravhandling, med artikler (Annet vitenskapelig)
Abstract [en]

Nonlinear eigenvalue problems (NEPs) arise in many fields of science and engineering. Such problems are often defined by large matrices, which have specific structures, such as being sparse, low-rank, etc. Like the linear eigenvalue problem, the eigenvector appears in a linear form, whereas the eigenvalue appears in a nonlinear form. This feature allows for an extension of several methods, which are originally derived for the linear eigenvalue problem, to the nonlinear case. Among these methods, Krylov algorithms have been successfully extended in various ways. These methods are designed to take advantage of the matrix structures mentioned above. In this thesis, we present two Krylov-based methods for solving NEPs: the tensor infinite Arnoldi (TIAR), with its restarting variant, and infinite Lanczos (ILAN). We illustrate the flexibility of TIAR by adapting it for solving a NEP which comes from the study of waves propagating in periodic mediums. Despite the fact that Krylov methods are, in a sense, globally convergent, the convergence to the targeted eigenvalues, in certain cases, may be slow. When an accurate solution is required, the obtained approximations are refined with methods which have higher convergence order, e.g., Newton-like methods, which are also analyzed in this thesis. In the context of eigenvalue computation, the framework used to analyse Newton methods can be combined with the Keldysh theorem in order to better characterize the convergence factor. We also show that several well-established methods, such as residual inverse iteration and Ruhe’s method of successive linear problems, belong to the class of Newton-like methods. In this spirit, we derive a new quasi-Newton method, which is, in terms of convergence properties, equivalent to residual inverse iteration, but does not require the solution of a nonlinear system per iteration. The mentioned methods are implemented in NEP-PACK, which is a registered Julia package for NEPs that we develop. This package consists of: many state-of-the-art, but also well-established, methods for solving NEPs, a vast problem collection, and types and structures to efficiently represent and do computations with NEPs.Many problems in control theory, and many discretized partial differential equations, can be efficiently solved if formulated as matrix equations. Moreover, matrix equations arise in a very large variety of areas as intrinsic problems. In our framework, for certain applications, solving matrix equations is a part of the process of solving a NEP. In this thesis we derive a preconditioning technique which is applicable to linear systems which can be formulate as generalized Sylvester equation. More precisely, we assume that the matrix equation can be formulated as the sum of a Sylvester operator and another term which can be low-rank approximated. Such linear systems arise, e.g., when solving certain NEPs which come from wave propagation problems.We also derive an algorithm, which consists of applying a Krylov method directly to the the matrix equation rather then to the vectorized linear system, that exploits certain structures in the matrix coefficients.

Abstract [sv]

Icke-linjära egenvärdesproblem, förkortat NEP från engelskans nonlinear eigenvalue problem, uppstår inom många områden inom vetenskap och teknik. Sådana problem definieras ofta av stora matriser med specifika strukturer, såsom gleshet, låg rang osv. Liksom det i linjära egenvärdesproblemet är beroendet på egenvektorn linjärt, medan beroendet på egenvärdet är icke-linjärt. Denna egenskap möjliggör en utvidgning av flera metoder, som ursprungligen härleds för det linjära egenvärdesproblemet, till det icke-linjära fallet. Bland dessa metoder har Krylov-metoder framgångsrikt vidareutvecklats på olika sätt. Dessa metoder är utformade för att dra fördel av de ovan nämnda matrisstrukturerna. I den här avhandlingen presenterar vi två Krylov-baserade metoder för att lösa NEP: tensor Infinite Arnoldi (TIAR), med en variant som möjliggör omstart, och Infinite Lanczos (ILAN). Vi illustrerar flexibiliteten i TIAR genom att anpassa den till att lösa en NEP som kommer från studien av vågor som sprider sig i periodiska medier.Även om Krylov-metoder på sätt och vis är globalt konvergenta, kan konvergensen till de önskade egenvärdena i vissa fall vara långsam. När en noggrann lösning erfordras kan de erhållna approximationerna förfinas med metoder som har högre konvergensordning, t.ex. Newton-liknande metoder, som också analyseras i denna avhandling. I detta sammanhang kan ramverket som används för att analysera Newton-metoder kombineras med Keldysh sats för att bättre karakterisera konvergensfaktorn. Vi visar också att flera väletablerade metoder, såsom residual inversiteration och Ruhes metod för successiva linjära problem, tillhör klassen Newton-liknande metoder. I denna anda erhåller vi en ny quasi-Newton metod som motsvarar residual inversiteration, när det gäller konvergensegenskaper, men inte kräver lösning av en olinjär ekvation per iteration.De nämnda metoderna är implementerade i NEP-PACK, som är ett registrerat Julia-paket för NEP som vi har utvecklat. Detta paket består av många nyutvecklade samt väletablerade metoder för att lösa NEP, en stor problemsamling samt typer och strukturer för att effektivt representera och göra beräkningar med NEP.Många problem inom styrteori, samt många diskretiserade partiella differentialekvationer, kan lösas effektivt om de formuleras som matrisekvationer. Dessutom uppstår matrisekvationer som delproblem i ett mycket stort antal områden. I vårt ramverk, är lösning av matrisekvationer en del av processen för att lösa en NEP i vissa tillämpningar. I denna avhandling härleder vi en förkonditioneringsteknik som är tillämplig på vissa linjära system vilka kan formuleras som en generaliserad Sylvesterekvation. Mer exakt antar vi att matrisekvationen kan skrivas som summan av en Sylvesteroperator och en annan term som kan approximeras med en operator med låg rang. Sådana linjära system uppstår, t.ex., vid lösning av vissa NEP som kommer från vågutbredningsproblem. Vi presenterar också en algoritm, som består av att tillämpa en Krylov-metod direkt på matrisekvationen snarare än på det vektoriserade linjära systemet, vilken utnyttjar vissa strukturer i matriskoefficienterna.

sted, utgiver, år, opplag, sider
Stockholm: KTH Royal Institute of Technology, 2020. s. 57
Serie
TRITA-SCI-FOU ; 2019:59
HSV kategori
Forskningsprogram
Tillämpad matematik och beräkningsmatematik, Numerisk analys
Identifikatorer
urn:nbn:se:kth:diva-266368 (URN)978-91-7873-392-7 (ISBN)
Disputas
2020-02-11, F3, Lindstedtsvägen 26, Sing-Sing, floor 2, KTH Campus, Stockholm, 10:00 (engelsk)
Opponent
Veileder
Tilgjengelig fra: 2020-01-09 Laget: 2020-01-09 Sist oppdatert: 2022-06-26bibliografisk kontrollert

Open Access i DiVA

fulltext(862 kB)158 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 862 kBChecksum SHA-512
7d800fa1df8ea0fc1e5abf372197461aa20086f3742aa9889b418fbd86a40f07572aaa89f9917e9cb29e035eb47d096b23a84eb28a72883e66e265956d0058ec
Type fulltextMimetype application/pdf

Andre lenker

Forlagets fulltekstScopus

Søk i DiVA

Av forfatter/redaktør
Jarlebring, EliasMele, GiampaoloRunborg, Olof
Av organisasjonen
I samme tidsskrift
SIAM Journal on Scientific Computing

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 158 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

doi
urn-nbn

Altmetric

doi
urn-nbn
Totalt: 114 treff
RefereraExporteraLink to record
Permanent link

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