QZ algorithm with two-sided generalized Rayleigh quotient shifts

We generalize the recently proposed two-sided Rayleigh quotient single-shift and the two-sided Grassmann–Rayleigh quotient double-shift used in the QR algorithm and apply the generalized versions to the QZ algorithm. With such shift strategies the QZ algorithm normally has a cubic local convergence rate. Our main focus is on the modified shift strategies and their corresponding truncated versions. Numerical examples are provided to demonstrate the convergence properties and the efficiency of the QZ algorithm equipped with the proposed shifts. For the truncated versions, local convergence analysis is not provided. Numerical examples show they outperform the modified shifts and the standard Rayleigh quotient single-shift and Francis double-shift.     

计算张量特征对的瑞利商迭代法

In this paper,we propose a Rayleigh quotient iteration method (RQI)to calculate the Z-eigenpairs of the symmetric tensor,which can be viewed as a generalization of shifted symmetric higher-order power method (SS-HOPM).The convergence analysis and the fixed-point analysis of this algorithm are given.Nu-merical examples show that RQI needs fewer iterations than SS-HOPM while keep the amount of computation per iteration.     

On the weighting method for mixed least squares–total least squares problems

It is well known that the standard algorithm for the mixed least squares–total least squares (MTLS) problem uses the QR factorization to reduce the original problem into a standard total least squares problem with smaller size, which can be solved based on the singular value decomposition (SVD). In this paper, the MTLS problem is proven to be closely related to a weighted total least squares problem with its error‐free columns multiplied by a large weighting factor. A criterion for choosing the weighting factor is given; and for the sake of stability in solving the MTLS problem, the Cholesky factorization‐based inverse (Cho‐INV) iteration and Rayleigh quotient iteration are also considered. For large‐scale MTLS problems, numerical tests show that Cho‐INV is superior to the standard QR‐SVD method, especially for the case with big gap between the desired and undesired singular values and the case when the coefficient matrix has much more error‐contaminated columns. Rayleigh quotient iteration behaves more efficient than QR‐SVD for most cases and fails occasionally, and in some cases, it converges much faster than Cho‐INV but still less efficient due to its higher computation cost.     

A new adaptive mixed finite element method based on residual type a posterior error estimates for the Stokes eigenvalue problem

In this article, we combine mixed finite element method, multiscale discretization, and Rayleigh quotient iteration to propose a new adaptive algorithm based on residual type a posterior error estimates for the Stokes eigenvalue problem. Both reliability and efficiency of the error indicator are proved. The efficiency of the algorithm is also investigated using Chen's Innovation Finite Element Method (iFEM) package. Numerical results are satisfying.© 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 31: 31–53, 2015     

Inexact Rayleigh Quotient-Type Methods for Eigenvalue Computations

We consider the computation of an eigenvalue and corresponding eigenvector of a Hermitian positive definite matrix A , assuming that good approximations of the wanted eigenpair are already available, as may be the case in applications such as structural mechanics. We analyze efficient implementations of inexact Rayleigh quotient-type methods, which involve the approximate solution of a linear system at each iteration by means of the Conjugate Residuals method. We show that the inexact version of the classical Rayleigh quotient iteration is mathematically equivalent to a Newton approach. New insightful bounds relating the inner and outer recurrences are derived. In particular, we show that even if in the inner iterations the norm of the residual for the linear system decreases very slowly, the eigenvalue residual is reduced substantially. Based on the theoretical results, we examine stopping criteria for the inner iteration. We also discuss and motivate a preconditioning strategy for the inner iteration in order to further accelerate the convergence. Numerical experiments illustrate the analysis.     

A note on Inverse Iteration

Inverse iteration, if applied to a symmetric positive definite matrix, is shown to generate a sequence of iterates with monotonously decreasing Rayleigh quotients. We present sharp bounds from above and from below which highlight inverse iteration as a descent scheme for the Rayleigh quotient. Such estimates provide the background for the analysis of the behaviour of the Rayleigh quotient in certain approximate variants of inverse iteration. Copyright © 2004 John Wiley & Sons, Ltd.     

Convergence analysis of a block preconditioned steepest descent eigensolver with implicit deflation

Gradient-type iterative methods for solving Hermitian eigenvalue problems can be accelerated by using preconditioning and deflation techniques. A preconditioned steepest descent iteration with implicit deflation (PSD-id) is one of such methods. The convergence behavior of the PSD-id is recently investigated based on the pioneering work of Samokish on the preconditioned steepest descent method (PSD). The resulting non-asymptotic estimates indicate a superlinear convergence of the PSD-id under strong assumptions on the initial guess. The present paper utilizes an alternative convergence analysis of the PSD by Neymeyr under much weaker assumptions. We embed Neymeyr's approach into the analysis of the PSD-id using a restricted formulation of the PSD-id. More importantly, we extend the new convergence analysis of the PSD-id to a practically preferred block version of the PSD-id, or BPSD-id, and show the cluster robustness of the BPSD-id. Numerical examples are provided to validate the theoretical estimates.     

A geometric theory for preconditioned inverse iteration IV: On the fastest convergence cases

