Error Analysis of the Symplectic Lanczos Method for the Symplectic Eigenvalue Problem

A rounding error analysis of the symplectic Lanczos algorithm for the symplectic eigenvalue problem is given. It is applicable when no break down occurs and shows that the restriction of preserving the symplectic structure does not destroy the characteristic feature of nonsymmetric Lanczos processes. An analog of Paige's theory on the relationship between the loss of orthogonality among the Lanczos vectors and the convergence of Ritz values in the symmetric Lanczos algorithm is discussed. As to be expected, it follows that (under certain assumptions) the computed J-orthogonal Lanczos vectors loose J-orthogonality when some Ritz values begin to converge.     

求解大规模Hamilton矩阵特征问题的辛Lanczos算法的误差分析

对求解大规模稀疏Hamilton矩阵特征问题的辛Lanczos算法给出了舍入误差分析.分析表明辛Lanczos算法在无中断时,保Hamilton结构的限制没有破坏非对称Lanczos算法的本质特性.本文还讨论了辛Lanczos算法计算出的辛Lanczos向量的J一正交性的损失与Ritz值收敛的关系.结论正如所料,当某些Ritz值开始收敛时.计算出的辛Lanczos向量的J-正交性损失是必然的.以上结果对辛Lanczos算法的改进具有理论指导意义.     

求解大规模非对称矩阵特征问题的精化双正交Lanczos算法

We combine Lanczos algorithm with the thought of the refined projection method using QR factorization and propose the refined biothogonalization Lanczos method for computing the desired eigenvalues of large unsymmetric matrix. With low cost of work space and flops the algorithm cures the disease that the Ritz vectors may not converge when the Ritz values converge usingthe Lanczos method. Numerical experiments show our algorithm is considerably more stable and efficient than its counterpart.     

计算大规模矩阵最大最小奇异值和奇异向量的两个精化Lanczos算法

1.引言 在科学工程计算中经常需要计算大规模矩阵的少数最大或最小的奇异值及其所对应的奇异子空间。例如图像处理中要计算矩阵端部奇异值之比作为图像的分辨率,诸如此类的问题还存在于最小二乘问题、控制理论、量子化学中等等。然而大多实际问题中的矩阵是大型稀疏矩阵,且需要的是矩阵的部分奇异对。如果计算A的完全奇异值分解(SVD),则运算量和存储量极大,甚至不可能。因此必须寻求其它有效可靠的算法。 假设A的SVD为     

A QUASI-REFINED ITERATIVE ALGORITHM BASED ON THE LANCZOS BIORTHOGONALIZATION PROCEDURE FOR LARGE EIGENPROBLEMS

The two-sided Lanczos method is popular for computing a few selected eigentriplets of large non-Hermitian matrices. However, it has been revealed that theRitz vectors gained by this method may not converge even if the subspaces are good enough and the associated eigenvalues converge. In order to remedy this drawback, a novel method is proposed which is based on the refined strategy, the quasi-refined ideaand the Lanczos biothogonalization procedure, the resulting algorithm is presented. Therelationship between the new method and the classical oblique projection technique isalso established. We report some numericalwith the conventional one, the results showthe latter.experiments and compare the new algorithmthat the former is often more powerful than     

A Hamiltonian Krylov-Schur-type method based on the symplectic Lanczos process

We discuss a Krylov-Schur like restarting technique applied within the symplectic Lanczos algorithm for the Hamiltonian eigenvalue problem. This allows us to easily implement a purging and locking strategy in order to improve the convergence properties of the symplectic Lanczos algorithm. The Krylov-Schur-like restarting is based on the SR algorithm. Some ingredients of the latter need to be adapted to the structure of the symplectic Lanczos recursion. We demonstrate the efficiency of the new method for several Hamiltonian eigenproblems.     

Generalized block Lanczos methods for large unsymmetric eigenproblems

Generalized block Lanczos methods for large unsymmetric eigenproblems are presented, which contain the block Arnoldi method, and the block Arnoldi algorithms are developed. The convergence of this class of methods is analyzed when the matrix A is diagonalizable. Upper bounds for the distances between normalized eigenvectors and a block Krylov subspace are derived, and a priori theoretical error bounds for Ritz elements are established. Compared with generalized Lanczos methods, which contain Arnoldi's method, the convergence analysis shows that the block versions have two advantages: First, they may be efficient for computing clustered eigenvalues; second, they are able to solve multiple eigenproblems. However, a deep analysis exposes that the approximate eigenvectors or Ritz vectors obtained by general orthogonal projection methods including generalized block methods may fail to converge theoretically for a general unsymmetric matrix A even if corresponding approximate eigenvalues or Ritz values do, since the convergence of Ritz vectors needs more sufficient conditions, which may be impossible to satisfy theoretically, than that of Ritz values does. The issues of how to restart and to solve multiple eigenproblems are addressed, and some numerical examples are reported to confirm the theoretical analysis. Received July 7, 1994 / Revised version received March 1, 1997     

