724 Matching Results

Search Results

Advanced search parameters have been applied.

Iterative Solution of Linear Programs

Description: By perturbing a linear program to a quadratic program, it is possible to solve the latter in its dual variable space by iterative techniques such as successive over-relaxation (SOR) methods. This provides a solution to the original linear program.
Date: July 1979
Creator: Mangasarian, Olvi L.
Partner: UNT Libraries Government Documents Department

Efficient computation of matched solutions of the KV envelopeequation for periodic focusing lattices

Description: A new iterative method is developed to numerically calculate the periodic, matched beam envelope solution of the coupled Kapchinskij-Vladimirskij (KV) equations describing the transverse evolution of a beam in a periodic, linear focusing lattice of arbitrary complexity. Implementation of the method is straightforward. It is highly convergent and can be applied to all usual parameterizations of the matched envelope solutions. The method is applicable to all classes of linear focusing lattices without skew couplings, and also applies to parameters where the matched beam envelope is strongly unstable. Example applications are presented for periodic solenoidal and quadrupole focusing lattices. Convergence properties are summarized over a wide range of system parameters.
Date: January 3, 2006
Creator: Lund, Steven M.; Chilton, Sven H. & Lee, Edward P.
Partner: UNT Libraries Government Documents Department

Iterative procedure for in-situ EUV optical testing with an incoherent source

Description: We propose an iterative method for in-situ optical testing under partially coherent illumination that relies on the rapid computation of aerial images. In this method a known pattern is imaged with the test optic at several planes through focus. A model is created that iterates through possible aberration maps until the through-focus series of aerial images matches the experimental result. The computation time of calculating the through-focus series is significantly reduced by a-SOCS, an adapted form of the Sum Of Coherent Systems (SOCS) decomposition. In this method, the Hopkins formulation is described by an operator S which maps the space of pupil aberrations to the space of aerial images. This operator is well approximated by a truncated sum of its spectral components.
Date: December 1, 2009
Creator: Miyawaka, Ryan; Naulleau, Patrick & Zakhor, Avideh
Partner: UNT Libraries Government Documents Department

Improving the Accuracy of Computed Eigenvalues and Eigenvectors

Description: This paper describes a computational method for improving the accuracy of a given eigenvalue and its associated eigenvector. The method is analogous to iterative improvement for the solution of linear systems. An iterative algorithm using working precision arithmetic is applied to increase the accuracy of the eigenpair. The only extended precision computation is the residual calculation. The method is related to inverse iteration and to Newton's method applied to the eigenvalue problem.
Date: July 1981
Creator: Dongarra, J. J.; Moler, Cleve B. & Wilkinson, J. H.
Partner: UNT Libraries Government Documents Department

Accurate Iterative Analysis Solution of theKapchinskij-Vladimirskij Equations for the Case of a Matched Beam

Description: The well-known Kapchinskij-Vladimirskij (KV) equations are difficult to solve in general, but the problem is simplified for the matched-beam case with sufficient symmetry. They show that the interdependence of the two KV equations is eliminated, so that only one needs to be solved--a great simplification. They present an iterative method of solution which can potentially yield any desired level of accuracy. The lowest level, the well-known smooth approximation, yields simple, explicit results with good accuracy for weak or moderate focusing fields. The next level improves the accuracy for high fields; they previously showed [Part. Accel. 52, 133 (1996)] how to maintain a simple explicit format for the results. That paper used expansion in a small parameter to obtain results of second-level accuracy. The present paper, using straightforward iteration, obtains equations of first, second, and third levels of accuracy. For a periodic lattice with beam matched to lattice, they use the lattice and beam parameters as input and solve for phase advances and envelope functions. They find excellent agreement with numerical solutions over a wide range of beam emittances and intensities.
Date: January 31, 2007
Creator: Anderson, O.A.
Partner: UNT Libraries Government Documents Department

Perturbation Method for Calculation of Narrow-Band Impedance and Trapped Modes

