计算最小奇异组的一个精化调和 Lanczos双对角化方法

在很多实际应用中需要计算大规模矩阵的若干个最小奇异组.调和投影方法是计算内部特征对的常用方法,其原理可用于求解大规模奇异值分解问题.本文证明了,当投影空间足够好时,该方法得到的近似奇异值收敛,但近似奇异向量可能收敛很慢甚至不收敛.根据第二作者近年来提出的精化投影方法的原理,本文提出一种精化的调和Lanczos双对角化方法,证明了它的收敛性.然后将该方法与Sorensen提出的隐式重新启动技术相结合,开发出隐式重新启动的调和Lanczos双对角化算法(IRHLB)和隐式重新启动的精化调和Lanczos双对角化算法(IRRHLB).位移的合理选取是算法成功的关键之一,本文对精化算法提出了一种新的位移策略,称之为"精化调和位移".理论分析表明,精化调和位移比IRHLB中所用的调和位移要好,且可以廉价可靠地计算出来.数值实验表明,IRRHLB比IRHLB要显著优越,而且比目前常用的隐式重新启动的Lanczos双对角化方法(IRLB)和精化算法IRRLB更有效.     

Linear system solution by null‐space approximation and projection (SNAP)

Solutions of large sparse linear systems of equations are usually obtained iteratively by constructing a smaller dimensional subspace such as a Krylov subspace. The convergence of these methods is sometimes hampered by the presence of small eigenvalues, in which case, some form of deflation can help improve convergence. The method presented in this paper enables the solution to be approximated by focusing the attention directly on the ‘small’ eigenspace (‘singular vector’ space). It is based on embedding the solution of the linear system within the eigenvalue problem (singular value problem) in order to facilitate the direct use of methods such as implicitly restarted Arnoldi or Jacobi–Davidson for the linear system solution. The proposed method, called ‘solution by null‐space approximation and projection’ (SNAP), differs from other similar approaches in that it converts the non‐homogeneous system into a homogeneous one by constructing an annihilator of the right‐hand side. The solution then lies in the null space of the resulting matrix. We examine the construction of a sequence of approximate null spaces using a Jacobi–Davidson style singular value decomposition method, called restarted SNAP‐JD, from which an approximate solution can be obtained. Relevant theory is discussed and the method is illustrated by numerical examples where SNAP is compared with both GMRES and GMRES‐IR. Copyright © 2006 John Wiley & Sons, Ltd.     

隐式重启精化全局Lanczos方法

The numerical methods for solving large symmetric eigenvalue problems are considered in this paper.Based on the global Lanczos process,a global Lanczos method for solving large symmetric eigenvalue problems is presented.In order to accelerate the convergence of the F-Ritz vectors,the refined global Lanczos method is developed.Combining the implicitly restarted strategy with the deflation technique,an implicitly restarted and refined global Lanczos method for computing some eigenvalues of large symmetric matrices is proposed.Numerical results show that the proposed methods are efficient.     

Jacobi–Davidson methods for cubic eigenvalue problems

Several Jacobi–Davidson type methods are proposed for computing interior eigenpairs of large‐scale cubic eigenvalue problems. To successively compute the eigenpairs, a novel explicit non‐equivalence deflation method with low‐rank updates is developed and analysed. Various techniques such as locking, search direction transformation, restarting, and preconditioning are incorporated into the methods to improve stability and efficiency. A semiconductor quantum dot model is given as an example to illustrate the cubic nature of the eigenvalue system resulting from the finite difference approximation. Numerical results of this model are given to demonstrate the convergence and effectiveness of the methods. Comparison results are also provided to indicate advantages and disadvantages among the various methods. Copyright © 2004 John Wiley & Sons, Ltd.     

A Jacobi–Davidson method for two‐real‐parameter nonlinear eigenvalue problems arising from delay‐differential equations

