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]

The optimal parameter of the Hermitian/skew-Hermitian splitting (HSS) iteration method for a real two-by-two linear system is obtained. The result is used to determine the optimal parameters for linear systems associated with certain two-by-two block matrices and to estimate the optimal parameters of the HSS iteration method for linear systems with n-by-n real coefficient matrices. Numerical examples are given to illustrate the results. [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]

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]

We consider 2 × 2 block indefinite linear systems whose (2, 2) block is zero. Such systems arise in many applications. We discuss two techniques that are based on modifying the (1, 1) block in a way that makes the system easier to solve. The main part of the paper focuses on an augmented Lagrangian approach: a technique that modifies the (1,1) block without changing the system size. The choice of the parameter involved, the spectrum of the linear system, and its condition number are discussed, and some analytical observations are provided. A technique of deflating the (1,1) block is then introduced. Finally, numerical experiments that validate the analysis are presented. [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.

In this paper, we present an inverse free Krylov subspace method for finding some extreme eigenvalues of the symmetric definite generalized eigenvalue problem Ax = λBx. The basic method takes a form of inner-outer iterations and involves no inversion of B or any shift-and-invert matrix A - λ[sub 0]B. A convergence analysis is presented that leads to a preconditioning scheme for accelerating convergence through some equivalent transformations of the eigenvalue problem. Numerical examples are given to illustrate the convergence properties and to demonstrate the competitiveness of the method. [ABSTRACT FROM AUTHOR]

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]

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]

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]

An important variation of preconditioned conjugate gradient algorithms is inexact preconditioner implemented with inner-outer iterations [G. H. Golub and M. L. Overton, Numerical Analysis, Lecture Notes in Math. 912, Springer, Berlin, New York, 1982], where the preconditioner is solved by an inner iteration to a prescribed precision. In this paper, we formulate an inexact preconditioned conjugate gradient algorithm for a symmetric positive definite system and analyze its convergence property. We establish a linear convergence result using a local relation of residual norms. We also analyze the algorithm using a global equation and show that the algorithm may have the superlinear convergence property when the inner iteration is solved to high accuracy. The analysis is in agreement with observed numerical behavior of the algorithm. In particular, it suggests a heuristic choice of the stopping threshold for the inner iteration. Numerical examples are given to show the effectiveness of this choice and to compare the convergence bound. [ABSTRACT FROM AUTHOR]

We derive a stable technique, based upon matrix pencils, for the reconstruction of (or approximation by) polygonal shapes from moments. We point out that this problem can be considered the dual of 2 — D numerical quadrature over polygonal domains. An analysis of the sensitivity of the problem is presented along with some numerical examples illustrating the relevant points. Finally, an application to the problem of gravimetry is explored where the shape of a gravitationally anomalous region is to be recovered from measurements of its exterior gravitational field. [ABSTRACT FROM AUTHOR]

We present a new method for solving total variation (TV) minimization problems in image restoration. The main idea is to remove some of the singularity caused by the nondifferentiability of the quantity ¦∇u¦ in the definition of the TV-norm before we apply a linearization technique such as Newton's method. This is accomplished by introducing an additional variable for the flux quantity appearing in the gradient of the objective function, which can be interpreted as the normal vector to the level sets of the image u. Our method can be viewed as a primal-dual method as proposed by Conn and Overton [A Primal-Dual Interior Point Method for Minimizing a Sum of Euclidean Norms, Preprint, 1994] and Andersen [Ph.D. thesis, Odense University, Denmark, 1995] for the minimization of a sum of Euclidean norms. In addition to possessing local quadratic convergence, experimental results show that the new method seems to be globally convergent.

We analyze the preconditioned Chebyshev iteration in which at each step the linear system involving the preconditioner is solved inexactly by an inner iteration. We allow the tolerance used in the inner iteration to decrease from one outer iteration to the next. When the tolerance converges to zero, the asymptotic convergence rate is the same as for the exact method. Motivated by this result, we seek the sequence of tolerance values that yields the lowest cost to achieve a specified accuracy. We find that among all sequences of slowly varying tolerances, a constant one is optimal. Numerical calculations that verify our results are presented. Asymptotic methods, such as the W.K.B. method for linear recurrence equations, are used with an estimate of the accuracy of the asymptotic result. [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]

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]