This paper is a continuation of Part I [M. H. Gutknecht, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 594–639], where the theory of the “unsymmetric” Lanczos biorthogonalization (BO) algorithm and the corresponding i...
详细信息
This paper is a continuation of Part I [M. H. Gutknecht, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 594–639], where the theory of the “unsymmetric” Lanczos biorthogonalization (BO) algorithm and the corresponding iterative method BIORES for non-Hermitian linear systems was extended to the nongeneric case. The analogous extension is obtained here for the biconjugategradient (or BIOMIN) method and for the related BIODIR method. Here, too, the breakdowns of these methods can be cured. As a preparation, mixed recurrence formulas are derived for a pair of sequences of formal orthogonal polynomials belonging to two adjacent diagonals in a nonnormal Padé table, and a matrix interpretation of these recurrences is developed. This matrix interpretation leads directly to a completed formulation of the progressive qd algorithm, valid also in the case of a nonnormal Padé table. Finally, it is shown how the cure for exact breakdown can be extended to near-breakdown in such a way that (in exact arithmetic) the well-conditioned formal orthogonal polynomials and the corresponding Krylov space vectors do not depend on the threshold specifying the near-breakdown.
Recently Van der Vorst [SLAM J. Sci. Statist. Comput., 13 (1992), pp. 631-644] proposed for solving nonsymmetric linear systems Az = b a biconjugategradient (BICG)-based Krylov space method called BICGSTAB that, like...
详细信息
Recently Van der Vorst [SLAM J. Sci. Statist. Comput., 13 (1992), pp. 631-644] proposed for solving nonsymmetric linear systems Az = b a biconjugategradient (BICG)-based Krylov space method called BICGSTAB that, like the biconjugategradient squared (BICGS) method of Sonneveld, does not require matrix-vector multiplications with the transposed matrix A(T), and that has typically a much smoother convergence behavior than BICG and BICGS. Its nth residual polynomial is the product of the one of BICG (i.e., the nth Lanczos polynomial) with a polynomial of the same degree with real zeros. Therefore, nonreal eigenvalues of A are not approximated well by the second polynomial factor. Here, the author presents for real nonsymmetric matrices a method BICGSTAB2 in which the second factor may have complex conjugate zeros. Moreover, versions suitable for complex matrices are given for both methods.
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 ...
详细信息
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 x(n) and 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 solver BIORES (brief for BIORTHORES or Lanczos/ORTHORES). The whole theory is developed as a consequence of known corresponding results on formal orthogonal polynomials and Pade approximants, for many of which new and simpler derivations are given.
暂无评论