The critical delays of a delay‐differential equation can be computed by solving a nonlinear two‐parameter eigenvalue problem. The solution of this two‐parameter problem can be translated to solving a quadratic eigenvalue problem of squared dimension. We present a structure preserving QR‐type method for solving such quadratic eigenvalue problem that only computes real‐valued critical delays; that is, complex critical delays, which have no physical meaning, are discarded. For large‐scale problems, we propose new correction equations for a Newton‐type or Jacobi–Davidson style method, which also forces real‐valued critical delays. We present three different equations: one real‐valued equation using a direct linear system solver, one complex valued equation using a direct linear system solver, and one Jacobi–Davidson style correction equation that is suitable for an iterative linear system solver. We show numerical examples for large‐scale problems arising from PDEs. Copyright © 2012 John Wiley & Sons, Ltd.     

Local preconditioners for two‐level non‐overlapping domain decomposition methods

We consider additive two‐level preconditioners, with a local and a global component, for the Schur complement system arising in non‐overlapping domain decomposition methods. We propose two new parallelizable local preconditioners. The first one is a computationally cheap but numerically relevant alternative to the classical block Jacobi preconditioner. The second one exploits all the information from the local Schur complement matrices and demonstrates an attractive numerical behaviour on heterogeneous and anisotropic problems. We also propose two implementations based on approximate Schur complement matrices that are cheaper alternatives to construct the given preconditioners but that preserve their good numerical behaviour. Through extensive computational experiments we study the numerical scalability and the robustness of the proposed preconditioners and compare their numerical performance with well‐known robust preconditioners such as BPS and the balancing Neumann–Neumann method. Finally, we describe a parallel implementation on distributed memory computers of some of the proposed techniques and report parallel performances. Copyright © 2001 John Wiley & Sons, Ltd.     

Tuned preconditioners for inexact two‐sided inverse and Rayleigh quotient iteration

Convergence results are provided for inexact two‐sided inverse and Rayleigh quotient iteration, which extend the previously established results to the generalized non‐Hermitian eigenproblem and inexact solves with a decreasing solve tolerance. Moreover, the simultaneous solution of the forward and adjoint problem arising in two‐sided methods is considered, and the successful tuning strategy for preconditioners is extended to two‐sided methods, creating a novel way of preconditioning two‐sided algorithms. Furthermore, it is shown that inexact two‐sided Rayleigh quotient iteration and the inexact two‐sided Jacobi‐Davidson method (without subspace expansion) applied to the generalized preconditioned eigenvalue problem are equivalent when a certain number of steps of a Petrov–Galerkin–Krylov method is used and when this specific tuning strategy is applied. Copyright © 2014 John Wiley & Sons, Ltd.     

IRAM‐based method for eigenpairs and their derivatives of large matrix‐valued functions

Based on the implicitly restarted Arnoldi method for eigenpairs of large matrix, a new method is presented for the computation of a few eigenpairs and their derivatives of large matrix‐valued functions. Eigenpairs and their derivatives are calculated simultaneously. Equation systems that are solved for eigenvector derivatives are greatly reduced from the original matrix size. The left eigenvectors are not required. Hence, the computational cost is saved. The convergence theory of the proposed method is established. Finally, numerical experiments are given to illustrate the efficiency of the proposed method. Copyright © 2010 John Wiley & Sons, Ltd.     

Approximate eigensolution of Laplacian matrices for locally modified graph products

Laplacian matrices and their spectrum are of great importance in algebraic graph theory. There exist efficient formulations for eigensolutions of the Laplacian matrices associated with a special class of graphs called product graphs. In this paper, the problem of determining a few approximate smallest eigenvalues and eigenvectors of large scale product graphs modified through the addition or deletion of some nodes and/or members, is investigated. The eigenproblem associated with a modified graph model is reduced using the set of master eigenvectors and linear approximated slave eigenvectors from the original model. Implicitly restarted Lanczos method is employed to obtain the required eigenpairs of the reduced problem. Examples of large scale models are included to demonstrate the efficiency of the proposed method compared to the direct application of the IRL method.     

