Estimating the largest singular values of large sparse matrices via modified moments

We describe a procedure for determining a few of the largest singular values of a large sparse matrix. The method by Golub and Kent which uses the method of modified moments for estimating the eigenvalues of operators used in iterative methods for the solution of linear systems of equations is appropriately modified in order to generate a sequence of bidiagonal matrices whose singular values approximate those of the original sparse matrix. A simple Lanczos recursion is proposed for determining the corresponding left and right singular vectors. The potential asynchronous computation of the bidiagonal matrices using modified moments with the iterations of an adapted Chebyshev semi-iterative (CSI) method is an attractive feature for parallel computers. Comparisons in efficiency and accuracy with an appropriate Lanczos algorithm (with selective re-orthogonalization) are presented on large sparse (rectangular) matrices arising from applications such as information retrieval and seismic reflection tomography. This procedure is essentially motivated by the theory of moments and Gauss quadrature.This author's work was supported by the National Science Foundation under grants NSF CCR-8717492 and CCR-910000N (NCSA), the U.S. Department of Energy under grant DOE DE-FG02-85ER25001, and the Air Force Office of Scientific Research under grant AFOSR-90-0044 while at the University of Illinois at Urbana-Champaign Center for Supercomputing Research and Development.This author's work was supported by the U.S. Army Research Office under grant DAAL03-90-G-0105, and the National Science Foundation under grant NSF DCR-8412314.     

Application of a block modified Chebyshev algorithm to the iterative solution of symmetric linear systems with multiple right hand side vectors

Summary. An adaptive Richardson iteration method is described for the solution of large sparse symmetric positive definite linear systems of equations with multiple right-hand side vectors. This scheme ``learns' about the linear system to be solved by computing inner products of residual matrices during the iterations. These inner products are interpreted as block modified moments. A block version of the modified Chebyshev algorithm is presented which yields a block tridiagonal matrix from the block modified moments and the recursion coefficients of the residual polynomials. The eigenvalues of this block tridiagonal matrix define an interval, which determines the choice of relaxation parameters for Richardson iteration. Only minor modifications are necessary in order to obtain a scheme for the solution of symmetric indefinite linear systems with multiple right-hand side vectors. We outline the changes required. Received April 22, 1993     

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…     

Computing eigenelements of Sturm-Liouville problems by using Daubechies wavelets

This work is our first step to get multiresolution approximation of eigenelements of Sturm-Liouville problems within bounded domain of varied nature. The formula for obtaining elements of representation of Sturm-Liouville operator involving polynomial coefficients in wavelet basis of Daubechies family have been derived in a form which can be readily used for their computations by a simple computer program. Estimates of errors for both the eigenvalues and eigenfunctions are also presented here. The proposed wavelet-Galerkin scheme based on scale functions and wavelets of Daubechies family having three or four vanishing moments of their wavelets has been applied to get approximate eigenelements of regular and singular Sturm-Liouville problems within bounded domain and compared with the exact or approximate results whenever available. From our study it appears that the proposed method is efficient and rapidly convergent in comparison to other approximation schemes based on variational method in Haar basis or finite difference methods studied by Bujurke et al. [39].     

A hybrid iterative method for symmetric positive definite linear systems

A hybrid iterative scheme that combines the Conjugate Gradient (CG) method with Richardson iteration is presented. This scheme is designed for the solution of linear systems of equations with a large sparse symmetric positive definite matrix. The purpose of the CG iterations is to improve an available approximate solution, as well as to determine an interval that contains all, or at least most, of the eigenvalues of the matrix. This interval is used to compute iteration parameters for Richardson iteration. The attraction of the hybrid scheme is that most of the iterations are carried out by the Richardson method, the simplicity of which makes efficient implementation on modern computers possible. Moreover, the hybrid scheme yields, at no additional computational cost, accurate estimates of the extreme eigenvalues of the matrix. Knowledge of these eigenvalues is essential in some applications.Research supported in part by NSF grant DMS-9409422.Research supported in part by NSF grant DMS-9205531.     

