Efficient eigenvalue computation for quasiseparable Hermitian matrices under low rank perturbations

In this paper we address the problem of efficiently computing all the eigenvalues of a large N×N Hermitian matrix modified by a possibly non Hermitian perturbation of low rank. Previously proposed fast adaptations of the QR algorithm are considerably simplified by performing a preliminary transformation of the matrix by similarity into an upper Hessenberg form. The transformed matrix can be specified by a small set of parameters which are easily updated during the QR process. The resulting structured QR iteration can be carried out in linear time using linear memory storage. Moreover, it is proved to be backward stable. Numerical experiments show that the novel algorithm outperforms available implementations of the Hessenberg QR algorithm already for small values of N.      

A quaternion QR algorithm

Summary This paper extends the Francis QR algorithm to quaternion and antiquaternion matrices. It calculates a quaternion version of the Schur decomposition using quaternion unitary similarity transformations. Following a finite step reduction to a Hessenberg-like condensed form, a sequence of implicit QR steps reduces the matrix to triangular form. Eigenvalues may be read off the diagonal. Eigenvectors may be obtained from simple back substitutions. For serial computation, the algorithm uses only half the work and storage of the unstructured Francis QR iteration. By preserving quaternion structure, the algorithm calculates the eigenvalues of a nearby quaternion matrix despite rounding errors.     

线性混合模型中方差分量的估计与QR分解

在线性混合模型中, 极大似然估计是一种很重要的估计方法, 但是它常常需要通过迭代求解. 应用设计阵的QR分解, 可以把设计阵变换成上三角矩阵. 这样可以降低参与迭代运算的矩阵的阶数, 还可以减少参与运算的数据量, 从而提高运算的速度. 本文讨论了QR分解在EM算法中的应用, 并用模拟的方法验证了QR分解可以极大的提高运算的速度. 本文同时讨论了QR分解在另外一种估计方法, 即ANOVA估计中的应用.     

Implicit QR algorithms for palindromic and even eigenvalue problems

In the spirit of the Hamiltonian QR algorithm and other bidirectional chasing algorithms, a structure-preserving variant of the implicit QR algorithm for palindromic eigenvalue problems is proposed. This new palindromic QR algorithm is strongly backward stable and requires less operations than the standard QZ algorithm, but is restricted to matrix classes where a preliminary reduction to structured Hessenberg form can be performed. By an extension of the implicit Q theorem, the palindromic QR algorithm is shown to be equivalent to a previously developed explicit version. Also, the classical convergence theory for the QR algorithm can be extended to prove local quadratic convergence. We briefly demonstrate how even eigenvalue problems can be addressed by similar techniques. D. S. Watkins partly supported by Deutsche Forschungsgemeinschaft through Matheon, the DFG Research Center Mathematics for key technologies in Berlin.     

On the fast reduction of a quasiseparable matrix to Hessenberg and tridiagonal forms

In this paper we design a fast new algorithm for reducing an N × N quasiseparable matrix to upper Hessenberg form via a sequence of N − 2 unitary transformations. The new reduction is especially useful when it is followed by the QR algorithm to obtain a complete set of eigenvalues of the original matrix. In particular, it is shown that in a number of cases some recently devised fast adaptations of the QR method for quasiseparable matrices can benefit from using the proposed reduction as a preprocessing step, yielding lower cost and a simplification of implementation.     

QR factorization for row or column symmetric matrix

The problem of fast computing the QR factorization of row or column symmetric matrix is considered. We address two new algorithms based on a correspondence of Q and R matrices between the row or column symmetric matrix and its mother matrix. Theoretical analysis and numerical evidence show that, for a class of row or column symmetric matrices, the QR factorization using the mother matrix rather than the row or column symmetric matrix per se can save dramatically the CPU time and memory without loss of any numerical precision.     

基于反Krylov矩阵正交分解的半可分矩阵

在本文中，我们证明了对一个反Krylov矩阵作QR分解后，利用得到的正交矩阵可以将一个具有互异特征值的对称矩阵转化为一个半可分矩阵的形式，这个结果表明了反Krylov矩阵与半可分矩阵之间的联系．另外，我们还证明了这类对称半可分矩阵在QR达代下矩阵结构保持不变性．     

Low-rank revealing QR factorizations

Rank revealing factorizations are used extensively in signal processing in connection with, for example, linear prediction and signal subspace algorithms. We present an algorithm for computing rank revealing QR factorizations of low-rank matrices. The algorithm produces tight upper and lower bounds for all the largest singular values, thus making it particularly useful for treating rank deficient problems by means of subset selection, truncated QR, etc. The algorithm is similar in spirit to an algorithm suggested earlier by Chan for matrices with a small nullity, and it can also be considered as an extension of ordinary column pivoting.     

