Krylov subspace

In linear algebra, the order-r Krylov subspace generated by an n-by-n matrix A and a vector b of dimension n is the linear subspace spanned by the of b under the first r powers of A (starting from A^0=I), that is, :\mathcal{K}_r(A,b) = \operatorname{span} , { b, Ab, A^2b, \ldots, A^{r-1}b }. Background The concept is named after Russian applied mathematician and naval engineer Alexei Krylov, who published a paper about it in 1931. Properties

\mathcal{K}_r(A,b),A\mathcal{K}r(A,b)\subset \mathcal{K}{r+1}(A,b).
Vectors { b, Ab, A^2b, \ldots, A^{r-1}b } are linearly independent until r>r_0, and \mathcal{K}r(A,b) \subset \mathcal{K}{r_0}(A,b). Thus, r_0 denotes the maximal dimension of a Krylov subspace.
The maximal dimension satisfies r_0\leq 1 + \operatorname{rank} A and r_0 \leq n+1.
More exactly, r_0\leq \deg[p(A)],

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (14)

Related publications

Related people (2)

Related people

Related units (1)

Related units

Related concepts (7)

Related concepts

Related courses (5)

Related courses

Related lectures (7)

Related lectures

Many-body localization in a fragmented Hilbert space

Loïc Jean Pierre Herviou

We study many-body localization (MBL) in a pair-hopping model exhibiting strong fragmentation of the Hilbert space. We show that several Krylov subspaces have both ergodic statistics in the thermodynamic limit and a dimension that scales much slower than the full Hilbert space but still exponentially. Such a property allows us to study the MBL phase transition in systems including up to 64 spins. The different Krylov spaces that we consider show clear signatures of a many-body localization transition, both in the Kullback-Leibler divergence of the distribution of their level spacing ratio and their entanglement properties. However, they also present distinct scalings with the system size. Depending on the subspace, the critical disorder strength can be nearly independent of the system size or conversely show an approximately linear increase with the number of spins.

2021

Memory-efficient Arnoldi algorithms for linearizations of matrix polynomials in Chebyshev basis

Daniel Kressner

Novel memory-efficient Arnoldi algorithms for solving matrix polynomial eigenvalue problems are presented. More specifically, we consider the case of matrix polynomials expressed in the Chebyshev basis, which is often numerically more appropriate than the standard monomial basis for a larger degree d. The standard way of solving polynomial eigenvalue problems proceeds by linearization, which increases the problem size by a factor d. Consequently, the memory requirements of Krylov subspace methods applied to the linearization grow by this factor. In this paper, we develop two variants of the Arnoldi method that build the Krylov subspace basis implicitly, in a way that only vectors of length equal to the size of the original problem need to be stored. The proposed variants are generalizations of the so-called quadratic Arnoldi method and two-level orthogonal Arnoldi procedure methods, which have been developed for the monomial case. We also show how the typical ingredients of a full implementation of the Arnoldi method, including shift-and-invert and restarting, can be incorporated. Numerical experiments are presented for matrix polynomials up to degree 30 arising from the interpolation of nonlinear eigenvalue problems, which stem from boundary element discretizations of PDE eigenvalue problems. Copyright (C) 2013 John Wiley & Sons, Ltd.

Wiley-Blackwell2014

Compress-and-restart block Krylov subspace methods for Sylvester matrix equations

Daniel Kressner, Kathryn Dianne Lund, Stefano Massei

Block Krylov subspace methods (KSMs) comprise building blocks in many state-of-the-art solvers for large-scale matrix equations as they arise, for example, from the discretization of partial differential equations. While extended and rational block Krylov subspace methods provide a major reduction in iteration counts over polynomial block KSMs, they also require reliable solvers for the coefficient matrices, and these solvers are often iterative methods themselves. It is not hard to devise scenarios in which the available memory, and consequently the dimension of the Krylov subspace, is limited. In such scenarios for linear systems and eigenvalue problems, restarting is a well-explored technique for mitigating memory constraints. In this work, such restarting techniques are applied to polynomial KSMs for matrix equations with a compression step to control the growing rank of the residual. An error analysis is also performed, leading to heuristics for dynamically adjusting the basis size in each restart cycle. A panel of numerical experiments demonstrates the effectiveness of the new method with respect to extended block KSMs.

2020

MATH-110(a): Advanced linear algebra I

L'objectif du cours est d'introduire les notions de base de l'algèbre linéaire et de démontrer rigoureusement les résultats principaux de ce sujet.

MATH-453: Computational linear algebra

This course provides an overview of advanced techniques for solving large-scale linear algebra problems, as they typically arise in applications. A central goal of this course is to give the ability to choose a suitable solver for a given application.

MATH-341: Linear models

Regression modelling is a fundamental tool of statistics, because it describes how the law of a random variable of interest may depend on other variables. This course aims to familiarize students with linear models and some of their extensions, which lie at the basis of more general regression model

Generalized minimal residual method

In mathematics, the generalized minimal residual method (GMRES) is an iterative method for the numerical solution of an indefinite nonsymmetric system of linear equations. The method approximates the

Iterative method

In computational mathematics, an iterative method is a mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which th

Arnoldi iteration

In numerical linear algebra, the Arnoldi iteration is an eigenvalue algorithm and an important example of an iterative method. Arnoldi finds an approximation to the eigenvalues and eigenvectors of g