# 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.