Rational Krylov Methods for Operator Functions
We present a unified and self-contained treatment of rational Krylov
methods for approximating the product of a function of a linear operator
with a vector. With the help of general rational Krylov decompositions
we reveal the connections between seemingly different approximation
methods, such as the Rayleigh--Ritz or shift-and-invert method, and derive
new methods, for example a restarted rational Krylov method and
a related method based on rational interpolation in prescribed nodes...
Dissertation Thesis, 2010.
Published online (citable): http://nbn-resolving.de/urn:nbn:de:bsz:105-qucosa-27645
Deflated restarting for matrix functions with M. Eiermann and O. G. Ernst. We investigate an acceleration technique for restarted Krylov
subspace methods for computing the action of a function of a large sparse matrix on a vector. Its effect is
to ultimately deflate a specific invariant subspace of the matrix which most impedes the convergence of the restarted
approximation process. An approximation to the subspace to be deflated is successively refined in
the course of the underlying restarted Arnoldi process by extracting Ritz vectors and using those
closest to the spectral region of interest as exact shifts. The approximation is constructed with the
help of a generalization of Krylov decompositions to linearly dependent vectors. A description of
the restarted process as a successive interpolation scheme at Ritz values is given in which the exact
shifts are replaced with improved approximations of eigenvalues in each restart cycle. Numerical
experiments demonstrate the efficacy of the approach.
Submitted, October 2009.
On the Convergence of Rational Ritz Values with B. Beckermann and R. Vandebril. The rational Krylov method is a method for computing parts of the spectrum of
a large Hermitian matrix. It is well known that its convergence behavior depends not only on the
distribution of eigenvalues but also on the choice of the poles which are free parameters. Under
fairly general assumptions we characterize the region of good convergence for the rational Arnoldi
process, and obtain various results on the rate of approximation of a given eigenvalue by a rational
Ritz value. In particular, we quantify how rational Ritz values are attracted by poles. Our results
generalize recent findings on superlinear convergence of Krylov subspace methods. In particular, we
will also consider a constrained extremal problem in logarithmic potential theory where an additional
external field of a special form is required for taking into account the poles. Our analytic results are
illustrated by discussing several examples.
SIAM J. Matrix Anal. Appl., 31:1740--1774, 2010.
A Generalization of the Steepest Descent Method for Matrix Functions with M. Afanasjew, M. Eiermann, and O. G. Ernst. We consider the special case of the restarted Arnoldi method for approximating the product of a
function of a Hermitian matrix with a vector which results when the restart length is set to one. When applied
to the solution of a linear system of equations, this approach coincides with the method of steepest descent. We
show that the method is equivalent to an interpolation process in which the node sequence has at most two points of
accumulation. This knowledge is used to quantify the asymptotic convergence rate.
Electronic Transactions on Numerical Analysis. 28:206--222, 2008.
Implementation of a Restarted Krylov Subspace Method for the Evaluation of Matrix Functions with M. Afanasjew, M. Eiermann, and O. G. Ernst. A new implementation of restarted Krylov subspace methods for evaluating f(A)b for a function f, a
matrix A and a vector b is proposed. In contrast to an implementation proposed previously, it requires constant
work and constant storage space per restart cycle. The convergence behavior of this scheme is discussed
and a new stopping criterion based on an error indicator is given. The performance of the implementation is
illustrated for three parabolic initial value problems, requiring the evaluation of exp(A)b.
Linear Algebra and its Applications. 429:2293--2314, 2008.
Time-parallel integration of linear ODEs
In this talk we report on joint work with M. Gander. It is demonstrated how the solution of linear ODEs can be parallelized in time
with almost perfect speedup.
AIMS Conference on Dynamical Systems, Differential Equations and Applications, Dresden (Germany), 26.05.2010
Rational Krylov methods and approximation of f(A)b
On this poster we report on joint work with B. Beckermann, M. Eiermann,
O. G. Ernst and R. Vandebril, and on some results from my dissertation. In particular, we show how to obtain a practical estimator for
the error arrising from
inexact solves of the shifted linear systems in the rational Krylov method, making use of a corrected Rayleigh quotient.
Additionally, an error estimator based on an extension of an idea of Saad (1992, "corrected schemes") is presented.
Conference on Scientific Computing, Geneva (Switzerland), 17.06.2009
Various aspects of rational Krylov methods for matrix functions
In this talk we report on joint work with B. Beckermann, M. Eiermann,
O. G. Ernst and R. Vandebril. We characterize different approximations to f(A)b from rational Krylov spaces as approximation and interpolation problems. The latter characterization opens the question which nodes underlie the
interpolation process. This question is answered in an asymptotic sense with the help of weighted potential theory.
Academy of Sciences of the Czech Republic (Prague), 15.05.2009
On Restarted Krylov Methods for the Approximation of Matrix Functions
We consider an interesting conjecture made by Forsythe and Motzkin in the early 1950s in connection with the directions of the optimum s-gradient method. We show that the asymptotic forward-backward
behavior of these directions can be explained by a local strong version of the conjecture, which is provable. We briefly describe why this conjecture is useful to understand the convergence of the restarted Lanczos method for the approximation of matrix functions.
Rolling Waves in Leuven (Leuven, Belgium), 15.12.2008
Restart code for the numerical evaluation of matrix functions
This Matlab code computes restarted Krylov approximations to f(A)b, where A is a square, large and sparse matrix, f is a matrix function (such that f(A) is defined) and b is a vector.
A simple error bound (indicator in the non-Hermitian case) is provided and it is also possible to perform thick restarts or harmonic restarts.
Modellbildung in der Verkehrsdynamik (german)
Vortrag im Rahmen eines mathematischen Seminars. Vorgestellt werden mikroskopische Modelle (Fahrzeugfolge-Modell, Zellulärer Automat) und makroskopische Modelle (Fluss-Dichte-Relation, Lighthill-Whitham-Richards-Modell).
Datum: 14.07.2004
Stefan Güttel
Contact