IMPROVING EIGENVECTORS IN ARNOLDI'S METHOD

1. IntroductionArnoldi's method [1, 12] is used for computing.,a few selected eigenpairs of largeunsymmetric matrices. It hajs been investigated since the 1980s; see, e-g., [3--15].It is well known that the m--step Arnoldi processt as described in detail in Section 2,generates an orthonormal basis {yi}7=1 of the Krylov subspace Km(vi, A) spanned byvil Avi,... 5 Am--'v,. Here yi is an initial unit norm vector. The projected matrix ofA onto Km(vi, A) is represented by an m x m upper Hessenb…     

Orthogonal similarity transformation into block‐semiseparable matrices of semiseparability rank k

Very recently, an algorithm, which reduces any symmetric matrix into a semiseparable one of semi‐ separability rank 1 by similar orthogonality transformations, has been proposed by Vandebril, Van Barel and Mastronardi. Partial execution of this algorithm computes a semiseparable matrix whose eigenvalues are the Ritz‐values obtained by the Lanczos' process applied to the original matrix. Also a kind of nested subspace iteration is performed at each step. In this paper, we generalize the above results and propose an algorithm to reduce any symmetric matrix into a similar block‐semiseparable one of semiseparability rank k, with k ∈ ?, by orthogonal similarity transformations. Also in this case partial execution of the algorithm computes a block‐semiseparable matrix whose eigenvalues are the Ritz‐values obtained by the block‐Lanczos' process with k starting vectors, applied to the original matrix. Subspace iteration is performed at each step as well. Copyright © 2005 John Wiley & Sons, Ltd.     

A VARIATION ON THE BLOCK ARNOLDIMETHOD FOR LARGE UNSYMMETRIC MATRIX EIGENPROBLEMS

1.IntroductionLarge-scalematrixeigenproblemsariseinappliedsciencesandmanyengineeringapplications.Arnoldi'smethod[1'2]anditsblockversion[3--6]areverypopularforsolvingthem.Thesemethodshavebeenintensivelyinvestigatedsincethe1980s,bothintheoryandinalgorithms;wereferto[7--17]fordetails.WhenmstepsoftheblockArnoldiprocessareperformed,anorthonormalbasis{K}7=1oftheblockKrylovsubspaceK.(VI,A)spannedbyVI5AVI,'IAm--1VIisgenerated,whereVIisaninitialNxporthogonalmatrix,andtherestrictionofAtoKm(V…     

A numerical solution of the constrained weighted energy problem

A numerical algorithm is presented to solve the constrained weighted energy problem from potential theory. As one of the possible applications of this algorithm, we study the convergence properties of the rational Lanczos iteration method for the symmetric eigenvalue problem. The constrained weighted energy problem characterizes the region containing those eigenvalues that are well approximated by the Ritz values. The region depends on the distribution of the eigenvalues, on the distribution of the poles, and on the ratio between the size of the matrix and the number of iterations. Our algorithm gives the possibility of finding the boundary of this region in an effective way.We give numerical examples for different distributions of poles and eigenvalues and compare the results of our algorithm with the convergence behavior of the explicitly performed rational Lanczos algorithm.     

调和Arnoldi方法的一种变形

讨论求解大规模非对称矩阵内部特征问题的一种方法,与标准的调和A rnold i方法相比,该方法仍用调和R itz值作为特征值的近似,而在近似特征向量选取方面,我们充分利用A rnold i过程所提供的最末一个基向量的信息,在多1维K ry lov子空间中选取一个向量-称之为改进的调和R itz向量-作为所求的特征向量的近似.理论分析和数值试验均表明这种变形的调和A rnold i方法的可行性和有效性.     

Limited memory preconditioners for symmetric indefinite problems with application to structural mechanics

This paper presents a class of limited memory preconditioners (LMP) for solving linear systems of equations with symmetric indefinite matrices and multiple right‐hand sides. These preconditioners based on limited memory quasi‐Newton formulas require a small number k of linearly independent vectors and may be used to improve an existing first‐level preconditioner. The contributions of the paper are threefold. First, we derive a formula to characterize the spectrum of the preconditioned operator. A spectral analysis of the preconditioned matrix shows that the eigenvalues are all real and that the LMP class is able to cluster at least k eigenvalues at 1. Secondly, we show that the eigenvalues of the preconditioned matrix enjoy interlacing properties with respect to the eigenvalues of the original matrix provided that the k linearly independent vectors have been prior projected onto the invariant subspaces associated with the eigenvalues of the original matrix in the open right and left half‐plane, respectively. Third, we focus on theoretical properties of the Ritz‐LMP variant, where Ritz information is used to determine the k vectors. Finally, we illustrate the numerical behaviour of the Ritz limited memory preconditioners on realistic applications in structural mechanics that require the solution of sequences of large‐scale symmetric saddle‐point systems. Numerical experiments show the relevance of the proposed preconditioner leading to a significant decrease in terms of computational operations when solving such sequences of linear systems. A saving of up to 43% in terms of computational effort is obtained on one of these applications. Copyright © 2016 John Wiley & Sons, Ltd.     

