Research reports

Years: 2024 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996 1995 1994 1993 1992 1991

The block grade of a block Krylov space

by M. H. Gutknecht and T. Schmelzer

(Report number 2008-11)

Abstract
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 $\bfA\bflcx=\bflcb$ have the property that in exact computer arithmetic the true solution is found after $\nu$ iterations, where $\nu$ is the dimension of the largest Krylov subspace generated by $\bfA$ from $\bflcr_0$, the residual of the initial approximation $\bflcx_0$. This dimension is called the grade of $\bflcr_0$ with respect to $\bfA$. 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 $\ess$, right-hand sides. In this case, the $\ess$ initial residuals are bundled into a matrix $\bfr_0$ with $\ess$ columns. The possibility of linear dependence among columns of the block Krylov matrix $(\begin{array}{cccc}\bfr_0 & \bfA\bfr_0 &\dots& \bfA^{\!\nu-1}\bfr_0\end{array})$, 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. There are close connections to system and control theory, to certain areas of pure linear algebra, and to the theory of matrix polynomials, but these are only noted in the margin here.

Keywords: sparse linear systems, multiple right-hand sides, several right-hand sides, block Krylov space method, block Krylov space solver, block size reduction, deflation, grade, minimal polynomial

@Techreport{GS08_376,
  author = {M. H. Gutknecht and T. Schmelzer},
  title = {The block grade of a block Krylov space},
  institution = {Seminar for Applied Mathematics, ETH Z{\"u}rich},
  number = {2008-11},
  address = {Switzerland},
  url = {https://www.sam.math.ethz.ch/sam_reports/reports_final/reports2008/2008-11.pdf },
  year = {2008}
}

Disclaimer
© Copyright for documents on this server remains with the authors. Copies of these documents made by electronic or mechanical means including information storage and retrieval systems, may only be employed for personal use. The administrators respectfully request that authors inform them when any paper is published to avoid copyright infringement. Note that unauthorised copying of copyright material is illegal and may lead to prosecution. Neither the administrators nor the Seminar for Applied Mathematics (SAM) accept any liability in this respect. The most recent version of a SAM report may differ in formatting and style from published journal version. Do reference the published version if possible (see SAM Publications).