Some of the most efficient iterative algorithms for large sparse Hermitian matrix computations are based on orthogonal or kernel polynomials. For the case of non-Hermitian matrices, methods based on orthogonal or kern...
详细信息
Some of the most efficient iterative algorithms for large sparse Hermitian matrix computations are based on orthogonal or kernel polynomials. For the case of non-Hermitian matrices, methods based on orthogonal or kernel polynomials are less satisfactory, in that the resulting algorithms involve long recurrences. Consequently, it is usually too expensive to run the full algorithms and restarts are necessary. A typical example is the generalized minimalresidual method (GMRES) for solving non-Hermitian linear systems, where work and storage per iteration grow linearly with the iteration number. Recently, two quasi-minimalresidual methods (QMR) for solving non-Hermitian linear systems have been proposed, which - unlike GMRES - are based on short recurrences and hence can be used as true iterative schemes, without restarts. In this paper, the concept of quasi-kernel polynomials is introduced. Some general theory for quasi-kernel polynomials is developed, such as recurrence relations and a characterization of roots of quasi-kernel polynomials as generalized eigenvalues. It is pointed out that the QMR approaches are based on two particular instances of quasi-kernel polynomials. Also, the use of quasi-kernel polynomials for approximating eigenvalues or pseudospectra of large sparse non-Hermitian matrices is briefly discussed.
We present a transpose-free version of the nonsymmetric scaled Lanczos procedure. It generates the same tridiagonal matrix as the classical algorithm, using two matrix-vector products per iteration without accessing A...
详细信息
We present a transpose-free version of the nonsymmetric scaled Lanczos procedure. It generates the same tridiagonal matrix as the classical algorithm, using two matrix-vector products per iteration without accessing A(T). We apply this algorithm to obtain a transpose-free version of the quasi-minimalresidual method of Freund and Nachtigal [15] (without look-ahead), which requires three matrix-vector products per iteration. We also present a related transpose-free version of the bi-conjugate gradients algorithm.
暂无评论