计算部分奇异值分解的隐式重新启动的双对角化Lanczos方法和精化的双对角化Lanczos方法

The singular value decomposition problem is mathematically equivalent to the eigenproblem of an argumented matrix. Golub et al. give a bidiagonalization Lanczos method for computing a number of largest or smallest singular values and corresponding singular vertors, but the method may encounter some convergence problems. In this paper we analyse the convergence of the method and show why it may fail to converge. To correct this possible nonconvergence, we propose a refined bidiagonalization Lanczos method and apply the implicitly restarting technique to it, and we then present an implicitly restarted bidiagonalization Lanczos algorithm(IRBL) and an implicitly restarted refined bidiagonalization Lanczos algorithm (IRRBL). A new implicitly restarting scheme and a reliable and efficient algorithm for computing refined shifts are developed for this special structure eigenproblem.Theoretical analysis and numerical experiments show that IRRBL performs much better than IRBL.     

The convergence of Jacobi–Davidson iterations for Hermitian eigenproblems

Rayleigh quotient iteration is an iterative method with some attractive convergence properties for finding (interior) eigenvalues of large sparse Hermitian matrices. However, the method requires the accurate (and, hence, often expensive) solution of a linear system in every iteration step. Unfortunately, replacing the exact solution with a cheaper approximation may destroy the convergence. The (Jacobi‐) Davidson correction equation can be seen as a solution for this problem. In this paper we deduce quantitative results to support this viewpoint and we relate it to other methods. This should make some of the experimental observations in practice more quantitative in the Hermitian case. Asymptotic convergence bounds are given for fixed preconditioners and for the special case if the correction equation is solved with some fixed relative residual precision. A dynamic tolerance is proposed and some numerical illustration is presented. Copyright © 2002 John Wiley & Sons, Ltd.     

A family of constrained pressure residual preconditioners for parallel reservoir simulations

Large‐scale reservoir simulations are extremely time‐consuming because of the solution of large‐scale linear systems arising from the Newton or Newton–Raphson iterations. The problem becomes even worse when highly heterogeneous geological models are employed. This paper introduces a family of multi‐stage preconditioners for parallel black oil simulations, which are based on the famous constrained pressure residual preconditioner. Numerical experiments demonstrate that our preconditioners are robust, efficient, and scalable. Copyright © 2015 John Wiley & Sons, Ltd.     

Approximate eigensolution of Laplacian matrices for locally modified graph products

Laplacian matrices and their spectrum are of great importance in algebraic graph theory. There exist efficient formulations for eigensolutions of the Laplacian matrices associated with a special class of graphs called product graphs. In this paper, the problem of determining a few approximate smallest eigenvalues and eigenvectors of large scale product graphs modified through the addition or deletion of some nodes and/or members, is investigated. The eigenproblem associated with a modified graph model is reduced using the set of master eigenvectors and linear approximated slave eigenvectors from the original model. Implicitly restarted Lanczos method is employed to obtain the required eigenpairs of the reduced problem. Examples of large scale models are included to demonstrate the efficiency of the proposed method compared to the direct application of the IRL method.     

An order optimal solver for the discretized bidomain equations

The electrical activity in the heart is governed by the bidomain equations. In this paper, we analyse an order optimal method for the algebraic equations arising from the discretization of this model. Our scheme is defined in terms of block Jacobi or block symmetric Gauss–Seidel preconditioners. Furthermore, each block in these methods is based on standard preconditioners for scalar elliptic or parabolic partial differential equations (PDEs). Such preconditioners can be realized in terms of multigrid or domain decomposition schemes, and are thus readily available by applying ‘off‐the‐shelves’ software. Finally, our theoretical findings are illuminated by a series of numerical experiments. Copyright © 2006 John Wiley & Sons, Ltd.     

Block-Arnoldi and Davidson methods for unsymmetric large eigenvalue problems

