Search

Abstract: Generalized eigenvalue problems play a significant role in many applications. In this paper, continuous methods are presented to compute generalized eigenvalues and their corresponding eigenvectors for two real symmetric matrices. Our study only requires that the right-hand-side matrix is positive semi-definite. The main idea of our continuous methods is to convert the generalized eigenvalue problem into an optimization problem. Then a continuous method which includes both a merit function and an ordinary differential equation (ODE) is introduced for the resulting optimization problem. The strong convergence of the ODE solution is proved for any starting point. Both the generalized eigenvalues and their corresponding eigenvectors can be easily obtained under some mild conditions. Some numerical results are also presented. [Copyright &y& Elsevier]

Abstract: We study theoretical properties of two inexact Hermitian/skew-Hermitian splitting (IHSS) iteration methods for the large sparse non-Hermitian positive definite system of linear equations. In the inner iteration processes, we employ the conjugate gradient (CG) method to solve the linear systems associated with the Hermitian part, and the Lanczos or conjugate gradient for normal equations (CGNE) method to solve the linear systems associated with the skew-Hermitian part, respectively, resulting in IHSS(CG, Lanczos) and IHSS(CG, CGNE) iteration methods, correspondingly. Theoretical analyses show that both IHSS(CG, Lanczos) and IHSS(CG, CGNE) converge unconditionally to the exact solution of the non-Hermitian positive definite linear system. Moreover, their contraction factors and asymptotic convergence rates are dominantly dependent on the spectrum of the Hermitian part, but are less dependent on the spectrum of the skew-Hermitian part, and are independent of the eigenvectors of the matrices involved. Optimal choices of the inner iteration steps in the IHSS(CG, Lanczos) and IHSS(CG, CGNE) iterations are discussed in detail by considering both global convergence speed and overall computation workload, and computational efficiencies of both inexact iterations are analyzed and compared deliberately. [Copyright &y& Elsevier]

The convergence features of a preconditioned algorithm for the convection-diffusion equation based on its diffusion part are considered. Analyses of the distribution of the eigenvalues of the preconditioned matrix in arbitrary dimensions and of the fundamental parameters of convergence are provided, showing the existence of a proper cluster of eigenvalues. The structure of the cluster is not influenced by the discretization. An upper bound on the condition number of the eigenvector matrix under some assumptions is provided as well. The overall cost of the algorithm is O(n), where n is the size of the underlying matrices. [ABSTRACT FROM AUTHOR]

In this paper a generalized eigenvalue problem for nonsquare pencils of the form A - λB with A,B ϵ Cmxn and m > n, which was proposed recently by Boutry, Elad, Golub, and Milanfar [SIAM J. Matrix Anal. Appl., 27 (2006), pp. 582–601], is studied. An algebraic characterization for the distance between the pair (A,B) and the pairs (A0,B0) with the property that for the pair (A0,B0) there exist l distinct eigenpairs of the form (A0-λkB0)v-k = 0, k = 1, … , l, is given, which implies that this distance can be obtained by solving an optimization problem over the compact set {Vl : Vl ϵ Cnxl, VH l VHlVl = I}. Furthermore, the distance between a controllable descriptor system and uncontrollable ones is also considered, an algebraic characterization is obtained, and hence a well-known result on the distance between a controllable linear time-invariant system to uncontrollable ones is extended to the descriptor systems. [ABSTRACT FROM AUTHOR]

We consider a positive definite block preconditioner for solving saddle point linear systems. An approach based on augmenting the (1,1) block while keeping its condition number small is described, and algebraic analysis is performed. Ways of selecting the parameters involved are discussed, and analytical and numerical observations are given. [ABSTRACT FROM AUTHOR]

We consider a generic sequence of matrices (the nonnormal case is of interest) showing a proper cluster at zero in the sense of the singular values. By a direct use of the notion of majorizations, we show that the uniform spectral boundedness is sufficient for the proper clustering at zero of the eigenvalues: if the assumption of boundedness is removed, then we can construct sequences of matrices with a proper singular value clustering and having all the eigenvalues of an arbitrarily big modulus. Applications to the preconditioning theory are discussed. [ABSTRACT FROM AUTHOR]

