A linear system solver based on a modified Krylov subspace method for breakdown recovery

Despite its usefulness in solving eigenvalue problems and linear systems of equations, the nonsymmetric Lanczos method is known to suffer from a potential breakdown problem. Previous and recent approaches for handling the Lanczos exact and near-breakdowns include, for example, the look-ahead schemes by Parlett-Taylor-Liu [23], Freund-Gutknecht-Nachtigal [9], and Brezinski-Redivo Zaglia-Sadok [4]; the combined look-ahead and restart scheme by Joubert [18]; and the low-rank modified Lanczos scheme by Huckle [17]. In this paper, we present yet another scheme based on a modified Krylov subspace approach for the solution of nonsymmetric linear systems. When a breakdown occurs, our approach seeks a modified dual Krylov subspace, which is the sum of the original subspace and a new Krylov subspaceK _m (w _j ,A ^T ) wherew _j is a newstart vector (this approach has been studied by Ye [26] for eigenvalue computations). Based on this strategy, we have developed a practical algorithm for linear systems called the MLAN/QM algorithm, which also incorporates the residual quasi-minimization as proposed in [12]. We present a few convergence bounds for the method as well as numerical results to show its effectiveness.Research supported by Natural Sciences and Engineering Research Council of Canada.     

An implicit shift bidiagonalization algorithm for ill-posed systems

Iterative methods based on Lanczos bidiagonalization with full reorthogonalization (LBDR) are considered for solving large-scale discrete ill-posed linear least-squares problems of the form min _x Ax–b₂. Methods for regularization in the Krylov subspaces are discussed which use generalized cross validation (GCV) for determining the regularization parameter. These methods have the advantage that no a priori information about the noise level is required. To improve convergence of the Lanczos process we apply a variant of the implicitly restarted Lanczos algorithm by Sorensen using zero shifts. Although this restarted method simply corresponds to using LBDR with a starting vector (AA ^T) ^p b, it is shown that carrying out the process implicitly is essential for numerical stability. An LBDR algorithm is presented which incorporates implicit restarts to ensure that the global minimum of the CGV curve corresponds to a minimum on the curve for the truncated SVD solution. Numerical results are given comparing the performance of this algorithm with non-restarted LBDR.This work was partially supported by DARPA under grant 60NANB2D1272 and by the National Science Foundation under grant CCR-9209349.     

Error analysis of symplectic Lanczos method for Hamiltonian eigenvalue problem

A rounding error analysis for the symplectic Lanczos method is given to solve the large-scale sparse Hamiltonian eigenvalue problem. If no breakdown occurs in the method, then it can be shown that the Hamiltonian structure preserving requirement does not destroy the essential feature of the nonsymmetric Lanczos algorithm. The relationship between the loss of J-orthogonality among the symplectic Lanczos vectors and the convergence of the Ritz values in the symmetric Lanczos algorithm is discussed. It is demonstrated that under certain assumptions the computed J-orthogonal Lanczos vectors lose the J-orthogonality when some Ritz values begin to converge. Our analysis closely follows the recent works of Bai and Fabbender. Selected from Journal of Mathematical Research and Exposition, 2004, 24(1): 91–106     

Estimation of uTƒ(A)v for large‐scale unsymmetric matrices

Fast algorithms, based on the unsymmetric look‐ahead Lanczos and the Arnoldi process, are developed for the estimation of the functional Φ(?)= u ^T?(A) v for fixed u , v and A, where A∈??^n×n is a large‐scale unsymmetric matrix. Numerical results are presented which validate the comparable accuracy of both approaches. Although the Arnoldi process reaches convergence more quickly in some cases, it has greater memory requirements, and may not be suitable for especially large applications. Copyright © 2003 John Wiley & Sons, Ltd.     

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.     

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.     

Lanczos,Householder transformations,and implicit deflation for fast and reliable dominant singular subspace computation

Many applications, such as subspace‐based models in information retrieval and signal processing, require the computation of singular subspaces associated with the k dominant, or largest, singular values of an m×n data matrix A, where k?min(m,n). Frequently, A is sparse or structured, which usually means matrix–vector multiplications involving A and its transpose can be done with much less than ??(mn) flops, and A and its transpose can be stored with much less than ??(mn) storage locations. Many Lanczos‐based algorithms have been proposed through the years because the underlying Lanczos method only accesses A and its transpose through matrix–vector multiplications. We implement a new algorithm, called KSVD, in the Matlab environment for computing approximations to the singular subspaces associated with the k dominant singular values of a real or complex matrix A. KSVD is based upon the Lanczos tridiagonalization method, the WY representation for storing products of Householder transformations, implicit deflation, and the QR factorization. Our Matlab simulations suggest it is a fast and reliable strategy for handling troublesome singular‐value spectra. Copyright © 2001 John Wiley & Sons, Ltd.     

Matrices, moments, and rational quadrature