Convergence of LR algorithm for a one-point spectrum tridiagonal matrix

We prove convergence for the basic LR algorithm on a real unreduced tridiagonal matrix with a one-point spectrum—the Jordan form is one big Jordan block. First we develop properties of eigenvector matrices. We also show how to deal with the singular case.     

A Wilkinson-like multishift QR algorithm for symmetric eigenvalue problems and its global convergence

In 1989, Bai and Demmel proposed the multishift QR algorithm for eigenvalue problems. Although the global convergence property of the algorithm (i.e., the convergence from any initial matrix) still remains an open question for general nonsymmetric matrices, in 1992 Jiang focused on symmetric tridiagonal case and gave a global convergence proof for the generalized Rayleigh quotient shifts. In this paper, we propose Wilkinson-like shifts, which reduce to the standard Wilkinson shift in the single shift case, and show a global convergence theorem.     

Symmetric Gaussian elimination for cauchy-type matrices with application to positive definite Toeplitz matrices

The problem of solving linear equations with a Toeplitz matrix appears in many applications. Often is positive definite but ill-conditioned with many small eigenvalues. In this case fast and superfast algorithms may show a very poor behavior or even break down. In recent papers the transformation of a Toeplitz matrix into a Cauchy-type matrix is proposed. The resulting new linear equations can be solved in operations using standard pivoting strategies which leads to very stable fast methods also for ill-conditioned systems. The basic tool is the formulation of Gaussian elimination for matrices with low displacement rank. In this paper, we will transform a Hermitian Toeplitz matrix into a Cauchy-type matrix by applying the Fourier transform. We will prove some useful properties of and formulate a symmetric Gaussian elimination algorithm for positive definite . Using the symmetry and persymmetry of we can reduce the total costs of this algorithm compared with unsymmetric Gaussian elimination. For complex Hermitian , the complexity of the new algorithm is then nearly the same as for the Schur algorithm. Furthermore, it is possible to include some strategies for ill-conditioned positive definite matrices that are well-known in optimization. Numerical examples show that this new algorithm is fast and reliable. Received March 24, 1995 / Revised version received December 13, 1995     

计算Hamilton矩阵特征值的一个稳定的有效的保结构的算法

提出了一个稳定的有效的保结构的计算Hamilton矩阵特征值和特征不变子空间的算法，该算法是由SR算法改进变形而得到的。在该算法中，提出了两个策略，一个叫做消失稳策略，另一个称为预处理技术，在消失稳策略中，通过求解减比方程和回溯彻底克服了Bunser Gerstner和Mehrmann提出的SR算法的严重失稳和中断现象的发生，两种策略的实施的代价都非常低。数值算例展示了该算法比其它求解Hamilton矩阵特征问题的算法更有效和可靠。     

New GMRES(k)-Type Algorithms with Explicit Restarts and the Analysis of Their Convergence Properties Based on Matrix Relations in QR Form

The paper considers the problem of constructing a basic iterative scheme for solving systems of linear algebraic equations with unsymmetric and indefinite coefficient matrices. A new GMRES-type algorithm with explicit restarts is suggested. When restarting, this algorithm takes into account the spectral/singular data transferred using orthogonal matrix relations in the so-called QR form, which arise when performing inner iterations of Arnoldi type. The main idea of the algorithm developed is to organize inner iterations and the filtering of directions before restarting in such a way that, from one restart to another, matrix relations effectively accumulate information concerning the current approximate solution and, simultaneously, spectral/singular data, which allow the algorithm to converge with a rate comparable with that of the GMRES algorithm without restarts. Convergence theory is provided for the case of nonsingular, unsymmetric, and indefinite matrices. A bound for the rate of decrease of the residual in the course of inner Arnoldi-type iterations is obtained. This bound depends on the spectral/singular characterization of the subspace spanned by the directions retained upon filtering and is used in developing efficient filtering procedures. Numerical results are provided. Bibliography: 9 titles.     

An inverse free parallel spectral divide and conquer algorithm for nonsymmetric eigenproblems

Summary. We discuss an inverse-free, highly parallel, spectral divide and conquer algorithm. It can compute either an invariant subspace of a nonsymmetric matrix , or a pair of left and right deflating subspaces of a regular matrix pencil . This algorithm is based on earlier ones of Bulgakov, Godunov and Malyshev, but improves on them in several ways. This algorithm only uses easily parallelizable linear algebra building blocks: matrix multiplication and QR decomposition, but not matrix inversion. Similar parallel algorithms for the nonsymmetric eigenproblem use the matrix sign function, which requires matrix inversion and is faster but can be less stable than the new algorithm. Received September 20, 1994 / Revised version received February 5, 1996     

