Browsing by Author "O'Leary, Dianne P."
Now showing 1 - 20 of 32
Results Per Page
Sort Options
Item Adaptive Use of Iterative Methods in Interior Point Methods for Linear Programming(1998-10-15) Wang, Weichung; O'Leary, Dianne P.In this work we devise efficient algorithms for finding the search directions for interior point methods applied to linear programming problems. There are two innovations. The first is the use of updating of preconditioners computed for previous barrier parameters. The second is an adaptive automated procedure for determining whether to use a direct or iterative solver, whether to reinitialize or update the preconditioner, and how many updates to apply. These decisions are based on predictions of the cost of using the different solvers to determine the next search direction, given costs in determining earlier directions. These ideas are tested by applying a modified version of the OB1-R code of Lustig, Marsten, and Shanno to a variety of problems from the NETLIB and other collections. If a direct method is appropriate for the problem, then our procedure chooses it, but when an iterative procedure is helpful, substantial gains in efficiency can be obtained. (Also cross-referenced as UMIACS-TR-95-111)Item Adaptive Use of Iterative Methods in Predictor-Corrector Interior Point Methods for Linear Programming(1999-04-06) Wang, Weichung; O'Leary, Dianne P.In this work we devise efficient algorithms for finding the search directions for interior point methods applied to linear programming problems. There are two innovations. The first is the use of updating of preconditioners computed for previous barrier parameters. The second is an adaptive automated procedure for determining whether to use a direct or iterative solver, whether to reinitialize or update the preconditioner, and how many updates to apply. These decisions are based on predictions of the cost of using the different solvers to determine the next search direction, given costs in determining earlier directions. We summarize earlier results using a modified version of the OB1-R code of Lustig, Marsten, and Shanno, and we present results from a predictor-corrector code PCx modified to use adaptive iteration. If a direct method is appropriate for the problem, then our procedure chooses it, but when an iterative procedure is helpful, substantial gains in efficiency can be obtained. (Also cross-referenced as UMIACS-TR-99-21)Item BFGS with Update Skipping and Varying Memory(1998-10-15) Gibson, Tamara; O'Leary, Dianne P.; Nazareth, LarryWe give conditions under which limited-memory quasi-Newton methods with exact line searches will terminate in $n$ steps when minimizing $n$-dimensional quadratic functions. We show that although all Broyden family methods terminate in $n$ steps in their full-memory versions, only BFGS does so with limited-memory. Additionally, we show that full-memory Broyden family methods with exact line searches terminate in at most $n+p$ steps when $p$ matrix updates are skipped. We introduce new limited-memory BFGS variants and test them on nonquadratic minimization problems. (Also cross-referenced as UMIACS-TR-96-49)Item Blind Deconvolution Using A Regularized Structured Total Least Norm Algorithm(2001-11-19) Pruessner, Armin; O'Leary, Dianne P.Rosen, Park and Glick proposed the structured total least norm (STLN) algorithm for solving problems in which both the matrix and the right-hand side contain errors. We extend this algorithm for ill-posed problems by adding regularization and use the resulting algorithm to solve blind deconvolution problems as encountered in image deblurring when both the image and the blurring function have uncertainty. The resulting regularized structured total least norm (RSTLN) algorithm preserves any affine structure of the matrix and minimizes the discrete L_p-norm error, where p=1,2, or infinity. We demonstrate the effectiveness of these algorithms for blind deconvolution.Item Choosing Regularization Parameters in Iterative Methods for Ill-Posed Problems(1998-10-15) Kilmer, Misha E.; O'Leary, Dianne P.Numerical solution of ill-posed problems is often accomplished by discretization (projection onto a finite dimensional subspace) followed by regularization. If the discrete problem has high dimension, though, typically we compute an approximate solution by projection onto an even smaller dimensional space, via iterative methods based on Krylov subspaces. In this work we present efficient algorithms that regularize after this second projection rather than before it. We prove some results on the approximate equivalence of this approach to other forms of regularization and we present numerical examples. (Also cross-referenced as UMIACS-TR-98-48)Item Computation and Uses of the Semidiscrete Matrix Decomposition(1999-04-06) Kolda, Tamara G.; O'Leary, Dianne P.We derive algorithms for computing a semidiscrete approximation to a matrix in the Frobenius and weighted norms. The approximation is formed as a weighted sum of outer products of vectors whose elements are plus or minus $1$ or $0$, so the storage required by the approximation is quite small. We also present a related algorithm for approximation of a tensor. Applications of the algorithms are presented to data compression, filtering, and information retrieval; and software is provided in C and in Matlab. (Also cross-referenced as UMIACS-TR-99-22)Item Conjugate Gradients and Related KMP Algorithms: The Beginnings(1998-10-15) O'Leary, Dianne P.In the late 1940's and early 1950's, newly available computing machines generated intense interest in solving ``large'' systems of linear equations. Among the algorithms developed were several related methods, all of which generated bases for Krylov subspaces and used the bases to minimize or orthogonally project a measure of error. These methods include the conjugate gradient algorithm and the Lanczos algorithm. We refer to these algorithms as the KMP family and discuss its origins, emphasizing research themes that continue to have central importance. (Also cross-referenced as UMIACS-TR-95-107)Item Displaying Confidence Images(2000-07-20) Nagy, James G.; O'Leary, Dianne P.Algorithms for computing images result in an estimate of an image. The image may result from deblurring a measured image, from deconvolving a set of measurements, or from computing an image by modeling physical processes such as the weather. These computations provide an estimated value for each pixel in the image. What is lacking, however, is an estimate of the statistical confidence that we can have in those pixel values or in the features they form. In this work we discuss novel ways to display confidence information, using an algorithm called {\sf Twinkle}, in order to give the viewer valuable visual insight into uncertainties. The technique is useful whether the confidence information is in the form of a confidence interval or a distribution of possible values. We demonstrate how to display confidence information in a variety of applications: weather forecasts, intensity of a star, and rating a potential tumor in a diagnostic image. (Also cross-referenced as UMIACS-TR-2000-51)Item Efficient Iterative Algorithms for the Stochastic Finite Element Method with Application to Acoustic Scattering(2002-12-19) Elman, Howard; Ernst, Oliver G.; O'Leary, Dianne P.; Stewart, MichaelIn this study, we describe the algebraic computations required to implement the stochastic finite element method for solving problems in which uncertainty is restricted to right hand side data coming from forcing functions or boundary conditions. We show that the solution can be represented in a compact outer product form which leads to efficiencies in both work and storage, and we demonstrate that block iterative methods for algebraic systems with multiple right hand sides can be used to advantage to compute this solution. We also show how to generate a variety of statistical quantities from the computed solution. Finally, we examine the behavior of these statistical quantities in one setting derived from a model of acoustic scattering. UMIACS-TR-2002-102Item Efficient Iterative Solution of the Three-Dimensional Helmholtz Equation(1998-10-15) Elman, Howard C.; O'Leary, Dianne P.We examine preconditioners for the discrete indefinite Helmholtz equation on a three-dimensional box-shaped domain with Sommerfeld-like boundary conditions. The preconditioners are of two types. The first is derived by discretization of a related continuous operator that differs from the original only in its boundary conditions. The second is derived by a block Toeplitz approximation to the discretized problem. The resulting preconditioning matrices allow the use of fast transform methods and differ from the discrete Helmholtz operator by an operator of low rank. We present experimental results demonstrating that when these methods are combined with Krylov subspace iteration, convergence rates depend only mildly on both the wave number and discretization mesh size. In addition, the methods display high efficiencies in an implementation on an IBM SP-2 parallel computer. (Also cross-referenced as UMIACS-TR-97-63)Item Eigenanalysis of Some Preconditioned Helmholtz Problems(1998-10-15) Elman, Howard C.; O'Leary, Dianne P.In this work we calculate the eigenvalues obtained by preconditioning the discrete Helmholtz operator with Sommerfeld-like boundary conditions on a rectilinear domain, by a related operator with boundary conditions that permit the use of fast solvers. The main innovation is that the eigenvalues for two and three-dimensional domains can be calculated exactly by solving a set of one-dimensional eigenvalue problems. This permits analysis of quite large problems. For grids fine enough to resolve the solution for a given wave number, preconditioning using Neumann boundary conditions yields eigenvalues that are uniformly bounded, located in the first quadrant, and outside the unit circle. In contrast, Dirichlet boundary conditions yield eigenvalues that approach zero as the product of wave number with the mesh size is decreased. These eigenvalue properties yield the first insight into the behavior of iterative methods such as GMRES applied to these preconditioned problems. (Also cross-referenced as UMIACS-TR-98-22)Item Exploiting Structure of Symmetric or Triangular Matrices on a GPU(2008-01) Jung, Jin Hyuk; O'Leary, Dianne P.Matrix computations are expensive, and GPUs have the potential to deliver results at reduced cost by exploiting parallel computation. We focus on dense matrices of the form A D2 A^T, where A is an m x n matrix (m less than or equal to n) and D is an n x n diagonal matrix. Many important numerical problems require solving linear systems of equations involving matrices of this form. These problems include normal equations approaches to solving linear least squares and weighted linear least squares problems, and interior point algorithms for linear and nonlinear programming problems. We develop in this work efficient GPU algorithms for forming and factoring A D2 A^T by exploiting the triangular rastorization capabilities of the GPU.Item Fast Iterative Image Restoration with a Spatially-Varying PSF(1998-10-15) Nagy, James G.; O'Leary, Dianne P.We describe how to efficiently apply a spatially-variant blurring operator using linear interpolation of measured point spread functions. Numerical experiments illustrate that substantially better resolution can be obtained at very little additional cost compared to piecewise constant interpolation. (Also cross-referenced as UMIACS-TR-97-53)Item Image Restoration through Subimages and Confidence Images(2000-07-20) Nagy, James G.; O'Leary, Dianne P.Some very effective but expensive image reconstruction algorithms cannot be applied to large images because of their cost. In this work, we first show how to apply such algorithms to subimages, giving improved reconstruction of regions of interest. Our second contribution is to construct confidence intervals for pixel values, by generalizing a theorem of O'Leary and Rust to allow both upper and lower bounds on variables. All current algorithms for image deblurring or deconvolution output an image. This provides an estimated value for each pixel in the image. What is lacking is an estimate of the statistical confidence that we can have in those pixel values or in the features they form in the image. There are two obstacles in determining confidence intervals for pixel values: first, the process is computationally quite intensive, and second, there has been no proposal for providing the results in a visually useful way. In this work we overcome the first of those limitations and use a recently developed algorithm called {\sf Twinkle} to overcome the second. We demonstrate the usefulness of these techniques on astronomical and motion-blurred images. (Also cross-referenced as UMIACS-TR-2000-52)Item Large Latent Semantic Indexing via a Semi-Discrete Matrix Decomposition(1998-10-15) Kolda, Tamara G.; O'Leary, Dianne P.With the electronic storage of documents comes the possibility of building search engines that can automatically choose documents relevant to a given set of topics. In information retrieval, we wish to match queries with relevant documents. Documents can be represented by the terms that appear within them, but literal matching of terms does not necessarily retrieve all relevant documents. There are a number of information retrieval systems based on inexact matches. Latent Semantic Indexing represents documents by approximations and tends to cluster documents on similar topics even if their term profiles are somewhat different. This approximate representation is usually accomplished using a low-rank singular value decomposition (SVD) approximation. In this paper, we use an alternate decomposition, the semi-discrete decomposition (SDD). For equal query times, the SDD does as well as the SVD and uses less than one-tenth the storage for the MEDLINE test set. (Also cross-referenced as UMIACS-TR-96-83)Item Modified Cholesky Algorithms: A Catalog with New Approaches(2006-08-08) Fang, Haw-ren; O'Leary, Dianne P.Given an $n \times n$ symmetric possibly indefinite matrix $A$, a modified Cholesky algorithm computes a factorization of the positive definite matrix $A+E$, where $E$ is a correction matrix. Since the factorization is often used to compute a Newton-like downhill search direction for an optimization problem, the goals are to compute the modification without much additional cost and to keep $A+E$ well-conditioned and close to $A$. Gill, Murray and Wright introduced a stable algorithm, with a bound of $\|E\|_2=O(n2)$. An algorithm of Schnabel and Eskow further guarantees $\|E\|_2=O(n)$. We present variants that also ensure $\|E\|_2=O(n)$. Mor\'{e} and Sorensen and Cheng and Higham used the block $LBL^T$ factorization with blocks of order $1$ or $2$. Algorithms in this class have a worst-case cost $O(n3)$ higher than the standard Cholesky factorization, We present a new approach using an $LTL^T$ factorization, with $T$ tridiagonal, that guarantees a modification cost of at most $O(n2)$.Item A Multigrid Method Enhanced by Krylov Subspace Iteration for Discrete Helmholtz Equations(1999-08-27) Elman, Howard C.; Ernst, Oliver G.; O'Leary, Dianne P.Standard multigrid algorithms have proven ineffective for the solution of discretizations of Helmholtz equations. In this work we modify the standard algorithm by adding GMRES iterations at coarse levels and as an outer iteration. We demonstrate the algorithm's effectiveness through theoretical analysis of a model problem and experimental results. In particular, we show that the combined use of GMRES as a smoother and outer iteration produces an algorithm whose performance depends relatively mildly on wave number and is robust for normalized wave numbers as large as two hundred. For fixed wave numbers, it displays grid-independent convergence rates and has costs proportional to number of unknowns. Also cross-referenced as UMIACS-TR-99-36Item Near-Optimal Parameters for Tikhonov and Other Regularization Methods(1999-04-06) O'Leary, Dianne P.Choosing the regularization parameter for an ill-posed problem is an art based on good heuristics and prior knowledge of the noise in the observations. In this work we propose choosing the parameter, without a priori information, by approximately minimizing the distance between the true solution to the discrete problem and the family of regularized solutions. We demonstrate the usefulness of this approach for Tikhonov regularization and for an alternate family of solutions. Further, we prove convergence of the regularization parameter to zero as the standard deviation of the noise goes to zero. We also prove that the alternate family produces solutions closer to the true solution than the Tikhonov family when the noise is small enough. Also cross-referenced as UMIACS-TR-99-17Item Overcomimg Instability in Computing the Fundamental Matrix for a Markov Chain(1998-10-15) Heyman, Daniel P.; O'Leary, Dianne P.We present an algorithm for solving linear systems involving the probability or rate matrix for a Markov chain. It is based on a UL factorization but works only with a submatrix of the factor U. We demonstrate its utility on Erlang-B models as well as more complicated models of a telephone multiplexing system. (Also cross-referenced as UMIACS-TR-96-24)Item A Parallel Inexact Newton Method Using a Krylov Multisplitting Algorithm(1998-10-15) Huang, Chiou-Ming; O'Leary, Dianne P.Abstract. We present a paraUel variant of the inexact Newton algorithm that uses the Krylov multisplitting algorithm (KMS) to compute the approxrmate Newton direction. The algorithm can be used for solving unconstrained optimization problems or systems of nonlinear equations. The KMS algorithm is a more efficient paraUel implementation of Krylov subspace methods (GMRES, Arnoldi, etc.) with multisplitting preconditioners. The work of the KMS algorithm is divided into the multisplitting tasks and a direction forrning task. There is a great deal of paraUelism within each task and the number of synchronization points between the tasks is greatly reduced. We study the local and global convergence properties of the algorithm and present results of numerical examples on a sequential computer. (Also cross-referenced as UMIACS-TR-93-71)