Description: An iterative method for calculation of the narrow-band impedance is described for a system with a small variation in boundary conditions, so that the variation can be considered as a perturbation.The results are compared with the degeneracy of the spectrum of an unperturbed system.The method also can be applied to transverse impedance calculations.
Date: August 1, 1987
Creator: Heifets, Sam
Partner: UNT Libraries Government Documents Department

Coarse Spaces by Algebraic Multigrid: Multigrid Convergence and Upscaled Error Estimates

Description: We give an overview of a number of algebraic multigrid methods targeting finite element discretization problems. The focus is on the properties of the constructed hierarchy of coarse spaces that guarantee (two-grid) convergence. In particular, a necessary condition known as 'weak approximation property', and a sufficient one, referred to as 'strong approximation property' are discussed. Their role in proving convergence of the TG method (as iterative method) and also on the approximation properties of the AMG coarse spaces if used as discretization tool is pointed out. Some preliminary numerical results illustrating the latter aspect are also reported.
Date: April 30, 2010
Creator: Vassilevski, P S
Partner: UNT Libraries Government Documents Department

Soft Error Vulnerability of Iterative Linear Algebra Methods

Description: Devices are increasingly vulnerable to soft errors as their feature sizes shrink. Previously, soft error rates were significant primarily in space and high-atmospheric computing. Modern architectures now use features so small at sufficiently low voltages that soft errors are becoming important even at terrestrial altitudes. Due to their large number of components, supercomputers are particularly susceptible to soft errors. Since many large scale parallel scientific applications use iterative linear algebra methods, the soft error vulnerability of these methods constitutes a large fraction of the applications overall vulnerability. Many users consider these methods invulnerable to most soft errors since they converge from an imprecise solution to a precise one. However, we show in this paper that iterative methods are vulnerable to soft errors, exhibiting both silent data corruptions and poor ability to detect errors. Further, we evaluate a variety of soft error detection and tolerance techniques, including checkpointing, linear matrix encodings, and residual tracking techniques.
Date: January 19, 2008
Creator: Bronevetsky, G & de Supinski, B
Partner: UNT Libraries Government Documents Department

Krylov subspace iterations for the calculation of K-Eigenvalues with sn transport codes

Description: We apply the Implicitly Restarted Arnoldi Method (IRAM), a Krylov subspace iterative method, to the calculation of k-eigenvalues for criticality problems. We show that the method can be implemented with only modest changes to existing power iteration schemes in an SN transport code. Numerical results on three dimensional unstructured tetrahedral meshes are shown. Although we only compare the IRAM to unaccelerated power iteration, the results indicate that the IRAM is a potentially efficient and powerful technique, especially for problems with dominance ratios approaching unity. Key Words: criticality eigenvalues, Implicitly Restarted Arnoldi Method (IRAM), deterministic transport methods
Date: January 1, 2002
Creator: Warsa, J. S. (James S.); Wareing, T. A. (Todd A.); Morel, J. E.; McGhee, J. M. (John M.) & Lehoucq, R. B. (Richard B.)
Partner: UNT Libraries Government Documents Department

Efficient computation of matched solutions of the KV envelope equations for periodic focusing lattices.

Description: A new iterative method is developed to numerically calculate the periodic, matched beam envelope solution of the coupled Kapchinskij-Vladimirskij (KV) equations describing the transverse evolution of a beam in a periodic, linear focusing lattice of arbitrary complexity. Implementation of the method is straightforward. It is highly convergent and can be applied to all usual parameterizations of the matched envelope solutions. The method is applicable to all classes of linear focusing lattices without skew couplings, and also applies to parameters where the matched beam envelope is strongly unstable. Example applications are presented for periodic solenoidal and quadrupole focusing lattices. Convergence properties are summarized over a wide range of system parameters.
Date: January 17, 2006
Creator: Lund, S M; Chilton, S H & Lee, E P
Partner: UNT Libraries Government Documents Department

Examples and Applications of Infinite Iterated Function Systems