A refined iterative algorithm based on the block arnoldi process for large unsymmetric eigenproblems

When the matrix in question is unsymmetric, the approximate eigenvectors or Ritz vectors obtained by orthogonal projection methods including Arnoldi's method and the block Arnoldi method cannot be guaranteed to converge in theory even if the corresponding approximate eigenvalues or Ritz values do. In order to circumvent this danger, a new strategy has been proposed by the author for Arnoldi's method. The strategy used is generalized to the block Arnoldi method in this paper. It discards Ritz vectors and instead computes refined approximate eigenvectors by small-sized singular-value decompositions. It is proved that the new strategy can guarantee the convergence of refined approximate eigenvectors if the corresponding Ritz values do. The resulting refined iterative algorithm is realized by the block Arnoldi process. Numerical experiments show that the refined algorithm is much more efficient than the iterative block Arnoldi algorithm.     

Dealing with linear dependence during the iterations of the restarted block Lanczos methods

The Lanczos method can be generalized to block form to compute multiple eigenvalues without the need of any deflation techniques. The block Lanczos method reduces a general sparse symmetric matrix to a block tridiagonal matrix via a Gram–Schmidt process. During the iterations of the block Lanczos method an off-diagonal block of the block tridiagonal matrix may become singular, implying that the new set of Lanczos vectors are linearly dependent on the previously generated vectors. Unlike the single vector Lanczos method, this occurrence of linearly dependent vectors may not imply an invariant subspace has been computed. This difficulty of a singular off-diagonal block is easily overcome in non-restarted block Lanczos methods, see [12,30]. The same schemes applied in non-restarted block Lanczos methods can also be applied in restarted block Lanczos methods. This allows the largest possible subspace to be built before restarting. However, in some cases a modification of the restart vectors is required or a singular block will continue to reoccur. In this paper we examine the different schemes mentioned in [12,30] for overcoming a singular block for the restarted block Lanczos methods, namely the restarted method reported in [12] and the Implicitly Restarted Block Lanczos (IRBL) method developed by Baglama et al. [3]. Numerical examples are presented to illustrate the different strategies discussed.     

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.     

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     

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

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

Algorithm for min-range multiplication of affine forms

We consider an approximate method based on the alternate trapezoidal quadrature for the eigenvalue problem given by a periodic singular Fredholm integral equation of second kind. For some convolution-type integral kernels, the eigenvalues of the discrete eigenvalue problem provided by the alternate trapezoidal quadrature method have multiplicity at least two, except up to two eigenvalues of multiplicity one. In general, these eigenvalues exhibit some symmetry properties that are not necessarily observed in the eigenvalues of the continuous problem. For a class of Hilbert-type kernels, we provide error estimates that are valid for a subset of the discrete spectrum. This subset is further enlarged in an improved quadrature method presented herein. The results are illustrated through numerical examples.     

An augmented LSQR method

The LSQR iterative method for solving least-squares problems may require many iterations to determine an approximate solution with desired accuracy. This often depends on the fact that singular vector components of the solution associated with small singular values of the matrix require many iterations to be determined. Augmentation of Krylov subspaces with harmonic Ritz vectors often makes it possible to determine the singular vectors associated with small singular values with fewer iterations than without augmentation. This paper describes how Krylov subspaces generated by the LSQR iterative method can be conveniently augmented with harmonic Ritz vectors. Computed examples illustrate the competitiveness of the augmented LSQR method proposed.     

矩阵奇异值分解问题重分析的摄动法

本文提出了一般实矩阵奇异值分解问题重分析的摄动法.这是一种简捷、高效的快速重分析方法,对于提高各种需要反复进行矩阵奇异值分解的迭代分析问题的计算效率具有较重要的实用价值.文中导出了奇异值和左、右奇异向量的直到二阶摄动量的渐近估计算式.文末指出了将这种振动分析方法直接推广到一般复矩阵情况的途径.     

