In April 2016 Manchester eScholar was replaced by the University of Manchester’s new Research Information Management System, Pure. In the autumn the University’s research outputs will be available to search and browse via a new Research Portal. Until then the University’s full publication record can be accessed via a temporary portal and the old eScholar content is available to search and browse via this archive.

Related resources

Search for item elsewhere

University researcher(s)

Academic department(s)

Rational Krylov Decompositions: Theory and Applications

Berljafa, Mario

[Thesis]. Manchester, UK: The University of Manchester; 2017.

Access to files

FULL-TEXT.PDF (pdf)

Abstract

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.