A Completed Theory of the Unsymmetric Lanczos Process and Related Algorithms, Part I

Abstract

The theory of the "unsymmetric" Lanczos biorthogonalization (BO) algorithm, which has so far been restricted to an essentially generic situation (characterized by the nonsingularity of the leading principal submatrices of the associated moment matrix or by the existence of a full set of regular formal orthogonal polynomials) is extended to the nongeneric case. The "serious" breakdowns due to the occurrence of two orthogonal right and left iteration vectors ${\bf x}_n $ and ${\bf y}_n $ can be overcome. For an operator of finite rank N the nongeneric BO algorithm, which generalizes the look-ahead Lanczos algorithm of Parlett, Taylor, and Liu [Math. Comp., 44 (1985), pp. 105–124], terminates regularly in at most N steps, except when a very special situation depending on the initial vectors occurs; but even then the algorithm produces in at most N steps a block tridiagonal matrix whose blocks are either small or sparse and whose characteristic polynomial is the minimal polynomial of the restriction of the operator to an invariant subspace. Formulas are also derived for a nongeneric version of the corresponding linear equation solves BIORES (brief for BIORTHORES or Lanczos/ORTHORES). The whole theory is developed as a consequence of known corresponding results on formal orthogonal polynomials and Padé approximants, for many of which new and simpler derivations are given.