Improved global algorithms for maximal eigenpair

This paper is a continuation of our previous paper [Front. Math. China, 2017, 12(5): 1023{1043] where global algorithms for computing the maximal eigenpair were introduced in a rather general setup. The efficiency of the global algorithms is improved in this paper in terms of a good use of power iteration and two quasi-symmetric techniques. Finally, the new algorithms are applied to Hua's economic optimization model.     

Development of powerful algorithm for maximal eigenpair

Based on a series of recent papers, a powerful algorithm is reformulated for computing the maximal eigenpair of self-adjoint complex tridiagonal matrices. In parallel, the same problem in a particular case for computing the sub-maximal eigenpair is also introduced. The key ideas for each critical improvement are explained. To illustrate the present algorithm and compare it with the related algorithms, more than 10 examples are included.     

A perturbation result for the asymptotic behavior of matrix powers

We prove a perturbation result for the asymptotic behavior of the sequence (A ⁿ c) _nN , whereAG|(d), the space of invertibled×d matrices, andc ^d .     

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.     

Convergence theory of exact interpolation scheme for computing several eigenvectors

An asymptotic convergence analysis of a new multilevel method for numerical solution of eigenvalues and eigenvectors of symmetric and positive definite matrices is performed. The analyzed method is a generalization of the original method that has recently been proposed by R. Ku?el and P. Vaněk (DOI: 10.1002/nla.1975) and uses a standard multigrid prolongator matrix enriched by one full column vector, which approximates the first eigenvector. The new generalized eigensolver is designed to compute eigenvectors. Their asymptotic convergence in terms of the generalized residuals is proved, and its convergence factor is estimated. The theoretical analysis is illustrated by numerical examples. Copyright © 2015 John Wiley & Sons, Ltd.     

求解PageRank问题的多步幂法修正的内外迭代法

引用两种加速计算PageRank的算法,分别为内外迭代法和两步分裂迭代算法.从这两种方法中,得到多步幂法修正的内外迭代方法.首先,详细介绍了算法实施过程.然后,对此算法的收敛性进行证明,并且将此算法的谱半径与两步分裂迭代算法的谱半径进行比较.最后,数值试验说明该算法的计算速度比两步分裂迭代法要快.     

Homotopy method for the numerical solution of the eigenvalue problem of self-adjoint partial differential operators

GivenA ₁, the discrete approximation of a linear self-adjoint partial differential operator, the smallest few eigenvalues and eigenvectors ofA ₁ are computed by the homotopy (continuation) method. The idea of the method is very simple. From some initial operatorA ₀ with known eigenvalues and eigenvectors, define the homotopyH(t)=(1–t)A ₀+tA₁, 0t1. If the eigenvectors ofH(t ₀) are known, then they are used to determine the eigenpairs ofH(t ₀+dt) via the Rayleigh quotient iteration, for some value ofdt. This is repeated untilt becomes 1, when the solution to the original problem is found. A fundamental problem is the selection of the step sizedt. A simple criterion to selectdt is given. It is shown that the iterative solver used to find the eigenvector at each step can be stabilized by applying a low-rank perturbation to the relevant matrix. By carrying out a small part of the calculation in higher precision, it is demonstrated that eigenvectors corresponding to clustered eigenvalues can be computed to high accuracy. Some numerical results for the Schrödinger eigenvalue problem are given. This algorithm will also be used to compute the bifurcation point of a parametrized partial differential equation.Dedicated to Herbert Bishop Keller on the occasion of his 70th birthdayThe work of this author was in part supported by RGC Grant DAG93/94.SC30.The work of this author was in part supported by NSF Grant DMS-9403899.     

一般边界条件下Sturm-Liouville算子的Ambarzumyan型定理

该文研究有限区间上一般自伴边界条件下的Sturm-Liouville方程的逆特征值问题.将Neumann边界条件下Sturm-Liouville方程的Ambarzumyan型定理推广到一般自伴边界条件下情形,证明了如果它的特征值与零势的特征值一样,则Sturm-Liouville方程的势为零.     

High‐performance direct algorithms for computing the sign function of triangular matrices

Algorithms and implementations for computing the sign function of a triangular matrix are fundamental building blocks for computing the sign of arbitrary square real or complex matrices. We present novel recursive and cache‐efficient algorithms that are based on Higham's stabilized specialization of Parlett's substitution algorithm for computing the sign of a triangular matrix. We show that the new recursive algorithms are asymptotically optimal in terms of the number of cache misses that they generate. One algorithm that we present performs more arithmetic than the nonrecursive version, but this allows it to benefit from calling highly optimized matrix multiplication routines; the other performs the same number of operations as the nonrecursive version, suing custom computational kernels instead. We present implementations of both, as well as a cache‐efficient implementation of a block version of Parlett's algorithm. Our experiments demonstrate that the blocked and recursive versions are much faster than the previous algorithms and that the inertia strongly influences their relative performance, as predicted by our analysis.     

New schemes with fractal error compensation for PDE eigenvalue computations

With an error compensation term in the fractal Rayleigh quotient of PDE eigen-problems,we propose a new scheme by perturbing the mass matrix Mhto Mh=Mh+Ch2mKh,where Khis the corresponding stif matrix of a 2m 1 degree conforming finite element with mesh size h for a 2m-order self-adjoint PDE,and the constant C exists in the priority error estimationλh jλj~Ch2mλ2j.In particular,for Laplace eigenproblems over regular domains in uniform mesh,e.g.,cube,equilateral triangle and regular hexagon,etc.,we find the constant C=I h 1Mh2 hKh and show that in this case the computation accuracy can raise two orders,i.e.,fromλh jλj=O(h2)to O(h4).Some numerical tests in 2-D and 3-D are given to verify the above arguments.     

Finding the Maximal Eigenpair for a Large,Dense,Symmetric Matrix based on Mufa Chen's Algorithm

A hybrid method is presented for determining maximal eigenvalue and its eigenvector(called eigenpair)of a large,dense,symmetric matrix.Many problems require finding only a small part of the eigenpairs,and some require only the maximal one.In a series of papers,efficient algorithms have been developed by Mufa Chen for computing the maximal eigenpairs of tridiagonal matrices with positive off-diagonal elements.The key idea is to explicitly construet effective initial guess of the maximal eigenpair and then to employ a self-closed iterative algorithm.In this paper we will extend Mufa Chen's algorithm to find maximal eigenpair for a large scale,dense,symmetric matrix.Our strategy is to first convert the underlying matrix into the tridiagonal form by using similarity transformations.We then handle the cases that prevent us from applying Chen's algorithm directly,e.g.,the cases with zero or negative super-or sub-diagonal elements.Serval numerical experiments are carried out to demonstrate the efficiency of the proposed hybrid method.     

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.     

Efficient algorithms for computing rank-revealing factorizations on a GPU

Standard rank-revealing factorizations such as the singular value decomposition (SVD) and column pivoted QR factorization are challenging to implement efficiently on a GPU. A major difficulty in this regard is the inability of standard algorithms to cast most operations in terms of the Level-3 BLAS. This article presents two alternative algorithms for computing a rank-revealing factorization of the form $\mathsf{A}=\mathsf{U}\mathsf{T}{\mathsf{V}}^{\ast }$, where $\mathsf{U}$ and $\mathsf{V}$ are orthogonal and $\mathsf{T}$ is trapezoidal (or triangular if $\mathsf{A}$ is square). Both algorithms use randomized projection techniques to cast most of the flops in terms of matrix-matrix multiplication, which is exceptionally efficient on the GPU. Numerical experiments illustrate that these algorithms achieve significant acceleration over finely tuned GPU implementations of the SVD while providing low rank approximation errors close to that of the SVD.     

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.     

On a matrix-based measure of the degree of coreness of a node in a network

The paper focuses on the right and left eigenvectors of a network matrix that belong to the largest eigenvalue. It is shown that each of vector entries measures the walk centrality of the corresponding node’s position in the network’s link structure and of the positions of the node’s adjacent nodes; as a result, it indicates to which degree the node can be associated with the structure’s core, i.e., the structural coreness of the node. The relationship between the vectors’ coordinates and the position of the nodes, as well as the actual computation of the coordinates, is based on an iterative computational scheme known as the power method. The paper studies the method’s convergence for networks of different structure. Some possible applications are discussed. The paper also includes a numerical example dealing with a real network of 197 nodes and 780 links.     

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.     

Efficient orthogonal matrix polynomial based method for computing matrix exponential

The matrix exponential plays a fundamental role in the solution of differential systems which appear in different science fields. This paper presents an efficient method for computing matrix exponentials based on Hermite matrix polynomial expansions. Hermite series truncation together with scaling and squaring and the application of floating point arithmetic bounds to the intermediate results provide excellent accuracy results compared with the best acknowledged computational methods. A backward-error analysis of the approximation in exact arithmetic is given. This analysis is used to provide a theoretical estimate for the optimal scaling of matrices. Two algorithms based on this method have been implemented as MATLAB functions. They have been compared with MATLAB functions funm and expm obtaining greater accuracy in the majority of tests. A careful cost comparison analysis with expm is provided showing that the proposed algorithms have lower maximum cost for some matrix norm intervals. Numerical tests show that the application of floating point arithmetic bounds to the intermediate results may reduce considerably computational costs, reaching in numerical tests relative higher average costs than expm of only 4.43% for the final Hermite selected order, and obtaining better accuracy results in the 77.36% of the test matrices. The MATLAB implementation of the best Hermite matrix polynomial based algorithm has been made available online.     

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     

Efficient algorithms for computing the largest eigenvalue of a nonnegative tensor

Consider the problem of computing the largest eigenvalue for nonnegative tensors. In this paper, we establish the Q-linear convergence of a power type algorithm for this problem under a weak irreducibility condition. Moreover, we present a convergent algorithm for calculating the largest eigenvalue for any nonnegative tensors.     

基于拟相对内部集值优化问题弱有效元的最优性条件

本文研究了基于拟相对内部的非凸集值优化问题弱有效元的最优性条件.首先,讨论了弱有效元与线性子空间之间的关系,利用涉及拟相对内部的凸集分离定理,获得了弱有效元的最优性条件.其次,给出了基于拟相对内部弱有效元的Lagrange乘子定理.