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 biconjugate gradient (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.
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.
We consider the problem of producing all the roots of a polynomial p(x) = a0xn + a1xn−l+ … + an(where all the roots are distinct) by an iterative systolic array. Two basic arrays are considered, one where the positio...
详细信息
We consider the problem of producing all the roots of a polynomial p(x) = a0xn + a1xn−l+ … + an(where all the roots are distinct) by an iterative systolic array. Two basic arrays are considered, one where the position of the roots remain stationary and another where they are non-stationary. The former scheme requires O(n) basic cells, the latter O(z) cells with z (>0) a suitably chosen constant determining the number of root approximations on a single pass through the array. Finally an area efficient systolic ring is discussed requiring O(n/A) cells to compute an arbitrary number of root approximations.
暂无评论