Description: The aim of this work is the study of infinite conformal iterated function systems. More specifically, we investigate some properties of a limit set J associated to such system, its Hausdorff and packing measure and Hausdorff dimension. We provide necessary and sufficient conditions for such systems to be bi-Lipschitz equivalent. We use the concept of scaling functions to obtain some result about 1-dimensional systems. We discuss particular examples of infinite iterated function systems derived from complex continued fraction expansions with restricted entries. Each system is obtained from an infinite number of contractions. We show that under certain conditions the limit sets of such systems possess zero Hausdorff measure and positive finite packing measure. We include an algorithm for an approximation of the Hausdorff dimension of limit sets. One numerical result is presented. In this thesis we also explore the concept of positively recurrent function. We use iterated function systems to construct a natural, wide class of such functions that have strong ergodic properties.
Date: August 2000
Creator: Hanus, Pawel Grzegorz
Partner: UNT Libraries

Users Manual for KSP Data-Structure-Neutral Codes Implementing Krylov Space Methods

Description: The combination of a Krylov space method and a pre-conditioner is at the heart of most modern numerical codes for the iterative solution of linear systems. This document contains both a users manual and a description of the implementation for the Krylov space methods package KSP included as part of the Portable, Extensible Tools for Scientific computation package (PETSc). PETSc is a large suite of data-structure-neutral libraries for the solution of large-scale problems in scientific computation, in particular on massively parallel computers. The methods in KSP are conjugate gradient method, GMRES, BiCG-Stab, two versions of transpose-free QMR, and others. All of the methods are coded using a common, data-structure-neutral framework and are compatible with the sequential, parallel, and out-of-core solution of linear systems. The codes make no assumptions about the representation of the linear operator; implicitly defined operators (say, calculated using differencing) are fully supported. In addition, unlike all other iterative packages we are aware of, the vector operations are also data-structure neutral. Once certain vector primitives are provided, the same KSP software runs unchanged using any vector storage format. It is not restricted to a few common vector representations. The codes described are actual working codes that run on a large variety of machines including the IBM SP1, Intel DELTA, workstations, networks of workstations, the TMC CM-5, and the CRAY C90. New Krylov space methods may be easily added to the package and used immediately with any application code that has been written using KSP; no changes to the application code are needed.
Date: August 1994
Creator: Gropp, William & Smith, Barry
Partner: UNT Libraries Government Documents Department

Newton's Method with a Model Trust-Region Modification

Description: A modified Newton method for unconstrained minimization is presented and analyzed. The modification is based upon the model trust region approach. This report contains a thorough analysis of the locally constrained quadratic minimizations that arise as sub-problems in the modified Newton iteration. Several promising alternatives are presented for solving these sub-problems in ways that overcome certain theoretical difficulties exposed by this analysis. Very strong convergence results are presented concerning the minimization algorithm. In particular, the explicit use of second-order information is justified by demonstrating that the iterates converge to a point that satisfies the second-order necessary conditions for minimization. With the exception of very pathological cases this convergence occurs whenever the algorithm is applied to problems with continuous second partial derivatives.
Date: September 1980
Creator: Sorensen, D. C.
Partner: UNT Libraries Government Documents Department

Newton's Method

Description: Newton's method plays a central role in the development of numerical techniques for optimization. In fact, most of the current practical methods for optimization can be viewed as variations on Newton's method. It is therefore important to understand Newton's method as an algorithm in its own right and as a key introduction to the most recent ideas in this area. One of the aims of this expository paper is to present and analyze two main approaches to Newton's method for unconstrained minimization: the line search approach and the trust region approach. The other aim is to present some of the recent developments in the optimization field which are related to Newton's method. In particular, we explore several variations on Newton's method which are appropriate for large scale problems, and we also show how quasi-Newton methods can be derived quite naturally from Newton's method.
Date: February 1982
Creator: MoreĢ, Jorge J. & Sorensen, D. C.
Partner: UNT Libraries Government Documents Department

Simplified Linear Equation Solvers : Users Manual

Description: The solution of large sparse systems of linear equations is at the heart of many algorithms in scientific computing. The SLES package is a set of easy-to-use yet powerful and extensible routines for solving large sparse linear systems. The design of the package allows new techniques to be used in existing applications without any source code changes in the applications.
Date: February 1993
Creator: Gropp, William & Smith, Barry
Partner: UNT Libraries Government Documents Department

