Approximate Solution of Non-Symmetric Generalized Eigenvalue Problems and Linear Matrix Equations on HPC Platforms
Martin Köhler
Diese Publikation zitieren
Martin Köhler, Approximate Solution of Non-Symmetric Generalized Eigenvalue Problems and Linear Matrix Equations on HPC Platforms (2022), Logos Verlag, Berlin, ISBN: 9783832585129
11
Accesses
Accesses
Beschreibung / Abstract
The solution of the generalized eigenvalue problem is one of the computationally most challenging operations in the field of numerical linear algebra. A well known algorithm for this purpose is the QZ algorithm. Although it has been improved for decades and is available in many software packages by now, its performance is unsatisfying for medium and large scale problems on current computer architectures.
In this thesis, a replacement for the QZ algorithm is developed. The design of the new spectral divide and conquer algorithms is oriented towards the capabilities of current computer architectures, including the support for accelerator devices. The thesis describes the co-design of the underlying mathematical ideas and the hardware aspects.
Closely connected with the generalized eigenvalue value problem, the solution of Sylvester-like matrix equations is the concern of the second part of this work. Following the co-design approach, introduced in the first part of this thesis, a flexible framework covering (generalized) Sylvester, Lyapunov, and Stein equations is developed. The combination of the new algorithms for the generalized eigenvalue problem and the Sylvester-like equation solves problems within an hour, whose solution took several days incorporating the QZ and the Bartels-Stewart algorithm.
In this thesis, a replacement for the QZ algorithm is developed. The design of the new spectral divide and conquer algorithms is oriented towards the capabilities of current computer architectures, including the support for accelerator devices. The thesis describes the co-design of the underlying mathematical ideas and the hardware aspects.
Closely connected with the generalized eigenvalue value problem, the solution of Sylvester-like matrix equations is the concern of the second part of this work. Following the co-design approach, introduced in the first part of this thesis, a flexible framework covering (generalized) Sylvester, Lyapunov, and Stein equations is developed. The combination of the new algorithms for the generalized eigenvalue problem and the Sylvester-like equation solves problems within an hour, whose solution took several days incorporating the QZ and the Bartels-Stewart algorithm.
Inhaltsverzeichnis
- BEGINN
- 1 Introduction
- 1.1 Motivation
- 1.2 Outline of the Thesis
- 1.3 Target Computer Architectures
- 1.4 Related own Publications
- 2 Mathematical Basics of the Generalized Eigenvalue Problem
- 2.1 Invariant Subspaces and Deflation
- 2.2 Generalized Schur Decomposition
- 2.3 Reordering of Eigenvalues
- 2.4 Transformation of Eigenvalues
- 3 Spectral Divide and Conquer Algorithms
- 3.1 Basic Concept
- 3.2 Deflating Subspaces via the Matrix Sign Function
- 3.3 Deflating Subspaces via the Matrix Disc Function
- 4 Implementation on Current Hardware
- 4.1 Divide-Shift/Scale-and-Conquer Algorithms
- 4.2 Computation of the Generalized Matrix Sign Function
- 4.3 Computation of the Matrix Disc Function
- 5 Numerical Experiments for the Eigenvalue Problem
- 5.1 Hardware and Software Setup
- 5.2 Performance of the Building Blocks
- 5.3 Computing the Generalized Schur Decomposition
- 6 Application to Sylvester-Type Matrix Equations
- 6.1 Mathematical Basics
- 6.2 Classic Direct Solution Techniques
- 6.3 Block Algorithms and their Implementation
- 6.4 Triangular Solvers and the Approximated Schur Decomposition
- 7 Numerical Experiments for the Matrix Equations
- 7.1 Hardware and Software Setup
- 7.2 Performance of Triangular Solvers
- 7.3 Solution of Generalized Lyapunov Equations
- 8 Conclusions
- A Explanatory Experiments
- A.1 Examples in Chapter 4
- A.2 Examples in Chapter 6
- Bibliography