Many problems in science and engineering require the evaluation of functionals of the form F_u(A)=u^Tf(A)u, where A is a large symmetric matrix, u a vector, and f a nonlinear function. A popular and fairly inexpensive approach to determining upper and lower bounds for such functionals is based on first carrying out a few steps of the Lanczos procedure applied to A with initial vector u, and then evaluating pairs of Gauss and Gauss-Radau quadrature rules associated with the tridiagonal matrix determined by the Lanczos procedure. The present paper extends this approach to allow the use of rational Gauss quadrature rules.     

基于Lanczos双A-正交的一种修正的QMR算法

本文研究了基于Lanczos双正交过程的拟极小残量法(QMR).将QMR算法中的Lanczos双正交过程用Lanczos双A-正交过程代替,利用该算法得到的近似解与最后一个基向量的线性组合来作为新的近似解,使新近似解的残差范数满足一个一维极小化问题,从而得到一种基于Lanczos双A-正交的修正的QMR算法.数值试验表明,对于某些大型线性稀疏方程组,新算法比QMR算法收敛快得多.     

GPBi‐CGstab(L): A Lanczos‐type product method unifying Bi‐CGstab(L) and GPBi‐CG

Lanczos‐type product methods (LTPMs), in which the residuals are defined by the product of stabilizing polynomials and the Bi‐CG residuals, are effective iterative solvers for large sparse nonsymmetric linear systems. Bi‐CGstab(L) and GPBi‐CG are popular LTPMs and can be viewed as two different generalizations of other typical methods, such as CGS, Bi‐CGSTAB, and Bi‐CGStab2. Bi‐CGstab(L) uses stabilizing polynomials of degree L, while GPBi‐CG uses polynomials given by a three‐term recurrence (or equivalently, a coupled two‐term recurrence) modeled after the Lanczos residual polynomials. Therefore, Bi‐CGstab(L) and GPBi‐CG have different aspects of generalization as a framework of LTPMs. In the present paper, we propose novel stabilizing polynomials, which combine the above two types of polynomials. The resulting method is referred to as GPBi‐CGstab(L). Numerical experiments demonstrate that our presented method is more effective than conventional LTPMs.     

Estimating a largest eigenvector by Lanczos and polynomial algorithms with a random start

We study Lanczos and polynomial algorithms with random start for estimating an eigenvector corresponding to the largest eigenvalue of an n × n large symmetric positive definite matrix. We analyze the two error criteria: the randomized error and the randomized residual error. For the randomized error, we prove that it is not possible to get distribution-free bounds, i.e., the bounds must depend on the distribution of eigenvalues of the matrix. We supply such bounds and show that they depend on the ratio of the two largest eigenvalues. For the randomized residual error, distribution-free bounds exist and are provided in the paper. We also provide asymptotic bounds, as well as bounds depending on the ratio of the two largest eigenvalues. The bounds for the Lanczos algorithm may be helpful in a practical implementation and termination of this algorithm. © 1998 John Wiley & Sons, Ltd.     

The Lanczos phenomenon—An interpretation based upon conjugate gradient optimization

The equivalence in exact arithmetic of the Lanczos tridiagonalization procedure and the conjugate gradient optimization procedure for solving Ax = b, where A is a real symmetric, positive definite matrix, is well known. We demonstrate that a relaxed equivalence is valid in the presence of errors. Specifically we demonstrate that local ε-orthonormality of the Lanczos vectors guarantees local ε-A-conjugacy of the direction vectors in the associated conjugate gradient procedure. Moreover we demonstrate that all the conjugate gradient relationships are satisfied approximately. Therefore, any statements valid for the conjugate gradient optimization procedure, which we show converges under very weak conditions, apply directly to the Lanczos procedure. We then use this equivalence to obtain an explanation of the Lanczos phenomenon: the empirically observed “convergence” of Lanczos eigenvalue procedures despite total loss of the global orthogonality of the Lanczos vectors.     

A computable error bound for matrix functionals

Many problems in applied mathematics require the evaluation of matrix functionals of the form F(A):=u^Tf(A)u, where A is a large symmetric matrix and u is a vector. Golub and collaborators have described how approximations of such functionals can be computed inexpensively by using the Lanczos algorithm. The present note shows that error bounds for these approximations can be computed essentially for free when bounds for derivatives of f on an interval containing the spectrum of A are available.     

The use of a refined error bound when updating eigenvalues of tridiagonals

The Lanczos algorithm is used to compute some eigenvalues of a given symmetric matrix of large order. At each step of the Lanczos algorithm it is valuable to know which eigenvalues of the associated tridiagonal matrix have stabilized at eigenvalues of the given symmetric matrix. We present a robust algorithm which is fast (20j to 40j operations at the jth Lanczos step), uses about 30 words of extra storage, and has a fairly short program (approxiamately 200 executable statements)     

A posteriori error estimate for computing tr(f(A)) by using the Lanczos method

