Technical Reports from UMIACS
Permanent URI for this collectionhttp://hdl.handle.net/1903/7
Browse
21 results
Search Results
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 Symbiosis between Linear Algebra and Optimization(1999-05-28) O'Leary, Dianne P.The efficiency and effectiveness of most optimization algorithms hinges on the numerical linear algebra algorithms that they utilize. Effective linear algebra is crucial to their success, and because of this, optimization applications have motivated fundamental advances in numerical linear algebra. This essay will highlight contributions of numerical linear algebra to optimization, as well as some optimization problems encountered within linear algebra that contribute to a symbiotic relationship. Also cross-referenced as UMIACS-TR-99-30Item 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 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 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 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 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 TIKHONOV REGULARIZATION AND TOTAL LEAST SQUARES(1998-10-15) Golub, Gene H.; Hansen, Per Christian; O'Leary, Dianne P.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. (Also cross-referenced as UMIACS-TR-97-65)Item 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 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)
- «
- 1 (current)
- 2
- 3
- »