BANDITS: a Matlab Package of Band Krylov Subspace Iterations
One of the most versatile tools for large-scale matrix computations
are iterative methods based on Krylov subspaces.
Standard Krylov subspaces are induced by a given square matrix \( A \) and a
single starting vector \( r \).
However, many important applications of Krylov-subspace methods involve a
block \( R \) of multiple starting vectors, rather than a single starting
vector \( r \).
Applications of this type include the iterative solution of systems of linear
equations with multiple right-hand sides and model reduction of linear dynamical
systems with multiple inputs and outputs.
The traditional approach of dealing with multiple starting vectors is to
employ block algorithms to generate suitable basis vectors for block
Krylov subspaces induced by a given square matrix \( A \) and a block \( R \)
of multiple starting vectors.
However, there are a number of conceptual issues with such block algorithms.
In general, Krylov vectors will become linearly dependent or almost
linearly dependent before the block Krylov subspaces are exhausted.
Dealing with such Krylov vectors requires deflation procedures and reduction
of block sizes to continue the block iteration.
For the general Lanczos method, which involves blocks \( R \) and \( L \) of
right and left starting vectors, block variants are only feasible if \( R \)
and \( L \) have the same number of columns and if deflations are assumed to
occur simultaneously for the right and left Krylov vectors.
Band Krylov subspace methods remedy some of the issues of block approaches.
Even though band methods generate suitable basis vectors for the same
Krylov subspaces as the block methods, they do so by employing a vector-wise
construction, instead of the block-wise construction in block methods.
This vector-wise construction makes it easy to check for necessary deflations
and to perform these deflations.
It also allows to deal with starting blocks \( R \) and \( L \) of any size.
The band approach was pioneered by Axel Ruhe who was the first to propose
a band version of the symmetric Lanczos method in the context of computing
eigenvalues of real symmetric matrices.
The more recent development of the band Lanczos method for general matrices
\( A \), \( R \), and \( L \) was motivated by
the need for an efficient Krylov subspace method in the context of
model reduction of linear time-invariant dynamical systems with multiple inputs
and outputs.
In this application, the starting blocks \( R \) and \( L \) do not have the
same number of columns in general.
BANDITS is a package of Matlab implementations of band versions of the Arnoldi
process, the Lanczos method, and of simplified versions of the Lanczos method
for Hermitian, symmetric, \( J \)-Hermitian, and \( J \)-symmetric matrices.
The Matlab functions of these methods are designed such that each band algorithm
can be started from scratch ("cold start") or can resume a previous
run ("hot start").
To facilitate this feature, the output of each algorithm is a structure "result"
the fields of which are quantities (such as projections of \( A \) and \( R \)
onto the subspaces spanned by the generated basis vectors) needed in applications
and internal quantities used inside the algorithm. In the case of a hot start,
the output structure "result" produced by a previous run is a required input
for the resuming run of the algorithm.
All Lanczos algorithms in BANDITS have the option of storing only the
Lanczos vectors needed to run the algorithm or of storing all Lanczos vectors
generated in the course of the iteration.
Algorithms
- Band Arnoldi process
The band Arnoldi process generates orthonormal basis vectors for
the block Krylov subspaces induced by a square matrix \( A \) and
a block \( R \) of multiple starting vectors.
The matrices \( A \) and \( R \) are allowed to be complex, and no
assumptions on \( A \) are made.
If the algorithm is run for \( n \) steps, \( n \) basis vectors and an
\( n \times n \) Arnoldi matrix \( H \) are produced.
The matrix \( H \) represents the orthogonal projection of \( A \)
onto the subspace spanned by the \( n \) basis vectors.
Supporting documentation for the Matlab function
band_Arnoldi
- Band Lanczos method
The band Lanczos method generates right and left Lanczos vectors
that are constructed to be biorthogonal to each other.
The right Lanczos vectors are basis vectors for
the block Krylov subspaces induced by a square matrix \( A \) and
a block \( R \) of multiple right starting vectors.
The left Lanczos vectors are basis vectors for
the block Krylov subspaces induced by the transpose \( A^T \)
of \( A \) and a block \( L \) of multiple left starting vectors.
The matrices \( A \), \( R \), and \( L \) are allowed to be complex, and no
assumptions on \( A \) and the number of columns of \( R \) and \( L \)
are made.
If the algorithm is run for \( n \) steps, \( n \) pairs of right and left Lanczos
vectors and an \( n \times n \) Lanczos matrix \( T \) are produced.
The matrix \( T \) represents the oblique projection of \( A \) onto the subspace
spanned by the \( n \) right Lanczos vectors and orthogonally to the subspace
spanned by the \( n \) left Lanczos vectors.
Supporting documentation for the Matlab function
band_Lanczos
- Hermitian band Lanczos method
The Hermitian band Lanczos method generates orthonormal basis vectors for
the block Krylov subspaces induced by an Hermitian matrix \( A \) and
a block \( R \) of multiple starting vectors.
The matrices \( A \) and \( R \) are allowed to be complex, and \( A \)
is assumed to be Hermitian, i.e., \( A = A^H \), where
\( A^H \) denotes the complex conjugate transpose of the matrix \( A \).
If the algorithm is run for \( n \) steps, \( n \) basis vectors and
an \( n \times n \) Lanczos matrix \( T \) are produced.
The matrix \( T \) represents the orthogonal projection of \( A \)
onto the subspace spanned by the n basis vectors.
Supporting documentation for the Matlab function
Herm_band_Lanczos
- Symmetric band Lanczos method
The symmetric band Lanczos method generates basis vectors for
the block Krylov subspaces induced by a complex symmetric matrix \( A \) and
a block \( R \) of multiple starting vectors.
These basis vectors are constructed to be "orthogonal" with
respect to the bilinear form
\[
(w,v) = w^T v,
\]
where \( w^T \) denotes the transpose of the vector \( w \).
The matrices \( A \) and \( R \) are allowed to be complex, and
\( A \) is assumed to be complex symmetric, i.e., \( A = A^T \),
where \(A^T \) denotes the transpose of the matrix \( A \).
If the algorithm is run for \( n \) steps, \( n \) basis vectors and
an \( n \times n \) Lanczos matrix \( T \) are produced.
The matrix \( T \) represents the oblique projection
of the matrix \( A \) onto the subspace spanned by the \( n \) basis vectors,
and "orthogonally" to the subspace spanned by the \( n \) basis vectors.
Note that a complex symmetric matrix \( A \) is non-Hermitian unless all
entries of \( A \) are real.
If the matrices \( A \) and \( R \) are both real, the symmetric band Lanczos
method and the Hermitian band Lanczos method are mathematically equivalent.
In this case, the Matlab function Herm_band_Lanczos
should be used instead of sym_band_Lanczos.
Supporting documentation for the Matlab function
sym_band_Lanczos
- J-Hermitian band Lanczos method
The \( J \)-Hermitian band Lanczos method generates basis vectors for
the block Krylov subspaces induced by a \( J \)-Hermitian matrix \( A \)
and a block \( R \) of multiple starting vectors.
These basis vectors are constructed to be "orthogonal" with
respect to the bilinear form
\[
(w,v) = w^H J v,
\]
where \( w^H \) denotes the complex conjugate transpose of the vector \( w \)
and \( J \) is a nonsingular Hermitian matrix.
The matrices \( A \) and \( R \) are allowed to be complex, and \( A \)
is assumed to \( J \)-Hermitian, i.e.,
\[
J A = A^H J,
\]
where \( A^H \) denotes the complex conjugate transpose of \( A \).
If the algorithm is run for \( n \) steps, \( n \) basis vectors and
an \( n \times n \) Lanczos matrix \( T \) are produced.
The matrix \( T \) represents the oblique projection
of the matrix \( A \) onto the subspace spanned by the \( n \) basis vectors,
and "orthogonally" to the subspace spanned by the \( J \)-multiples of the
\( n \) basis vectors.
Supporting documentation for the Matlab function
JHerm_band_Lanczos
- J-Symmetric band Lanczos method
The \( J \)-symmetric band Lanczos method generates basis vectors for
the block Krylov subspaces induced by a \( J \)-symmetric matrix \( A \) and
a block \( R \) of multiple starting vectors.
These basis vectors are constructed to be "orthogonal" with
respect to the bilinear form
\[
(w,v) = w^T J v,
\]
where \( w^T \) denotes the transpose of the vector \( w \) and \( J \) is
a nonsingular complex symmetric matrix.
The matrices \( A \) and \( R \) are allowed to be complex, and \( A \)
is assumed to be \( J \)-symmetric, i.e.,
\[ J A = A^T J,
\]
where \( A^T \) denotes the transpose of \( A \).
If the algorithm is run for \( n \) steps, \( n \) basis vectors and
an \( n \times n \) Lanczos matrix \( T \) are produced.
The matrix \( T \) represents the oblique projection of the matrix \( A \)
onto the subspace spanned by the \( n \) basis vectors,
and "orthogonally" to the subspace spanned by the \( J \)-multiples of the
\( n \) basis vectors.
Supporting documentation for the Matlab function
Jsym_band_Lanczos
- Tools and auxiliary functions
The recurrence relations used in the various band algorithms can be stated
in compact form.
All the information that is needed to set up the necessary matrices for
this compact form is contained in the output structure "result" produced
by each of the above band algorithms.
The Matlab function make_matrices_for_compact_recursions
takes the structure "result" as an input, makes the matrices for the
compact form of the recurrence relations, and adds these matrices
to the structure "result".
Supporting documentation for the Matlab function
make_matrices_for_compact_recursions
Supporting documentation for the auxiliary Matlab functions
auxiliary functions that are called
in the Matlab functions band_Arnoldi, band_Lanczos,
sym_band_Lanczos, Herm_band_Lanczos, Jsym_band_Lanczos,
and JHerm_band_Lanczos.
Download
Related Publications
-
Aliaga, J.I., Boley, D.L., Freund, R.W., Hernandez, V.:
A Lanczos-type method for multiple starting vectors,
Math. Comp. Vol. 69(232), pp. 1577-1601, 2000
-
Freund, R.W.:
Model reduction methods based on Krylov subspaces,
Acta Numerica Vol. 12, pp. 267-319, 2003
-
Freund, R.W.:
Large-scale matrix computations,
in: Hogben, L. (ed.) Handbook of Linear Algebra, second edn.,
chap. 64, Chapman & Hall/CRC, Boca Raton, 2013
-
Freund, R.W.:
Electronic circuit simulation and the
development of new Krylov-subspace methods,
Technical Report, Department of Mathematics, UC Davis, February 2019
-
Ruhe, A.:
Implementation aspects of band Lanczos algorithms for computation
of eigenvalues of large sparse symmetric matrices,
Math. Comp. Vol. 33(146), pp. 680-687, 1979