In order to compute the smallest eigenvalue together with an eigenfunction of a self-adjoint elliptic partial differential operator one can use the preconditioned inverse iteration scheme, also called the preconditioned gradient iteration. For this iterative eigensolver estimates on the poorest convergence have been published by several authors. In this paper estimates on the fastest possible convergence are derived. To this end the convergence problem is reformulated as a two-level constrained optimization problem for the Rayleigh quotient. The new convergence estimates reveal a wide range between the fastest possible and the slowest convergence.     

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.      

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.     

Two-sided Grassmann–Rayleigh quotient iteration

The two-sided Rayleigh quotient iteration proposed by Ostrowski computes a pair of corresponding left–right eigenvectors of a matrix C. We propose a Grassmannian version of this iteration, i.e., its iterates are pairs of p-dimensional subspaces instead of one-dimensional subspaces in the classical case. The new iteration generically converges locally cubically to the pairs of left–right p-dimensional invariant subspaces of C. Moreover, Grassmannian versions of the Rayleigh quotient iteration are given for the generalized Hermitian eigenproblem, the Hamiltonian eigenproblem and the skew-Hamiltonian eigenproblem.     

Subspace correction multi‐level methods for elliptic eigenvalue problems

In this work, we apply the ideas of domain decomposition and multi‐grid methods to PDE‐based eigenvalue problems represented in two equivalent variational formulations. To find the lowest eigenpair, we use a “subspace correction” framework for deriving the multiplicative algorithm for minimizing the Rayleigh quotient of the current iteration. By considering an equivalent minimization formulation proposed by Mathew and Reddy, we can use the theory of multiplicative Schwarz algorithms for non‐linear optimization developed by Tai and Espedal to analyse the convergence properties of the proposed algorithm. We discuss the application of the multiplicative algorithm to the problem of simultaneous computation of several eigenfunctions also formulated in a variational form. Numerical results are presented. Copyright © 2001 John Wiley & Sons, Ltd.     

Rayleigh quotient algorithms for nonsymmetric matrix pencils

A classical Rayleigh-quotient iterative algorithm (known as “broken iteration”) for finding eigenvalues and eigenvectors is applied to semisimple regular matrix pencils A − λB. It is proved that cubic convergence is attained for eigenvalues and superlinear convergence of order three for eigenvectors. Also, each eigenvalue has a local basin of attraction. A closely related Newton algorithm is examined. Numerical examples are included. Dedicated to the memory of Gene H. Golub.     

FAST PARALLELIZABLE METHODS FOR COMPUTING INVARIANT SUBSPACES OF HERMITIAN MATRICES

We propose a quadratically convergent algorithm for computing the invariant subspaces of an Hermitian matrix. Each iteration of the algorithm consists of one matrix-matrix multiplication and one QR decomposition. We present an accurate convergence analysis of the algorithm without using the big O notation. We also propose a general framework based on implicit rational transformations which allows us to make connections with several existing algorithms and to derive classes of extensions to our basic algorithm with faster convergence rates. Several numerical examples are given which compare some aspects of the existing algorithms and the new algorithms.     

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.     

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.     

计算对称带状矩阵广义特征值问题的并行分治多分法

1 引 言 本文研究了广义特征值问题 Ax=λBx (1)的并行计算。其中,A,B均为半带宽为r的n阶实对称带状矩阵且其中之一是正定的.本文总假设B是正定的.     

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.     

A derivative-free three-term projection algorithm involving spectral quotient for solving nonlinear monotone equations

ABSTRACT

In this paper, we develop a three-term conjugate gradient method involving spectral quotient, which always satisfies the famous Dai-Liao conjugacy condition and quasi-Newton secant equation, independently of any line search. This new three-term conjugate gradient method can be regarded as a variant of the memoryless Broyden-Fletcher-Goldfarb-Shanno quasi-Newton method with regard to spectral quotient. By combining this method with the projection technique proposed by Solodov and Svaiter in 1998, we establish a derivative-free three-term projection algorithm for dealing with large-scale nonlinear monotone system of equations. We prove the global convergence of the algorithm and obtain the R-linear convergence rate under some mild conditions. Numerical results show that our projection algorithm is effective and robust, and is more competitive with the TTDFP algorithm proposed Liu and Li [A three-term derivative-free projection method for nonlinear monotone system of equations. Calcolo. 2016;53:427–450].     

Numerical Solution of the Two-Sided Space–Time Fractional Telegraph Equation Via Chebyshev Tau Approximation

The operational matrices of left Caputo fractional derivative, right Caputo fractional derivative, and Riemann–Liouville fractional integral, for shifted Chebyshev polynomials, are presented and derived. We propose an accurate and efficient spectral algorithm for the numerical solution of the two-sided space–time Caputo fractional-order telegraph equation with three types of non-homogeneous boundary conditions, namely, Dirichlet, Robin, and non-local conditions. The proposed algorithm is based on shifted Chebyshev tau technique combined with the derived shifted Chebyshev operational matrices. We focus primarily on implementing the novel algorithm both in temporal and spatial discretizations. This algorithm reduces the problem to a system of algebraic equations greatly simplifying the problem. This system can be solved by any standard iteration method. For confirming the efficiency and accuracy of the proposed scheme, we introduce some numerical examples with their approximate solutions and compare our results with those achieved using other methods.