Verification of the MCNP (TM) Perturbation Correction Feature for Cross-Section Dependent Tallies

Description: The Monte Carlo N-Particle Transport Code MCNP version 4B perturbation capability has been extended to cross-section dependent tallies and to the track-length estimate of Iqff in criticality problems. We present the complete theory of the MCNP perturbation capability including the correction to MCNP4B which enables cross-section dependent perturbation tallies. We also present the MCNP interface as an upgrade to the MCNP4B manual. Finally, we present test results demonstrating the validity of the perturbation capability in MCNP, particularly cross-section dependent problems.
Date: October 1, 1998
Creator: Hess, A. K.; McKinney, G. W.; Hendricks, J. S. & Carter, L. L.
Partner: UNT Libraries Government Documents Department

Conditioning analysis of incomplete Cholesky factorizations with orthogonal dropping

Description: The analysis of preconditioners based on incomplete Cholesky factorization in which the neglected (dropped) components are orthogonal to the approximations being kept is presented. General estimate for the condition number of the preconditioned system is given which only depends on the accuracy of individual approximations. The estimate is further improved if, for instance, only the newly computed rows of the factor are modified during each approximation step. In this latter case it is further shown to be sharp. The analysis is illustrated with some existing factorizations in the context of discretized elliptic partial differential equations.
Date: March 16, 2012
Creator: Napov, Artem
Partner: UNT Libraries Government Documents Department

Accurate iterative analytic solution of theKapchinskij-Vladimirskij equations for the case of a matched beam

Description: The well-known Kapchinskij-Vladimirskij (KV) equations are difficult to solve in general, but the problem is simplified for the matched-beam case with sufficient symmetry. They show that the interdependence of the two KV equations is eliminated, so that only one needs to be solved--a great simplification. They present an iterative method of solution which can potentially yield any desired level of accuracy. The lowest level, the well-known smooth approximation, yields simple, explicit results with good accuracy for weak or moderate focusing fields. The next level improves the accuracy for high fields; they previously showed how to maintain a simple explicit format for the results. That paper used expansion in a small parameter to obtain the second level. The present paper, using straightforward iteration, obtains equations of first, second, and third levels of accuracy. For a periodic lattice with beam matched to lattice, they use the lattice and beam parameters as input and solve for phase advances and envelope waveforms. They find excellent agreement with numerical solutions over a wide range of beam emittances and intensities.
Date: August 6, 2006
Creator: Anderson, Oscar A.
Partner: UNT Libraries Government Documents Department

RESISTIVITY MODELING FOR ARBITRARILY SHAPED THREE-DIMENSIONAL STRUCTURES

Description: A numerical technique has been developed to solve the three-dimensional potential distribution about a point source of current located in or on the surface of a half-space containing an arbitrary three-dimensional conductivity distribution. Self-adjoint difference equations are obtained for Poisson's equation using finite-difference approximations in conjunction with an elemental volume discretization of the lower half-space. Potential distribution at all points in the set defining the subsurface are simultaneously solved for multiple point sources of current. Accurate and stable solutions are obtained using full, banded, Cholesky decomposition of the capacitance matrix as well as the recently developed Incomplete Cholesky-Conjugate Gradient Iterative method. A comparison of the two- and three-dimensional simple block-shaped models, for the collinear dipole-dipole array, indicates substantially lower anomaly indices for inhomogeneities of finite strike-extent. In general, the strike-extents of inhomogeneities have to be approximately 10 times the dipole lengths before the response becomes two-dimensional. The saturation effect with increasing conductivity contrasts appears sooner for the three-dimensional conductive inhomogeneities than for corresponding models with infinite strike lengths. A downhole-to-surface configuration of electrodes produces diagnostic total field apparent resistivity maps for three-dimensional buried inhomogeneities. Experiments with various lateral and depth locations of the current pole indicate that mise a la masse surveys give the largest anomaly if a current pole is located asymmetrically and preferably near the top-surface of the buried conductor.
Date: October 1, 1977
Creator: Dey, Abhijit & Morrison, H. Frank
Partner: UNT Libraries Government Documents Department