Constructing integrable systems of semitoric type

Let (M, ω) be a connected, symplectic 4-manifold. A semitoric integrable system on (M, ω) essentially consists of a pair of independent, real-valued, smooth functions J and H on M, for which J generates a Hamiltonian circle action under which H is invariant. In this paper we give a general method to construct, starting from a collection of five ingredients, a symplectic 4-manifold equipped a semitoric integrable system. Then we show that every semitoric integrable system on a symplectic 4-manifold is obtained in this fashion. In conjunction with the uniqueness theorem proved recently by the authors, this gives a classification of semitoric integrable systems on 4-manifolds, in terms of five invariants.     

A Variant of the Inverted Lanczos Method

In this note we study a variant of the inverted Lanczos method which computes eigenvalue approximates of a symmetric matrix A as Ritz values of A from a Krylov space of A ^–1. The method turns out to be slightly faster than the Lanczos method at least as long as reorthogonalization is not required. The method is applied to the problem of determining the smallest eigenvalue of a symmetric Toeplitz matrix. It is accelerated taking advantage of symmetry properties of the correspond ng eigenvector.This revised version was published online in October 2005 with corrections to the Cover Date.     

A new load-dependent Ritz vector method for structural dynamics analyses: quasi-static Ritz vectors

Existing load-dependent Ritz vector (LDRV) methods employ static recurrence procedures to generate the Ritz vectors. As such, these vector methods are best suited for low-frequency problems. For higher-frequency problems, the existing methods may engender large sets of Ritz vectors, which significantly reduces the methods’ efficiency. A new algorithm is presented for LDRV generation using a quasi-static recurrence procedure, denoted as the quasi-static Ritz vector (QSRV) method. A tuning parameter, designated as the centering frequency, controls the behavior of the QSRV approach, enabling the new method to improve upon existing LDRV methods for particular frequency ranges of interest. Compared with existing LDRV methods, the QSRV method is more efficient (in terms of the number of Ritz vectors), more accurate (in terms of response errors), and more stable (in terms of orthogonality). Numerical examples are provided to illustrate the accuracy, efficiency and generality of the proposed method.     

The Rayleigh-Ritz method, refinement and Arnoldi process for periodic matrix pairs

We extend the Rayleigh-Ritz method to the eigen-problem of periodic matrix pairs. Assuming that the deviations of the desired periodic eigenvectors from the corresponding periodic subspaces tend to zero, we show that there exist periodic Ritz values that converge to the desired periodic eigenvalues unconditionally, yet the periodic Ritz vectors may fail to converge. To overcome this potential problem, we minimize residuals formed with periodic Ritz values to produce the refined periodic Ritz vectors, which converge under the same assumption. These results generalize the corresponding well-known ones for Rayleigh-Ritz approximations and their refinement for non-periodic eigen-problems. In addition, we consider a periodic Arnoldi process which is particularly efficient when coupled with the Rayleigh-Ritz method with refinement. The numerical results illustrate that the refinement procedure produces excellent approximations to the original periodic eigenvectors.     

Restarted block Lanczos bidiagonalization methods

The problem of computing a few of the largest or smallest singular values and associated singular vectors of a large matrix arises in many applications. This paper describes restarted block Lanczos bidiagonalization methods based on augmentation of Ritz vectors or harmonic Ritz vectors by block Krylov subspaces. Research supported in part by NSF grant DMS-0107858, NSF grant DMS-0311786, and an OBR Research Challenge Grant.     

A limited memory steepest descent method

The possibilities inherent in steepest descent methods have been considerably amplified by the introduction of the Barzilai–Borwein choice of step-size, and other related ideas. These methods have proved to be competitive with conjugate gradient methods for the minimization of large dimension unconstrained minimization problems. This paper suggests a method which is able to take advantage of the availability of a few additional ‘long’ vectors of storage to achieve a significant improvement in performance, both for quadratic and non-quadratic objective functions. It makes use of certain Ritz values related to the Lanczos process (Lanczos in J Res Nat Bur Stand 45:255–282, 1950). Some underlying theory is provided, and numerical evidence is set out showing that the new method provides a competitive and more simple alternative to the state of the art l-BFGS limited memory 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.