The block grade of a block Krylov space

• Published in: Linear algebra and its applications 2009, Vol.430 (1), p.174-185
• Main Authors: Gutknecht, Martin H., Schmelzer, Thomas
• Format: Article
• Language: English
• Subjects: Algebra; Block Krylov space method; Block Krylov space solver; Block size reduction; Deflation; Exact sciences and technology; Grade; Linear and multilinear algebra, matrix theory; Mathematics; Minimal polynomial; Multiple right-hand sides; Sciences and techniques of general use; Several right-hand sides; Sparse linear systems
• ISSN: 0024-3795; 1873-1856
• DOI: 10.1016/j.laa.2008.07.008

The aim of the paper is to compile and compare basic theoretical facts on Krylov subspaces and block Krylov subspaces. Many Krylov (sub)space methods for solving a linear system Ax = b have the property that in exact computer arithmetic the true solution is found after ν iterations, where ν is the dimension of the largest Krylov subspace generated by A from r 0 , the residual of the initial approximation x 0 . This dimension is called the grade of r 0 with respect to A. Though the structure of block Krylov subspaces is more complicated than that of ordinary Krylov subspaces, we introduce here a block grade for which an analogous statement holds when block Krylov space methods are applied to linear systems with multiple, say s , right-hand sides. In this case, the s initial residuals are bundled into a matrix R 0 with s columns. The possibility of linear dependence among columns of the block Krylov matrix ( R 0 AR 0 ⋯ A ν - 1 R 0 ) , which in practical algorithms calls for the deletion (or, deflation) of some columns, requires extra care. Relations between grade and block grade are also established, as well as relations to the corresponding notions of a minimal polynomial and its companion matrix.