Adaptive Algebraic Multigrid Methods

Description: Our ability to simulate physical processes numerically is constrained by our ability to solve the resulting linear systems, prompting substantial research into the development of multiscale iterative methods capable of solving these linear systems with an optimal amount of effort. Overcoming the limitations of geometric multigrid methods to simple geometries and differential equations, algebraic multigrid methods construct the multigrid hierarchy based only on the given matrix. While this allows for efficient black-box solution of the linear systems associated with discretizations of many elliptic differential equations, it also results in a lack of robustness due to assumptions made on the near-null spaces of these matrices. This paper introduces an extension to algebraic multigrid methods that removes the need to make such assumptions by utilizing an adaptive process. The principles which guide the adaptivity are highlighted, as well as their application to algebraic multigrid solution of certain symmetric positive-definite linear systems.
Date: April 9, 2004
Creator: Brezina, M; Falgout, R; MacLachlan, S; Manteuffel, T; McCormick, S & Ruge, J
Partner: UNT Libraries Government Documents Department

Reducing Complexity in Parallel Algebraic Multigrid Preconditioners

Description: Algebraic multigrid (AMG) is a very efficient iterative solver and preconditioner for large unstructured linear systems. Traditional coarsening schemes for AMG can, however, lead to computational complexity growth as problem size increases, resulting in increased memory use and execution time, and diminished scalability. Two new parallel AMG coarsening schemes are proposed, that are based on solely enforcing a maximum independent set property, resulting in sparser coarse grids. The new coarsening techniques remedy memory and execution time complexity growth for various large three-dimensional (3D) problems. If used within AMG as a preconditioner for Krylov subspace methods, the resulting iterative methods tend to converge fast. This paper discusses complexity issues that can arise in AMG, describes the new coarsening schemes and examines the performance of the new preconditioners for various large 3D problems.
Date: September 21, 2004
Creator: De Sterck, H; Yang, U M & Heys, J
Partner: UNT Libraries Government Documents Department

The Godunov-Inverse Iteration : A fast and accurate solution to the symmetric tridiagonal eigenvalue problem.

Description: We present a new hybrid algorithm based on Godunov's method for computing eigenvectors of symmetric tridiagonal matrices and Inverse Iteration, which we call the Godunov-Inverse Iteration Algorithm. We use eigenvectors computed according to Godunov's method as starting vectors in the Inverse Iteration, replacing any nonnumeric elements of the Godunov eigenvectors with random uniform numbers. We use the right-hand bounds of the Ritz intervals found by the bisection method as Inverse Iteration shifts, while staying within guaranteed error bounds. In most test cases convergence is reached after only one step of the iteration, producing error estimates that are as good as or superior to those produced by standard Inverse Iteration implementations.
Date: November 27, 2002
Creator: Matsekh, A. M. (Anna M.)
Partner: UNT Libraries Government Documents Department

A multigrid method for variable coefficient Maxwell's equations

Description: This paper presents a multigrid method for solving variable coefficient Maxwell's equations. The novelty in this method is the use of interpolation operators that do not produce multilevel commutativity complexes that lead to multilevel exactness. Rather, the effects of multilevel exactness are built into the level equations themselves--on the finest level using a discrete T-V formulation, and on the coarser grids through the Galerkin coarsening procedure of a T-V formulation. These built-in structures permit the levelwise use of an effective hybrid smoother on the curl-free near-nullspace components, and these structures permit the development of interpolation operators for handling the curl-free and divergence-free error components separately, with the resulting block diagonal interpolation operator not satisfying multilevel commutativity but having good approximation properties for both of these error components. Applying operator-dependent interpolation for each of these error components leads to an effective multigrid scheme for variable coefficient Maxwell's equations, where multilevel commutativity-based methods can degrade. Numerical results are presented to verify the effectiveness of this new scheme.
Date: May 13, 2004
Creator: Jones, J E & Lee, B
Partner: UNT Libraries Government Documents Department