Palindromic and Even Eigenvalue Problems - Analysis and Numerical Methods
| dc.contributor.advisor | Mehrmann, Volker | en |
| dc.contributor.author | Schröder, Christian | en |
| dc.contributor.grantor | Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften | en |
| dc.date.accepted | 2008-04-11 | |
| dc.date.accessioned | 2015-11-20T18:03:22Z | |
| dc.date.available | 2008-05-19T12:00:00Z | |
| dc.date.issued | 2008-05-19 | |
| dc.date.submitted | 2008-05-19 | |
| dc.description.abstract | Diese Arbeit handelt von der Analyse und der numerischen Lösung palindromischer und gerader Eigenwertprobleme. So bezeichnet man generalisierte Eigenwertprobleme der Form Ax=lambda A^star x, beziehungsweise Mx=lambda Nx, wobei M=M^star, N=-N^star. Das Symbol A^star bedeutet in diesem Zusammenhang die Transponierte oder die konjugiert komplexe Transponierte der Matrix A. Die Analyse erfolgt anhand von Normalformen von palindromischen bzw. geraden Büscheln unter der der struktur- und spektrumerhaltenden Transformationsklasse, der Kongruenz. Diese Normalformen zeigen, dass das Spektrum der betrachteten Büschel nicht beliebig ist, sondern im Gegenteil gewissen Gesetzmäßigkeiten entsprechen muß. So können die Eigenwerte von palindromischen Büscheln nur in Paaren (lambda, 1/lambda) auftreten, während die Eigenwerte eines geraden Büschels die Paarung (lambda, -lambda) zeigen. Diese Erkenntnisse begründen einen Bedarf an numerischen Verfahren, die diese Paarung garantieren. Da die oben genannten Normalformen aus Stabilitätsgründen nicht für numerische Zwecke nutzbar sind, werden in der Arbeit zusätzlich spektrumsverratende strukturierte Schurformen besprochen, die unter unitären Transformationen erreichbar und damit als Ziel numerischer Verfahren geeignet sind. Außerdem beschäftigt sich die Arbeit mit Stufenformen, die den singulären Teil eines palindromischen oder geraden Büschels vom regulären Teil trennen. Der Rest der Arbeit stellt numerische Verfahren vor, eine strukturierte Schurform eines palindromischen oder geraden Büschels zu berechnen. So wird der palindromische QR Algorithmus entwickelt. Dabei handelt es sich um eine Anpassung des QR-Algorithmusses an das palindromische Eigenwertproblem. Eine implizite Version arbeitet, indem Ausbuchtungen entlang der Antidiagonalen von Anti-Hessenberg-Matrizen gejagt werden. Dieser Algorithmus vereint eine kurze Laufzeit mit starker Stabilität, hat jedoch einen schwerwiegenden Nachteil: Er kann nur auf Anti-Hessenberg-Matrizen angewandt werden. Ein anderer Algorithmus, der auf jedes palindromische oder gerade Problem anwendbar ist, benutzt eine neuartige Matrixzerlegung, die antidreieckige URV-Zerlegung. Diese ordnet einem Tripel gleichgroßer quadratischer Matrizen (A,N=-N^T,S=-S^T) zwei unitäre Matrizen U,V gleicher Größe zu, so dass jedes der Produkte T=U^TNU, R=U^TAV und P=V^TSV antidreieckig ist. Angewandt auf (A,A-A^T,A-A^T) bzw. (M,N,N) ergeben sich die Eigenwerte des zugrunde liegenden palindromischen oder graden Büschels durch einfache Transformationen der Antidiagonalelemente von T,R,P. Als weitere Algorithmen stellt die Dissertation kurz den sogenannten Laubtrick, eine Methode der sukzessiven Verfeinerung (iterative refinement) und einen Hybridalgorithmus vor. Ersterer konstruiert eine palindromische Schurform aus einer unstrukturierten generalisierten Schurform. Dieser Algorithmus ist in der Lage, den gutkonditionierten Teil eines palindromischen oder geraden Problems zu lösen, während der schlechtkonditionierte Anteil (fast) abgespalten wird. Der Refinementalgorithmus verbessert die Qualität einer approximativen Lösung des Problems. Er ist hervorragend geeignet, um das Ergebnis des Laubtricks nachzubearbeiten. Beide Algorithmen, kombiniert mit einer Methode zur Lösung schlechtkonditionierter Probleme, bilden einen Hybridalgorithmus, der die Vorzüge seiner Bestandteile vereint. Schließlich vergleicht die Arbeit die vorgestellten Methoden und entwickelt Kriterien, wie der passende Algorithmus für ein gegebenes Problem ausgewählt werden kann. | de |
| dc.description.abstract | This work covers the analysis and numerical solution of certain structured eigenvalue problems. For square complex matrices A, M, N a generalized eigenvalue problem of the form Ax=lambda A^star x, is called palindromic whereas a generalized eigenvalue problem of the form Mx=lambda Nx, with M=M^star, N=-N^star is called even. Here, A^star can denote the transpose or conjugate transpose of a complex matrix A. The analysis part of the work is carried out in terms of canonical forms for palindromic and even pencils under congruence as congruences preserve both structures. These canonical forms imply that the spectrum of the considered pencils is not arbitrary, but adheres to strict rules. For example, the eigenvalues of palindromic pencils always occur in pairs of the form (lambda, 1/lambda) and the eigenvalues of even pencils come in pairs (lambda, -lambda). This pairing leads to a demand for numerical methods that compute correctly paired eigenvalues. The afore mentioned canonical forms are not suited for numerical computations for stability reasons. As a remedy the thesis examines spectrum revealing structured Schur forms. These are obtained using unitary transformations and are thus well suited as target for numerical methods. Moreover, structured staircase forms are discussed that deflate the singular part off a palindromic or even pencil. The remainder of the work presents numerical methods for palindromic and even eigenvalue problems. The first method is the palindromic QR algorithm, an adaption of the standard QR algorithm to the palindromic setting. An implicit variant of this algorithm proceeds by chasing bulges along the antidiagonal of anti-Hessenberg matrices. It is very efficient and strongly backwards stable, but can be applied to anti-Hessenberg matrices only. The second presented algorithm, which can be applied to every palindromic or even eigenvalue problem, utilizes a novel matrix factorization: the antitriangular URV factorization. Given a triple of quadratic matrices of the same size (A,N=-N^T,S=-S^T), two unitary matrices U,V are found such that each of the three products T=U^TNU, R=U^TAV, and P=V^TSV is antitriangular. Applied to (A,A-A^T,A-A^T) or (M,N,N), the eigenvalues of the underlying palindromic or even pencil can be obtained via simple transformations of the antidiagonal elements of T,R,P. Additionally the work briefly discusses the so-called Laub trick, a structured iterative refinements method, and a hybrid algorithm. The Laub trick constructs a structured Schur form from an unstructured one. It is able to solve the well-conditioned part of a palindromic or even pencil, whereas the badly conditioned part is (almost) deflated. The refinement algorithm improves the quality of an approximate solution. It is excellently suited to post process the result of the Laub trick. Combining these two Algorithms with a method to tackle badly conditioned subproblems results in a hybrid algorithm that shares the advantages of its components. Finally, the presented methods are compared and criteria are given to chose an appropriate algorithm for a given problem. | en |
| dc.identifier.uri | urn:nbn:de:kobv:83-opus-18598 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/2149 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-1852 | |
| dc.language | English | en |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | Normalform | de |
| dc.subject.other | Palindromisch | de |
| dc.subject.other | QR-algorithmus | de |
| dc.subject.other | Strukturiertes Eigenwertproblem | de |
| dc.subject.other | URV-Algorithmus | de |
| dc.subject.other | Canonical form | en |
| dc.subject.other | Palindromic | en |
| dc.subject.other | QR-Algorithm | en |
| dc.subject.other | Structured eigenvalue problem | en |
| dc.subject.other | URV-Algorithm | en |
| dc.title | Palindromic and Even Eigenvalue Problems - Analysis and Numerical Methods | en |
| dc.title.translated | Palindromische und gerade Eigenwertprobleme - Analyse und numerische Methoden | de |
| dc.type | Doctoral Thesis | en |
| dc.type.version | publishedVersion | en |
| tub.accessrights.dnb | free | * |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.identifier.opus3 | 1859 | |
| tub.identifier.opus4 | 1770 | |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
Files
Original bundle
1 - 1 of 1