A block algorithm for computing rank-revealing QR factorizations

We present a block algorithm for computing rank-revealing QR factorizations (RRQR factorizations) of rank-deficient matrices. The algorithm is a block generalization of the RRQR-algorithm of Foster and Chan. While the unblocked algorithm reveals the rank by peeling off small singular values one by one, our algorithm identifies groups of small singular values. In our block algorithm, we use incremental condition estimation to compute approximations to the nullvectors of the matrix. By applying another (in essence also rank-revealing) orthogonal factorization to the nullspace matrix thus created, we can then generate triangular blocks with small norm in the lower right part ofR. This scheme is applied in an iterative fashion until the rank has been revealed in the (updated) QR factorization. We show that the algorithm produces the correct solution, under very weak assumptions for the orthogonal factorization used for the nullspace matrix. We then discuss issues concerning an efficient implementation of the algorithm and present some numerical experiments. Our experiments show that the block algorithm is reliable and successfully captures several small singular values, in particular in the initial block steps. Our experiments confirm the reliability of our algorithm and show that the block algorithm greatly reduces the number of triangular solves and increases the computational granularity of the RRQR computation.This work was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, US Department of Energy, under Contract W-31-109-Eng-38. The second author was also sponsored by a travel grant from the Knud Højgaards Fond.This work was partially completed while the author was visiting the IBM Scientific Center in Heidelberg, Germany.     

Convergence of the shifted QR algorithm on 3×3 normal matrices

Summary This paper concerns the convergence properties of the shifted QR algorithm on 3×3 normal, Hessenberg matrices. The algorithm is viewed as an iteration on one dimensional subspaces. A class of matrices is characterized for which HQR2 is unable to approximate a solution.The author was partially supported by the NSF     

A NUMERICALLY STABLE BLOCK MODIFIED GRAM-SCHMIDT ALGORITHM FOR SOLVING STIFF WEIGHTED LEAST SQUARES PROBLEMS

Recently, Wei in proved that perturbed stiff weighted pseudoinverses and stiff weighted least squares problems are stable, if and only if the original and perturbed coefficient matrices A and A^- satisfy several row rank preservation conditions. According to these conditions, in this paper we show that in general, ordinary modified Gram-Schmidt with column pivoting is not numerically stable for solving the stiff weighted least squares problem. We then propose a row block modified Gram-Schmidt algorithm with column pivoting, and show that with appropriately chosen tolerance, this algorithm can correctly determine the numerical ranks of these row partitioned sub-matrices, and the computed QR factor R^- contains small roundoff error which is row stable. Several numerical experiments are also provided to compare the results of the ordinary Modified Gram-Schmidt algorithm with column pivoting and the row block Modified Gram-Schmidt algorithm with column pivoting.     

Computing the field of values and pseudospectra using the Lanczos method with continuation

The field of values and pseudospectra are useful tools for understanding the behaviour of various matrix processes. To compute these subsets of the complex plane it is necessary to estimate one or two eigenvalues of a large number of parametrized Hermitian matrices; these computations are prohibitively expensive for large, possibly sparse, matrices, if done by use of the QR algorithm. We describe an approach based on the Lanczos method with selective reorthogonalization and Chebyshev acceleration that, when combined with continuation and a shift and invert technique, enables efficient and reliable computation of the field of values and pseudospectra for large matrices. The idea of using the Lanczos method with continuation to compute pseudospectra is not new, but in experiments reported here our algorithm is faster and more accurate than existing algorithms of this type.This work was supported by Engineering and Physical Sciences Research Council grants GR/H/52139 and GR/H/94528.     

The QRPS algorithm: A generalization of the QR algorithm for the singular values decomposition of rectangular matrices

A generalization of the QR algorithm proposed by Francis [2] for square matrices is introduced for the singular values decomposition of arbitrary rectangular matrices. Geometrically the algorithm means the subsequent orthogonalization of the image of orthonormal bases produced in the course of the iteration. Our purpose is to show how to get a series of lower triangular matrices by alternate orthogonal-upper triangular decompositions in different dimensions and to prove the convergence of this series.     

Decomposition of an Updated Correlation Matrix via Hyperbolic Transformations

An algorithm for hyperbolic singular value decomposition of a given complex matrix based on hyperbolic Householder and Givens transformation matrices is described in detail. The main application of this algorithm is the decomposition of an updated correlation matrix.