Numerical methods based on rational Krylov spaces have become an indispensabletool of scientific computing. In this thesis we study rational Krylov spaces by consideringrational Krylov decompositions; matrix relations which, under certain conditions,are associated with these spaces. We investigate the algebraic properties of suchdecompositions and present an implicit Q theorem for rational Krylov spaces.We derive standard and harmonic Ritz extraction strategies for approximatingthe eigenpairs of a matrix and for approximating the action of a matrix functiononto a vector. While these topics have been considered previously, our approachdoes not require the last pole to be infinite, which makes the extraction procedurecomputationally more efficient.Typically, the computationally most expensive component of the rational Arnoldialgorithm for computing a rational Krylov basis is the solution of a large linear systemof equations at each iteration. We explore the option of solving several linear systemssimultaneously, thus constructing the rational Krylov basis in parallel. If this is notdone carefully, the basis being orthogonalized may become poorly conditioned, leadingto numerical instabilities in the orthogonalization process. We introduce the newconcept of continuation pairs which gives rise to a near-optimal parallelization strategythat allows to control the growth of the condition number of this nonorthogonal basis.As a consequence we obtain a more accurate and reliable parallel rational Arnoldialgorithm. The computational benefits are illustrated using our high performance C++implementation.We develop an iterative algorithm for solving nonlinear rational least squaresproblems. The difficulty is in finding the poles of a rational function. For this purpose,at each iteration a rational Krylov decomposition is constructed and a modified linearproblem is solved in order to relocate the poles to new ones. Our numerical resultsindicate that the algorithm, called RKFIT, is well suited for model order reductionof linear time invariant dynamical systems and for optimisation problems related toexponential integration. Furthermore, we derive a strategy for the degree reduction ofthe approximant obtained by RKFIT. The rational function obtained by RKFIT isrepresented with the aid of a scalar rational Krylov decomposition and an additionalcoefficient vector. A function represented in this form is called an RKFUN. We developefficient methods for the evaluation, pole and root finding, and for performing basicarithmetic operations with RKFUNs.Lastly, we discuss RKToolbox, a rational Krylov toolbox for MATLAB, whichimplements all our algorithms and is freely available from http://rktoolbox.org.RKToolbox also features an extensive guide and a growing number of examples. Inparticular, most of our numerical experiments are easily reproducible by downloadingthe toolbox and running the corresponding example files in MATLAB.
Date of Award | 1 Aug 2017 |
---|
Original language | English |
---|
Awarding Institution | - The University of Manchester
|
---|
Supervisor | Francoise Tisseur (Supervisor) & Stefan Guettel (Supervisor) |
---|
- RKToolbox
- RKFUN
- RKFIT
- rational approximation
- parallelization
- matrix functions
- harmonic Ritz values
- Ritz values
- rational Krylov space
- rational Arnoldi algorithm
- rational Krylov method
Rational Krylov Decompositions: Theory and Applications
Berljafa, M. (Author). 1 Aug 2017
Student thesis: Phd