In this paper we consider the solution of linear systems of saddle point type by preconditioned Krylov subspace methods. A preconditioning strategy based on the symmetric/skew-symmetric splitting of the coefficient matrix is proposed, and some useful properties of the preconditioned matrix are established. The potential of this approach is illustrated by numerical experiments with matrices from various application areas. [ABSTRACT FROM AUTHOR]

A parallel algorithm is proposed for the solution of narrow banded non-symmetric linear systems. The linear system is partitioned into blocks of rows with a small number of unknowns common to multiple blocks. Our technique yields a reduced system defined only on these common unknowns which can then be solved by a direct or iterative method. A projection based extension to this approach is also proposed for computing the reduced system implicitly, which gives rise to an inner–outer iteration method. In addition, the product of a vector with the reduced system matrix can be computed efficiently on a multiprocessor by concurrent projections onto subspaces of block rows. Scalable implementations of the algorithm can be devized for hierarchical parallel architectures by exploiting the two-level parallelism inherent in the method. Our experiments indicate that the proposed algorithm is a robust and competitive alternative to existing methods, particularly for difficult problems with strong indefinite symmetric part. Copyright © 2001 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Preconditioners are often conceived as approximate inverses. For nonsingular indefinite matrices of saddle-point (or KKT) form, we show how preconditioners incorporating an exact Schur complement lead to preconditioned matrices with exactly two or exactly three distinct eigenvalues. Thus approximations of the Schur complement lead to preconditioners which can be very effective even though they are in no sense approximate inverses. [ABSTRACT FROM AUTHOR]

Let A be a symmetric matrix and let f be a smooth function defined on an interval containing the spectrum of A. Generalizing a well-known result of Demko, Moss and Smith on the decay of the inverse we show that when A is banded, the entries of ƒ(A) are bounded in an exponentially decaying manner away from the main diagonal. Bounds obtained by representing the entries of ƒ(A) in terms of Riemann-Stieltjes integrals and by approximating such integrals by Gaussian quadrature rules are also considered. Applications of these bounds to preconditioning are suggested and illustrated by a few numerical examples. [ABSTRACT FROM AUTHOR]

Discretizations of inverse problems lead to systems of linear equations with a highly ill-conditioned coefficient matrix, and in order to compute stable solutions to these systems it is necessary to apply regularization methods. We show how Tikhonov's regularization method, which in its original formulation involves a least squares problem, can be recast in a total least squares formulation suited for problems in which both the coefficient matrix and the right-hand side are known only approximately. We analyze the regularizing properties of this method and demonstrate by a numerical example that, in certain cases with large perturbations, the new method is superior to standard regularization methods. [ABSTRACT FROM AUTHOR]

This paper analyzes rank modification of symmetric positive definite matrices H of the form H - M + P, where H - M denotes a step of reducing H to a lower-rank, symmetric and positive semidefinite matrix and (H - M) + P denotes a step of restoring H - M to a sym- metric positive definite matrix. These steps and their generalizations for rectangular matrices are fully characterized. The well-known BFGS and DFP updates used in Hessian and inverse Hessian approximations provided the motivation for the generalizations and are special cases with H and P having rank one. [ABSTRACT FROM AUTHOR]

The OR algorithm is a basic algorithm for computing the eigenvalues of dense matrices. For efficiency reasons it is prerequisite that the algorithm is applied only after the original matrix has been reduced to a matrix of a particular shape, most notably Hessenberg and tridiagonal, which is preserved during the iterative process. In certain circumstances a reduction to another matrix shape may be advantageous. In this paper, we identify which zero patterns of symmetric matrices are preserved under the OR algorithm. [ABSTRACT FROM AUTHOR]

A variational formulation for the generalized singular value decomposition (GSVD) of a pair of matrices A ∈ Rm×n and B ∈ Rp×n is presented. In particular, a duality theory analogous to that of the SVD provides new understanding of left and right generalized singular vectors. It is shown that the intersection of row spaces of A and B plays a key role in the GSVD duality theory. The main result that characterizes left GSVD vectors involves a generalized singular value deflation process. [ABSTRACT FROM AUTHOR]