调和Arnoldi方法的一种变形

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

A PROCESS FOR SOLVING A FEW EXTREME EIGENPAIRS OF LARGE SPARSE POSITIVE DEFINITE GENERALIZED EIGENVALUE PROBLEM

1. IntroductionWe are concerned in this work with finding a few extreme eigenvalues and theircorresponding eigenvectors of a generalized large scale eigenvalue problem in which thematrices are sparse and symmetric positive definite.Although finding a few extreme eigenpairs is of interest both in theory and practice,there are only few usable and efficient methods up to now. Reinsch and Baner ([12]),suggested a oR algorithm with Newton shift for the standard eigenproblem which included an ingen…     

An adaptive Chebyshev iterative method\newline for nonsymmetric linear systems based on modified moments

Summary. Large, sparse nonsymmetric systems of linear equations with a matrix whose eigenvalues lie in the right half plane may be solved by an iterative method based on Chebyshev polynomials for an interval in the complex plane. Knowledge of the convex hull of the spectrum of the matrix is required in order to choose parameters upon which the iteration depends. Adaptive Chebyshev algorithms, in which these parameters are determined by using eigenvalue estimates computed by the power method or modifications thereof, have been described by Manteuffel [18]. This paper presents an adaptive Chebyshev iterative method, in which eigenvalue estimates are computed from modified moments determined during the iterations. The computation of eigenvalue estimates from modified moments requires less computer storage than when eigenvalue estimates are computed by a power method and yields faster convergence for many problems. Received May 13, 1992/Revised version received May 13, 1993     

Projection methods for the solution of one class of singular integrodifferential equations

In this paper we propose a computational scheme of the general projection method for the solution of singular integrodifferential equations in the theory of stream lines and thermal conductivity. We theoretically substantiate this scheme from the standpoint of the theory of approximate methods of functional analysis. We consider particular cases of the general projection method, namely, the method of moments and the collocation method.     

A low-order active fault-tolerant state space self-tuner for the unknown sampled-data nonlinear singular system using OKID and modified ARMAX model-based system identification

In this paper, we present two control schemes for the unknown sampled-data nonlinear singular system. One is an observer-based digital redesign tracker with the state-feedback gain and the feed-forward gain based on off-line observer/Kalman filter identification (OKID) method. The presented control scheme is able to make the unknown sampled-data nonlinear singular system to well track the desired reference signal. The other is an active fault tolerance state-space self-tuner using the OKID method and modified autoregressive moving average with exogenous inputs (ARMAX) model-based system identification for unknown sampled-data nonlinear singular system with input faults. First, one can apply the off-line OKID method to determine the appropriate (low-) order of the unknown system order and good initial parameters of the modified ARMAX model to improve the convergent speed of recursive extended-least-squares (RELS) method. Then, based on modified ARMAX-based system identification, a corresponding adaptive digital control scheme is presented for the unknown sampled-data nonlinear singular system with immeasurable system state. Moreover, in order to overcome the interference of input fault, one can use a fault-tolerant control scheme for unknown sampled-data nonlinear singular system by modifying the conventional self-tuner control (STC). The presented method can effectively cope with partially abrupt and/or gradual system input faults. Finally, some illustrative examples including a real circuit system are given to demonstrate the effectiveness of the presented design methodologies.     

由混合谱数据构造矩阵

The eigenvalues and singular values are two of the most distinguished characteristics in a square matrix. Weyl has proved the majorization between them. Horn has proved its inverse, i.e. there exists a matrix with prescribed eigenvalues and singular values. This paper presents a direct transform method which shows the matrix can be upper triangular with its diagonal elements in any order. There exists a real-valued matrix with prescribed complex-conjugate eigenvalues and singular values. Construction of matrices with mixed data is also considered.     

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…