The periodic qr algorithm is a strongly backward stable method for computing the eigenvalues of products of matrices, or equivalently for computing the eigenvalues of block cyclic matrices. The main purpose of this pa...
详细信息
The periodic qr algorithm is a strongly backward stable method for computing the eigenvalues of products of matrices, or equivalently for computing the eigenvalues of block cyclic matrices. The main purpose of this paper is to show that this algorithm is numerically equivalent to the standard qr algorithm. It will be demonstrated how this connection may be used to develop a better understanding of the periodic qr algorithm. (c) 2003 Elsevier Inc. All rights reserved.
By use of the three-term recurrence relation, an elementary and constructive proof is given for the global convergence of the symmetric tridiagonal qr algorithm with Wilkinson's shift. It is further illustrated wh...
详细信息
By use of the three-term recurrence relation, an elementary and constructive proof is given for the global convergence of the symmetric tridiagonal qr algorithm with Wilkinson's shift. It is further illustrated why the asymptotic rate of convergence is essentially cubic, as has long been observed in numerical experiments. A general mixed shift strategy with global convergence and cubic rate is also presented. (C) 2001 Published by Elsevier Science Inc. All rights reserved.
An extended qr algorithm specifically tailored for Hamiltonian matrices is presented. The algorithm generalizes the customary Hamiltonian qr algorithm with additional freedom in choosing between various possible exten...
详细信息
An extended qr algorithm specifically tailored for Hamiltonian matrices is presented. The algorithm generalizes the customary Hamiltonian qr algorithm with additional freedom in choosing between various possible extended Hamiltonian Hessenberg forms. We introduced in Ferranti et al. (Calcolo, 2015. doi10.1007/s10092-016-0192-1) an algorithm to transform certain Hamiltonian matrices to such forms. Whereas the convergence of the classical qr algorithm is related to classical Krylov subspaces, convergence in the extended case links to extended Krylov subspaces, resulting in a greater flexibility, and possible enhanced convergence behavior. Details on the implementation, covering the bidirectional chasing and the bulge exchange based on rotations are presented. The numerical experiments reveal that the convergence depends on the selected extended forms and illustrate the validity of the approach.
The efficient solution of the matrix eigenvalue problem is of great importance for quantum mechanical calculations. For the determination of all eigenvalues and all eigenvectors of a non-sparse matrix, we have investi...
详细信息
The efficient solution of the matrix eigenvalue problem is of great importance for quantum mechanical calculations. For the determination of all eigenvalues and all eigenvectors of a non-sparse matrix, we have investigated the widely-used qr algorithm. In this paper we present a new efficient parallelization for loosely-coupled multiprocessing systems, based upon cyclic reductions.
In this paper, we study two equivalent ways of transforming a system of orthogonal polynomials: one is the so-called lifting of the recurrence relation associated with an orthogonal polynomial system (OPS) and the oth...
详细信息
In this paper, we study two equivalent ways of transforming a system of orthogonal polynomials: one is the so-called lifting of the recurrence relation associated with an orthogonal polynomial system (OPS) and the other consists of applying the qr algorithm to the Jacobi matrix of the OPS. These transformations are useful for, among other things, identifying the Sobolev orthogonal polynomials with respect to certain measures, which were previously investigated by Iserles et al. (1991). As a by-product we obtain a new class of modified Lommel polynomials.
Aggressive early deflation has proven to significantly enhance the convergence of the qr algorithm for computing the eigenvalues of a nonsymmetric matrix. One purpose of this paper is to point out that this deflation ...
详细信息
Aggressive early deflation has proven to significantly enhance the convergence of the qr algorithm for computing the eigenvalues of a nonsymmetric matrix. One purpose of this paper is to point out that this deflation strategy is equivalent to extracting converged Ritz vectors from certain Krylov subspaces. As a special case, the single-shift qr algorithm enhanced with aggressive early deflation corresponds to a Krylov subspace method whose starting vector undergoes a Rayleigh-quotient iteration. It is shown how these observations can be used to derive improved convergence bounds for the qr algorithm.
The qr algorithm is still one of the most important methods for computing eigenvalues and eigenvectors of matrices. Most discussions of the qr algorithm begin with a very basic version and move by steps toward the ver...
详细信息
The qr algorithm is still one of the most important methods for computing eigenvalues and eigenvectors of matrices. Most discussions of the qr algorithm begin with a very basic version and move by steps toward the versions of the algorithm that are actually used. This paper outlines a pedagogical path that leads directly to the implicit multishift qr algorithms that are used in practice, bypassing the basic qr algorithm completely.
In this paper, we discuss the convergence of the double-shift and multi-shift qr algorithms for symmetric tridiagonal matrices. We analyze how to choose multi-shifts by comparing the relationships between the number o...
详细信息
In this paper, we discuss the convergence of the double-shift and multi-shift qr algorithms for symmetric tridiagonal matrices. We analyze how to choose multi-shifts by comparing the relationships between the number of iterations, CPU time and the number of multi-shifts. Numerical tests and figures are performed. (C) 2013 Elsevier Inc. All rights reserved.
Recently a generalization of Francis's implicitly shifted qr algorithm was proposed, notably widening the class of matrices admitting low-cost implicit qr steps. This unifying framework covered the methods and the...
详细信息
Recently a generalization of Francis's implicitly shifted qr algorithm was proposed, notably widening the class of matrices admitting low-cost implicit qr steps. This unifying framework covered the methods and theory for Hessenberg and inverse Hessenberg matrices and furnished also new, single-shifted, qr-type methods for, e.g., CMV matrices. Convergence of this approach was only suggested by numerical experiments. No theoretical claims supporting the results were presented. In this paper we present multishift variants of these new algorithms. We also provide a convergence theory that shows that the new algorithm performs nested subspace iterations on rational Krylov subspaces. Numerical experiments confirm the validity of the theory.
We have written out all shifting algorithm in the qr corresponding to article [SIAM J. Matrix Anal. 12 (1991) 385], specially the block shift algorithm, and tested them with Maple8. A comparison table has been designe...
详细信息
We have written out all shifting algorithm in the qr corresponding to article [SIAM J. Matrix Anal. 12 (1991) 385], specially the block shift algorithm, and tested them with Maple8. A comparison table has been designed in each case to compare the implementation of the algorithms with each other. The differences of the shifts have been noted in the last section. (C) 2004 Elsevier Inc. All rights reserved.
暂无评论