We discuss the convergence rate of the qr algorithm with Wilkinson's shift for tridiagonal symmetric eigenvalue problems. It is well known that the convergence rate is theoretically at least quadratic, and practic...
详细信息
We discuss the convergence rate of the qr algorithm with Wilkinson's shift for tridiagonal symmetric eigenvalue problems. It is well known that the convergence rate is theoretically at least quadratic, and practically better than cubic for most matrices. In an effort to derive the convergence rate, the limiting patterns of some lower right submatrices have been intensively investigated. In this paper, we first describe a new limiting pattern of the lower right 3-by-3 submatrix with a concrete example, and then prove that the convergence rate of this new pattern is strictly cubic. In addition, we stress that our analysis identifies three classes of the limiting patterns of the tridiagonal qr algorithm with Wilkinson's shift.
One approach to solving the nonsymmetric eigenvalue problem in parallel is to parallelize the qr algorithm. Not long ago, this was widely considered to be a hopeless task. Recent efforts have led to significant advanc...
详细信息
One approach to solving the nonsymmetric eigenvalue problem in parallel is to parallelize the qr algorithm. Not long ago, this was widely considered to be a hopeless task. Recent efforts have led to significant advances, although the methods proposed up to now have suffered from scalability problems. This paper discusses an approach to parallelizing the qr algorithm that greatly improves scalability. A theoretical analysis indicates that the algorithm is ultimately not scalable, but the nonscalability does not become evident until the matrix dimension is enormous. Experiments on the Intel Paragon system, the IBM SP2 supercomputer, the SGI Origin 2000, and the Intel ASCI Option Red supercomputer are reported.
Fifty years after the invention of the qr algorithm by John Francis and Vera Kublanovskaya we reconstruct the ideas and the influences that led to its genesis from the originators' own recollections and their sour...
详细信息
Fifty years after the invention of the qr algorithm by John Francis and Vera Kublanovskaya we reconstruct the ideas and the influences that led to its genesis from the originators' own recollections and their sources and give an account of some of its subsequent developments.
Aggressive early deflation is a qr algorithm deflation strategy that takes advantage of matrix perturbations outside of the subdiagonal entries of the Hessenberg qr iterate. It identifies and deflates converged eigenv...
详细信息
Aggressive early deflation is a qr algorithm deflation strategy that takes advantage of matrix perturbations outside of the subdiagonal entries of the Hessenberg qr iterate. It identifies and deflates converged eigenvalues long before the classic small-subdiagonal strategy would. The new deflation strategy enhances the performance of conventional large-bulge multishift qr algorithms, but it is particularly effective in combination with the small-bulge multishift qr algorithm. The small-bulge multishift qr sweep with aggressive early deflation maintains a high rate of execution of floating point operations while significantly reducing the number of operations required.
Over the last few years, it has been suggested that the popular qr algorithm for the unsymmetric Schur decomposition does not parallelize. In this paper, we present both positive and negative results on this subject. ...
详细信息
Over the last few years, it has been suggested that the popular qr algorithm for the unsymmetric Schur decomposition does not parallelize. In this paper, we present both positive and negative results on this subject. In theory, asymptotically perfect speedup can be obtained. In practice, reasonable speedup can be obtained on an MIMD distributed memory computer for a relatively small number of processors. However, we also show theoretically that it is impossible for the standard qr algorithm to be scalable. performance of a parallel implementation of the LAPACK DLAHqr routine on the Intel Paragon(TM) system is reported.
A number of results on the distributions of least squares estimators and their associatedtandFstatistics are derived via theqralgorithm. Given the initialqrtransformation, the proofs are simple and direct, and the tra...
详细信息
A number of results on the distributions of least squares estimators and their associatedtandFstatistics are derived via theqralgorithm. Given the initialqrtransformation, the proofs are simple and direct, and the transformation itself requires only a minimal understanding of matrix algebra.
The qr algorithm is one of the most popular methods for calculating the eigenvalues of a matrix. In the course of iterations of the implicitly shifted qr algorithm on an upper Hessenberg matrix, it is crucial to check...
详细信息
The qr algorithm is one of the most popular methods for calculating the eigenvalues of a matrix. In the course of iterations of the implicitly shifted qr algorithm on an upper Hessenberg matrix, it is crucial to check for zeros on the subdiagonal of the matrix. A zero on the subdiagonal allows the problem to be split into two independent subproblems. Moreover, if the splitting is not carried out, the subdiagonal zero will cause the subsequent qr iterations to break down. In practice exact zeros are rare;instead one normally sees very tiny numbers like 10(-19). It is reasonable to set such numbers to zero and split the problem. Indeed it is widely believed that it is crucial to carry out a splitting in such cases. Although such small entries, if left in place, will not cause the qr iterations to break down outright, they will (or so it is thought) trigger a breakdown of forward stability;small roundoff errors will be magnified dangerously, and the qr step will degenerate to a random similarity transformation. The first objective of this paper is to show that this widespread belief is mistaken;tiny subdiagonal entries do not normally cause forward instability or interfere in any way with the convergence of the algorithm. The second objective is to show that even in situations where forward instability does occur, the qr step is not normally rendered ineffective. On the contrary, the shift is transmitted accurately through the region of instability in such a way that a qr step with the chosen shift is performed on the trailing submatrix.
The qr algorithm is a basic algorithm for computing the eigenvalues of dense matrices. For efficiency reasons it is prerequisite that the algorithm is applied only after the original matrix has been reduced to a matri...
详细信息
The qr algorithm is a basic algorithm for computing the eigenvalues of dense matrices. For efficiency reasons it is prerequisite that the algorithm is applied only after the original matrix has been reduced to a matrix of a particular shape, most notably Hessenberg and tridiagonal, which is preserved during the iterative process. In certain circumstances a reduction to another matrix shape may be advantageous. In this paper, we identify which zero patterns of symmetric matrices are preserved under the qr algorithm.
Let H be an n × n unitary right Hessenberg matrix with positive subdiagonal elements. Using what we call the Schur parameterization of H , we show how one step of the shifted qr algorithm for H can be carried out...
详细信息
Let H be an n × n unitary right Hessenberg matrix with positive subdiagonal elements. Using what we call the Schur parameterization of H , we show how one step of the shifted qr algorithm for H can be carried out in O( n ) arithmetic operations. Coupled with the shift strategy of Eberlein and Huang [3], this will permit computation of the spectrum of H , to machine precision, in O( n 2 ) operations. One potential application is the computation of Gauss-Szegö quadrature formulas [12], given the associated Schur parameters [7]. The weights can also be computed, by direct analogy with [6].
This paper shows that for unitary Hessenberg matrices the qr algorithm, with ( an exceptional initial-value modi cation of) the Wilkinson shift, gives global convergence;moreover, the asymptotic rate of convergence is...
详细信息
This paper shows that for unitary Hessenberg matrices the qr algorithm, with ( an exceptional initial-value modi cation of) the Wilkinson shift, gives global convergence;moreover, the asymptotic rate of convergence is at least cubic, higher than that which can be shown to be quadratic only for Hermitian tridiagonal matrices, under no further assumption. A general mixed shift strategy with global convergence and cubic rates is also presented.
暂无评论