An outstanding problem when computing a function of a matrix, f(A), by using a Krylov method is to accurately estimate errors when convergence is slow. Apart from the case of the exponential function that has been extensively studied in the past, there are no well‐established solutions to the problem. Often, the quantity of interest in applications is not the matrix f(A) itself but rather the matrix–vector products or bilinear forms. When the computation related to f(A) is a building block of a larger problem (e.g., approximately computing its trace), a consequence of the lack of reliable error estimates is that the accuracy of the computed result is unknown. In this paper, we consider the problem of computing tr(f(A)) for a symmetric positive‐definite matrix A by using the Lanczos method and make two contributions: (a) an error estimate for the bilinear form associated with f(A) and (b) an error estimate for the trace of f(A). We demonstrate the practical usefulness of these estimates for large matrices and, in particular, show that the trace error estimate is indicative of the number of accurate digits. As an application, we compute the log determinant of a covariance matrix in Gaussian process analysis and underline the importance of error tolerance as a stopping criterion as a means of bounding the number of Lanczos steps to achieve a desired accuracy.     

A semidefinite framework for trust region subproblems with applications to large scale minimization

Primal-dual pairs of semidefinite programs provide a general framework for the theory and algorithms for the trust region subproblem (TRS). This latter problem consists in minimizing a general quadratic function subject to a convex quadratic constraint and, therefore, it is a generalization of the minimum eigenvalue problem. The importance of (TRS) is due to the fact that it provides the step in trust region minimization algorithms. The semidefinite framework is studied as an interesting instance of semidefinite programming as well as a tool for viewing known algorithms and deriving new algorithms for (TRS). In particular, a dual simplex type method is studied that solves (TRS) as a parametric eigenvalue problem. This method uses the Lanczos algorithm for the smallest eigenvalue as a black box. Therefore, the essential cost of the algorithm is the matrix-vector multiplication and, thus, sparsity can be exploited. A primal simplex type method provides steps for the so-called hard case. Extensive numerical tests for large sparse problems are discussed. These tests show that the cost of the algorithm is 1 +α(n) times the cost of finding a minimum eigenvalue using the Lanczos algorithm, where 0<α(n)<1 is a fraction which decreases as the dimension increases. Research supported by the National Science and Engineering Research Council Canada.     

Linear maps between C*-algebras that are *-homomorphisms at a fixed point

Let A and B be C*-algebras. A linear map T : A → B is said to be a *-homomorphism at an element z ∈ A if ab* = z in A implies T (ab*) = T (a)T (b)* = T (z), and c*d = z in A gives T (c*d) = T (c)*T (d) = T (z). Assuming that A is unital, we prove that every linear map T : A → B which is a *-homomorphism at the unit of A is a Jordan *-homomorphism. If A is simple and infinite, then we establish that a linear map T : A → B is a *-homomorphism if and only if T is a *-homomorphism at the unit of A. For a general unital C*-algebra A and a linear map T : A → B, we prove that T is a *-homomorphism if, and only if, T is a *-homomorphism at 0 and at 1. Actually if p is a non-zero projection in A, and T is a ^?-homomorphism at p and at 1 ? p, then we prove that T is a Jordan *-homomorphism. We also study bounded linear maps that are *-homomorphisms at a unitary element in A.     

On the self-inverse operators

Let T be an operator on a Hilbert space . The problem of computing of the norm of T, norm of selfcommutators of T, and the numerical radius of T are discussed in many papers and a number of textbooks. In this paper we determine the relationships between these values for self inverse operators and explain how we can determine any three of these (‖T‖, ‖[T*,T]‖, ‖{T*,T}‖, and the numerical radius of T) by knowing any one of them. Also, we find the spectrum of T*T,[T*,T] and {T*,T} in the case that T is self inverse and the spectrum of T*T is an interval. Finally, by giving some examples on automorphic composition operators, we show that these results make it possible to replace lengthy computation with quick ones. Research partially supported by the Shiraz university Research Council Grant No. 86-GR-SC-32.     

On the Weyl Spectrum: Spectral Mapping Theorem and Weyl's Theorem

It is shown that ifTis a dominant operator or an analytic quasi-hyponormal operator on a complex Hilbert space and iffis a function analytic on a neighborhood of σ(T), then σ_w(f(T)) = f(σ_w(T)), where σ(T) and σ_w(T) stand respectively for the spectrum and the Weyl spectrum ofT; moreover, Weyl's theorem holds forf(T) + Fif “dominant” is replaced by “M-hyponormal,” whereFis any finite rank operator commuting withT. These generalize earlier results for hyponormal operators. It is also shown that there exist an operatorTand a finite rank operatorFcommuting withTsuch that Weyl's theorem holds forTbut not forT + F. This answers negatively a problem raised by K. K. Oberai (Illinois J. Math.21, 1977, 84–90). However, ifTis required to be isoloid, then the statement that Weyl's theorem holds forTwill imply it holds forT + F.     

On Operators Satisfying T＊｜T2｜T≥ T＊｜T＊｜2T

Let T be a bounded linear operator on a complex Hilbert space H. In this paper we introduce a new class denoted by l-＊-A, of operators satisfying T＊｜T2｜T≥ T＊｜T＊｜2T, and we prove the basic properties of these operators. Using these results, we also prove that if T or T＊ ∈l-＊-A, then w（f（T）） = f（w（T））, σea（f（T）） = f（σea（T）） for every f C H（σ（T））, where g（σ（T）） denotes the set of all analytic functions on an open neighborhood of σ（T）.