Numerical methods for Sylvester-type matrix equations and nonlinear eigenvalue problems

• Linear matrix equations and nonlinear eigenvalue problems (NEP) appear in a wide variety of applications in science and engineering. Important special cases of the former are the Lyapunov equation, the Sylvester equation, and their respective generalizations. These appear, e.g., as Gramians to linear and bilinear systems, in computations involving block-triangularization of matrices, and in connection with discretizations of some partial differential equations. The NEP appear, e.g., in stability analysis of time-delay systems, and as results of transformations of linear eigenvalue problems.This thesis mainly consists of 4 papers that treats the above mentioned computational problems, and presents both theory and methods. In paper A we consider a NEP stemming from the discretization of a partial differential equation describing wave propagation in a waveguide. Some NEP-methods require in each iteration to solve a linear system with a fixed matrix, but different right-hand sides, and with a fine discretization, this linear solve becomes the bottleneck. To overcome this we present a Sylvester-based preconditioner, exploiting the Sherman–Morrison–Woodbury formula.Paper B treats the generalized Sylvester equation and present two main results: First, a characterization that under certain assumptions motivates the existence of low-rank solutions. Second, a Krylov method applicable when the matrix coefficients are low-rank commuting, i.e., when the commutator is of low rank.In Paper C we study the generalized Lyapunov equation. Specifically, we extend the motivation for applying the alternating linear scheme (ALS) method, from the stable Lyapunov equation to the stable generalized Lyapunov equation. Moreover, we show connections to H2-optimal model reduction of associated bilinear systems, and show that ALS can be understood to construct a rank-1 model reduction subspace to such a bilinear system related to the residual. We also propose a residual-based generalized rational-Krylov-type subspace as a solver for the generalized Lyapunov equation.The fourth paper, Paper D, connects the NEP to the two-parameter eigenvalue problem. The latter is a generalization of the linear eigenvalue problem in the sense that there are two eigenvalue-eigenvector equations, both depending on two scalar variables. If we fix one of the variables, then we can use one of the equations, which is then a generalized eigenvalue problem, to solve for the other variable. In that sense, the solved-for variable can be understood as a family of functions of the first variable. Hence, it is a variable elimination technique where the second equation can be understood as a family of NEPs. Methods for NEPs can thus be adapted and exploited to solve the original problem. The idea can also be reversed, providing linearizations for certain NEPs.

• Linjära matrisekvationer är en vanligt förekommande variant av linjära ekvationssystem. Viktiga specialfall är Lyapunovekvationen och Sylvesterekvationen, samt deras respektive generaliseringar. Dessa ekvationer uppstår till exempel som karakteriseringar av Gramianer till linjära och bilinjära dynamiska system, i beräkningar som innebär blocktriangularisering av matriser, och vid diskretiseringar av vissa partiella differentialekvationer. Det icke-linjära egenvärdesproblemet, från engelskan förkortat NEP, är en generalisering av det linjära egenvärdesproblemet för en matris. I det icke-linjära fallet tillåts matrisens beroende på den skalära parametern att vara just icke-linjärt. Formellt betraktas problemet som en funktion vars definitionsmängd är en delmängd av de komplexa talen, och vars värdemängd är (en delmängd av de) komplexvärda matriserna. Problemet kan beskrivas som att hitta värden, så kallade egenvärden, som gör att den tillhörande matrisen i värdemängden är singulär; en vektor i nollrummet kallas för en egenvektor. Notera att beroendet på egenvektorn är linjärt. Tillämpningar inkluderar bland annat studier av dynamiska system med tidsfördröjning, samt vid transformationer av linjära egenvärdesproblem. En annan generalisering av egenvärdesproblemet är två-parameters egenvärdesproblemet vilket består av två matrisvärda funktioner som båda beror på två parametrar. Målet är att hitta par av parametrar så att båda matriserna är singulära.Denna avhandling är en sammanläggningsavhandling och består i huvudsak av 4 artiklar. Dessa artiklar berör både praktiska och teoretiska aspekter av de ovan nämnda beräkningsproblemen. I artikel A betraktas ett NEP som härstammar från en partiell differentialekvation, vilken beskriver vågutbredning i en vågledare. På det diskretiserade problemet tillämpas residual inversiteration (residual inverse iteration). Metoden kräver att man löser likartade linjära ekvationssystem många gånger, med olika högerled. När diskretiseringen blir noggrannare blir beräkningen av lösningen till det linjära ekvationssystemen en flaskhals. För att komma runt detta presenteras en Sylvester-baserad förkonditionerare som utnyttjar Sherman–Morrison–Woodburys formel för invertering av matriser med lågrangstermer.Artikel B behandlar den generaliserade Sylvesterekvationen och har två huvudresultat: Ett resultat är en karakterisering som under vissa antaganden motiverar existensen av lösningar som kan approximeras med matriser med låg rang. Resultatet är viktigt då många metoder för storskaliga problem har som mål att hitta en approximation av låg rang. Ett annat resultat är en Krylovmetod som kan användas när matriskoefficienterna lågrangskommuterar, d.v.s. när kommutatorn är en matris av låg rang.I artikel C undersöker vi den generaliserade Lyapunovekvationen. ALS-metoden, från engelskan alternating linear scheme, är en girig algoritm som presenterats i literaturen, och som iterativt utökar approximationen med en matris av rang 1. Denna utökning definieras utifrån att den är ett lokalt minimum av felet, när det senare mäts i en relaterad energinorm. Vi presenterar en utvidgning av den teoretiska motiveringen till användandet av ALS-metoden, från den stabila Lyapunovekvationen till den stabila generaliserade Lyapunovekvationen. Vi visar också på kopplingar till H2-optimal modellreduktion för bilinjära dynamiska system, och hur rang-1-uppdateringarna i ALS-metoden kan ses som lokalt H2-optimala till relaterade modellreduktionsproblem. Vi presenterar även varianter av den rationella Krylovmetoden som är anpassade till den generaliserade Lyapunovekvationen.Den fjärde artikeln, artikel D, presenterar en koppling mellan två-parameters egenvärdesproblemet och NEP. Genom att använda den ena ekvationen för att genomföra en variabeleliminering kan den andra skrivas som en familj av NEP:ar. Elimineringen sker på bekostnad av att ett generaliserat egenvärdesproblem behöver lösas för varje funktionsevaluering av NEP:en. Metoder för NEP kan på så sätt anpassas för att lösa två-parameters egenvärdesproblemet. Icke-linjärisering kan även tillämpas i omvänd riktning och kan på så sätt leda till linjäriseringar av vissa NEP:ar.

Ämnesord

NATURVETENSKAP  -- Matematik -- Beräkningsmatematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Computational Mathematics (hsv//eng)

Nyckelord

Matrix equations

Lyapunov equation

Sylvester equation

nonlinear eigenvalue problems

two-parameter eigenvalue problems

Krylov methods

iterative methods

preconditioning

projection methods

Matrisekvationer

Lyapunovekvationen

Sylvesterekvationen

ickelinjära egenvärdesproblem

två-parameters egenvärdesproblem

Krylovmetoder

iterativa metoder

förkonditionering

projektionsmetoder

Tillämpad matematik och beräkningsmatematik

Applied and Computational Mathematics

Optimization and Systems Theory

Optimeringslära och systemteori

Numerical Analysis

Numerisk analys

Publikations- och innehållstyp

vet (ämneskategori)

dok (ämneskategori)