Search

A new method is proposed to solve an ellipsoid-constrained integer least squares (EILS) problem arising in communications. In this method, the LLL reduction, which is cast as a QRZ factorization of a matrix, is used to transform the original EILS problem to a reduced EILS problem, and then a search algorithm is proposed to solve the reduced EILS problem. Simulation results indicate the new method can be much more computationally efficient than the existing method. The method is extended to solve a more general EILS problem. [ABSTRACT FROM AUTHOR]

One of the most powerful iterative schemes for solving symmetric, positive definite linear systems is the conjugate gradient algorithm of Hestenes and Stiefel [J. Res. Nat. Bur. Standards, 49 (1952), pp. 409-435], especially when it is combined with preconditioning (cf. [P. Concus, G.H. Golub, and D.P. O'Leary, in Proceedings of the Symposium on Sparse Matrix Computations, Argonne National Laboratory, 1975, Academic, New York, 1976]). In many applications, the solution of a sequence of equations with the same coefficient matrix is required. We propose an approach based on a combination of the conjugate gradient method with Chebyshev filtering polynomials, applied only to a part of the spectrum of the coefficient matrix, as preconditioners that target some specific convergence properties of the conjugate gradient method. We show that our preconditioner puts a large number of eigenvalues near one and do not degrade the distribution of the smallest ones. This procedure enables us to construct a lower dimensional Krylov basis that is very rich with respect to the smallest eigenvalues and associated eigenvectors. A major benefit of our method is that this information can then be exploited in a straightforward way to solve sequences of systems with little extra work. We illustrate the performance of our method through numerical experiments on a set of linear systems. [ABSTRACT FROM AUTHOR]

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]

For the iterative solution of saddle point problems, a nonsymmetric preconditioner is studied which, with respect to the upper-left block of the system matrix, can be seen as a variant of SSOR. An idealized situation where SSOR is taken with respect to the skew-symmetric part plus the diagonal part of the upper-left block is analyzed in detail. Since action of the preconditioner involves solution of a Schur complement system, an inexact form of the preconditioner can be of interest. This results in an inner-outer iterative process. Numerical experiments with solution of linearized Navier-Stokes equations demonstrate the efficiency of the new preconditioner, especially when the upper-left block is far from symmetric. [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]

Examines efficient iterative methods for the large sparse non-Hermitian positive definite systems of linear equations based on the Hermitian and skew-Hermitian splitting of the coefficient matrix. Demonstration that the Hermitian/skew-Hermitian splitting iteration method converges unconditionally to the unique solution of the system of linear equations.

The singular value decomposition (SVD) has been extensively used in engineering and statistical applications. This method was originally discovered by Eckart and Young in [Psychometrika, 1 (1936), pp. 211-218], where they considered the problem of low-rank approximation to a matrix. A natural generalization of the SVD is the problem of low-rank approximation to high order tensors, which we call the multidimensional SVD. In this paper, we investigate certain properties of this decomposition as well as numerical algorithms. [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]

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]