Summary We present two methods for computing the leading eigenpairs of large sparse unsymmetric matrices. Namely the block-Arnoldi method and an adaptation of the Davidson method to unsymmetric matrices. We give some theoretical results concerning the convergence and discuss implementation aspects of the two methods. Finally some results of numerical tests on a variety of matrices, in which we compare these two methods are reported.     

Harmonic and refined Rayleigh–Ritz for the polynomial eigenvalue problem

After reviewing the harmonic Rayleigh–Ritz approach for the standard and generalized eigenvalue problem, we discuss several extraction processes for subspace methods for the polynomial eigenvalue problem. We generalize the harmonic and refined Rayleigh–Ritz approaches which lead to new approaches to extract promising approximate eigenpairs from a search space. We give theoretical as well as numerical results of the methods. In addition, we study the convergence of the Jacobi–Davidson method for polynomial eigenvalue problems with exact and inexact linear solves and discuss several algorithmic details. Copyright © 2008 John Wiley & Sons, Ltd.     

Structured preconditioners for nonsingular matrices of block two-by-two structures

For the large sparse block two-by-two real nonsingular matrices, we establish a general framework of practical and efficient structured preconditioners through matrix transformation and matrix approximations. For the specific versions such as modified block Jacobi-type, modified block Gauss-Seidel-type, and modified block unsymmetric (symmetric) Gauss-Seidel-type preconditioners, we precisely describe their concrete expressions and deliberately analyze eigenvalue distributions and positive definiteness of the preconditioned matrices. Also, we show that when these structured preconditioners are employed to precondition the Krylov subspace methods such as GMRES and restarted GMRES, fast and effective iteration solvers can be obtained for the large sparse systems of linear equations with block two-by-two coefficient matrices. In particular, these structured preconditioners can lead to efficient and high-quality preconditioning matrices for some typical matrices from the real-world applications.

     

A Jacobi–Davidson type method with a correction equation tailored for integral operators

We propose two iterative numerical methods for eigenvalue computations of large dimensional problems arising from finite approximations of integral operators, and describe their parallel implementation. A matrix representation of the problem on a space of moderate dimension, defined from an infinite dimensional one, is computed along with its eigenpairs. These are taken as initial approximations and iteratively refined, by means of a correction equation based on the reduced resolvent operator and performed on the moderate size space, to enhance their quality. Each refinement step requires the prolongation of the correction equation solution back to a higher dimensional space, defined from the infinite dimensional one. This approach is particularly adapted for the computation of eigenpair approximations of integral operators, where prolongation and restriction matrices can be easily built making a bridge between coarser and finer discretizations. We propose two methods that apply a Jacobi–Davidson like correction: Multipower Defect-Correction (MPDC), which uses a single-vector scheme, if the eigenvalues to refine are simple, and Rayleigh–Ritz Defect-Correction (RRDC), which is based on a projection onto an expanding subspace. Their main advantage lies in the fact that the correction equation is performed on a smaller space while for general solvers it is done on the higher dimensional one. We discuss implementation and parallelization details, using the PETSc and SLEPc packages. Also, numerical results on an astrophysics application, whose mathematical model involves a weakly singular integral operator, are presented.     

A locally and cubically convergent algorithm for computing 𝒵‐eigenpairs of symmetric tensors

This paper is concerned with computing $\mathrm{??}$‐eigenpairs of symmetric tensors. We first show that computing $\mathrm{??}$‐eigenpairs of a symmetric tensor is equivalent to finding the nonzero solutions of a nonlinear system of equations, and then propose a modified normalized Newton method (MNNM) for it. Our proposed MNNM method is proved to be locally and cubically convergent under some suitable conditions, which greatly improves the Newton correction method and the orthogonal Newton correction method recently provided by Jaffe, Weiss and Nadler since these two methods only enjoy a quadratic rate of convergence. As an application, the unitary symmetric eigenpairs of a complex‐valued symmetric tensor arising from the computation of quantum entanglement in quantum physics are calculated by the MNNM method. Some numerical results are presented to illustrate the efficiency and effectiveness of our method.