Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “approximation algorithms”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 1,567 records · Page 87

Effects of ray profile modeling on resolution recovery in clinical CT

Purpose: Iterative image reconstruction gains more and more interest in clinical routine, as it promises to reduce image noise (and thereby patient dose), to reduce artifacts, or to improve spatial resolution. However, among vendors and researchers, there is no consensus of how to best achieve these goals. The authors are focusing on the aspect of geometric ray profile modeling, which is realized by some algorithms, while others model the ray as a straight line. The authors incorporate ray-modeling (RM) in nonregularized iterative reconstruction. That means, instead of using one simple single needle beam to represent the x-ray, the authors evaluate the double integral of attenuation path length over the finite source distribution and the finite detector element size in the numerical forward projection. Our investigations aim at analyzing the resolution recovery (RR) effects of RM. Resolution recovery means that frequencies can be recovered beyond the resolution limit of the imaging system. In order to evaluate, whether clinical CT images can benefit from modeling the geometrical properties of each x-ray, the authors performed a 2D simulation study of a clinical CT fan-beam geometry that includes the precise modeling of these geometrical properties. Methods: All simulations and reconstructions are performed in native fan-beam geometry. A water phantom with resolution bar patterns and a Forbild thorax phantom with circular resolution patterns representing calcifications in the heart region are simulated. An FBP reconstruction with a Ram–Lak kernel is used as a reference reconstruction. The FBP is compared to iterative reconstruction techniques with and without RM: An ordered subsets convex (OSC) algorithm without any RM (OSC), an OSC where the forward projection is modeled concerning the finite focal spot and detector size (OSC-RM) and an OSC with RM and with a matched forward and backprojection pair (OSC-T-RM, T for transpose). In all cases, noise was matched to be able to focus on comparing spatial resolution. The authors use two different simulation settings. Both are based on the geometry of a typical clinical CT system (0.7 mm detector element size at isocenter, 1024 projections per rotation). Setting one has an exaggerated source width of 5.0 mm. Setting two has a realistically small source width of 0.5 mm. The authors also investigate the transition from setting one to two. To quantify image quality, the authors analyze line profiles through the resolution patterns to define a contrast factor (CF) for contrast-resolution plots, and the authors compare the normalized cross-correlation (NCC) with respect to the ground truth of the circular resolution patterns. To independently analyze whether RM is of advantage, the authors implemented several iterative reconstruction algorithms: The statistical iterative reconstruction algorithm OSC, the ordered subsets simultaneous algebraic reconstruction technique (OSSART) and another statistical iterative reconstruction algorithm, denoted with ordered subsets maximum likelihood (OSML) algorithm. All algorithms were implemented both without RM (denoted as OSC, OSSART, and OSML) and with RM (denoted as OSC-RM, OSSART-RM, and OSML-RM). Results: For the unrealistic case of a 5.0 mm focal spot the CF can be improved by a factor of two due to RM: the 4.2 LP/cm bar pattern, which is the first bar pattern that cannot be resolved without RM, can be easily resolved with RM. For the realistic case of a 0.5 mm focus, all results show approximately the same CF. The NCC shows no significant dependency on RM when the source width is smaller than 2.0 mm (as in clinical CT). From 2.0 mm to 5.0 mm focal spot size increasing improvements can be observed with RM. Conclusions: Geometric RM in iterative reconstruction helps improving spatial resolution, if the ray cross-section is significantly larger than the ray sampling distance. In clinical CT, however, the ray is not much thicker than the distance between neighboring ray centers, as the focal spot size is small and detector crosstalk is negligible, due to reflective coatings between detector elements. Therefore,RM appears not to be necessary in clinical CT to achieve resolution recovery.

62 RADIOLOGY AND NUCLEAR MEDICINE↗

Fast, accurate evaluation of exact exchange: The occ-RI-K algorithm

Construction of the exact exchange matrix, K, is typically the rate-determining step in hybrid density functional theory, and therefore, new approaches with increased efficiency are highly desirable. We present a framework with potential for greatly improved efficiency by computing a compressed exchange matrix that yields the exact exchange energy, gradient, and direct inversion of the iterative subspace (DIIS) error vector. The compressed exchange matrix is constructed with one index in the compact molecular orbital basis and the other index in the full atomic orbital basis. To illustrate the advantages, we present a practical algorithm that uses this framework in conjunction with the resolution of the identity (RI) approximation. We demonstrate that convergence using this method, referred to hereafter as occupied orbital RI-K (occ-RI-K), in combination with the DIIS algorithm is well-behaved, that the accuracy of computed energetics is excellent (identical to conventional RI-K), and that significant speedups can be obtained over existing integral-direct and RI-K methods. For a 4400 basis function C{sub 68}H{sub 22} hydrogen-terminated graphene fragment, our algorithm yields a 14 × speedup over the conventional algorithm and a speedup of 3.3 × over RI-K.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

A comparison of transport algorithms for premixed, laminar steady state flames

The effects of different methods of approximating multispecies transport phenomena in models of premixed, laminar, steady state flames were studied. Five approximation methods that span a wide range of computational complexity were developed. Identical data for individual species properties were used for each method. Each approximation method is employed in the numerical solution of a set of five H2-02-N2 flames. For each flame the computed species and temperature profiles, as well as the computed flame speeds, are found to be very nearly independent of the approximation method used. This does not indicate that transport phenomena are unimportant, but rather that the selection of the input values for the individual species transport properties is more important than the selection of the method used to approximate the multispecies transport. Based on these results, a sixth approximation method was developed that is computationally efficient and provides results extremely close to the most sophisticated and precise method used.

Coffee, T. P.↗

Approximations of thermoelastic and viscoelastic control systems

Well-posed models and computational algorithms are developed and analyzed for control of a class of partial differential equations that describe the motions of thermo-viscoelastic structures. An abstract (state space) framework and a general well-posedness result are presented that can be applied to a large class of thermo-elastic and thermo-viscoelastic models. This state space framework is used in the development of a computational scheme to be used in the solution of a linear quadratic regulator (LQR) control problem. A detailed convergence proof is provided for the viscoelastic model and several numerical results are presented to illustrate the theory and to analyze problems for which the theory is incomplete.

Burns, J. A.↗

Convergence behavior of a new DSMC algorithm.

The convergence rate of a new direct simulation Monte Carlo (DSMC) method, termed 'sophisticated DSMC', is investigated for one-dimensional Fourier flow. An argon-like hard-sphere gas at 273.15K and 266.644Pa is confined between two parallel, fully accommodating walls 1mm apart that have unequal temperatures. The simulations are performed using a one-dimensional implementation of the sophisticated DSMC algorithm. In harmony with previous work, the primary convergence metric studied is the ratio of the DSMC-calculated thermal conductivity to its corresponding infinite-approximation Chapman-Enskog theoretical value. As discretization errors are reduced, the sophisticated DSMC algorithm is shown to approach the theoretical values to high precision. The convergence behavior of sophisticated DSMC is compared to that of original DSMC. The convergence of the new algorithm in a three-dimensional implementation is also characterized. Implementations using transient adaptive sub-cells and virtual sub-cells are compared. The new algorithm is shown to significantly reduce the computational resources required for a DSMC simulation to achieve a particular level of accuracy, thus improving the efficiency of the method by a factor of 2.

97 MATHEMATICS AND COMPUTING↗

The Optimization of Trained and Untrained Image Classification Algorithms for Use on Large Spatial Datasets

The HARVIST project seeks to automatically provide an accurate, interactive interface to predict crop yield over the entire United States. In order to accomplish this goal, large images must be quickly and automatically classified by crop type. Current trained and untrained classification algorithms, while accurate, are highly inefficient when operating on large datasets. This project sought to develop new variants of two standard trained and untrained classification algorithms that are optimized to take advantage of the spatial nature of image data. The first algorithm, harvist-cluster, utilizes divide-and-conquer techniques to precluster an image in the hopes of increasing overall clustering speed. The second algorithm, harvistSVM, utilizes support vector machines (SVMs), a type of trained classifier. It seeks to increase classification speed by applying a "meta-SVM" to a quick (but inaccurate) SVM to approximate a slower, yet more accurate, SVM. Speedups were achieved by tuning the algorithm to quickly identify when the quick SVM was incorrect, and then reclassifying low-confidence pixels as necessary. Comparing the classification speeds of both algorithms to known baselines showed a slight speedup for large values of k (the number of clusters) for harvist-cluster, and a significant speedup for harvistSVM. Future work aims to automate the parameter tuning process required for harvistSVM, and further improve classification accuracy and speed. Additionally, this research will move documents created in Canvas into ArcGIS. The launch of the Mars Reconnaissance Orbiter (MRO) will provide a wealth of image data such as global maps of Martian weather and high resolution global images of Mars. The ability to store this new data in a georeferenced format will support future Mars missions by providing data for landing site selection and the search for water on Mars.

Kocurek, Michael J.↗

CgWind: A high-order accurate simulation tool for wind turbines and wind farms

CgWind is a high-fidelity large eddy simulation (LES) tool designed to meet the modeling needs of wind turbine and wind park engineers. This tool combines several advanced computational technologies in order to model accurately the complex and dynamic nature of wind energy applications. The composite grid approach provides high-quality structured grids for the efficient implementation of high-order accurate discretizations of the incompressible Navier-Stokes equations. Composite grids also provide a natural mechanism for modeling bodies in relative motion and complex geometry. Advanced algorithms such as matrix-free multigrid, compact discretizations and approximate factorization will allow CgWind to perform highly resolved calculations efficiently on a wide class of computing resources. Also in development are nonlinear LES subgrid-scale models required to simulate the many interacting scales present in large wind turbine applications. This paper outlines our approach, the current status of CgWind and future development plans.

17 WIND ENERGY↗

Learning Stochastic Parametric Differentiable Predictive Control Policies

We present a scalable unsupervised learning-based method for obtaining explicit control policies for model predictive control problems for stochastic linear systems with additive uncertainties subject to nonlinear chance constraints. We call the proposed method stochastic parametric differentiable predictive control (SP-DPC), which extends the recently proposed deterministic DPC policy optimization algorithm. We formulate the SP-DPC as a deterministic approximation to the stochastic parametric constrained optimal control problem via independent sampling of the problem's parameters and uncertainties. This formulation allows us to directly compute the policy gradients via automatic differentiation of the problem's value function, evaluated over sampled parameters and uncertainties. In particular, the computed expectation of the problem's value function is backpropagated through the finite-time closed-loop system rollouts parametrized by a known nominal system dynamics model and neural control policy. We also provide theoretical probabilistic guarantees on closed-loop stability and chance constraints satisfaction for systems controlled by learned neural policies. We demonstrate the computational efficiency and scalability of the proposed policy optimization algorithm in three numerical examples, including systems with a large number of states or subject to nonlinear constraints.

Drgona, Jan↗

A robust multilevel simultaneous eigenvalue solver

Multilevel (ML) algorithms for eigenvalue problems are often faced with several types of difficulties such as: the mixing of approximated eigenvectors by the solution process, the approximation of incomplete clusters of eigenvectors, the poor representation of solution on coarse levels, and the existence of close or equal eigenvalues. Algorithms that do not treat appropriately these difficulties usually fail, or their performance degrades when facing them. These issues motivated the development of a robust adaptive ML algorithm which treats these difficulties, for the calculation of a few eigenvectors and their corresponding eigenvalues. The main techniques used in the new algorithm include: the adaptive completion and separation of the relevant clusters on different levels, the simultaneous treatment of solutions within each cluster, and the robustness tests which monitor the algorithm's efficiency and convergence. The eigenvectors' separation efficiency is based on a new ML projection technique generalizing the Rayleigh Ritz projection, combined with a technique, the backrotations. These separation techniques, when combined with an FMG formulation, in many cases lead to algorithms of O(qN) complexity, for q eigenvectors of size N on the finest level. Previously developed ML algorithms are less focused on the mentioned difficulties. Moreover, algorithms which employ fine level separation techniques are of O(q(sub 2)N) complexity and usually do not overcome all these difficulties. Computational examples are presented where Schrodinger type eigenvalue problems in 2-D and 3-D, having equal and closely clustered eigenvalues, are solved with the efficiency of the Poisson multigrid solver. A second order approximation is obtained in O(qN) work, where the total computational work is equivalent to only a few fine level relaxations per eigenvector.

Costiner, Sorin↗

A Block-Based MC-SURE Algorithm for Denoising Sensor Data Streams

We propose a strategy to automatically denoise sensor data streams corrupted with noise that can be approximated as additive white Gaussian noise. The proposed block-based method is adapted from the Monte-Carlo-SURE (MC-SURE) algorithm which enables the blind optimization of the denoising parameter of a wide class of filters. Our framework is formulated by identifying and addressing the challenges that arise when the MC-SURE algorithm is applied in an on-line data processing setting, where latency (and the length of data blocks) must be constrained. The strategy has been tested using real datasets. Our results indicate that the proposed method can be effectively used to handle the denoising of real sensor streaming data that reasonably fit the Gaussian model assumption.

97 MATHEMATICS AND COMPUTING↗

Nonperturbative Algorithm for the Resistive Wall Impedance of General Cross-Section Beam Pipes.

Nonperturbative algorithm for the resistive wall impedance of general cross-section beam pipes; ABSTRACT = We present an algorithm for calculating the impedance of infinitely long beam pipes with arbitrary cross section. The method is not restricted to ultrarelativistic beams or perturbative approximations with respect to the wall surface impedance or skin penetration depth. We exemplify our algorithm with a calculation of the impedance for rectangular metallic beam pipes. Unlike the situation in the perturbative regime, where the beam pipe geometry modifies the metallic resistive-wall impedances by only a multiplicative factor, the beam pipe geometry has a more complex influence on the impedance when nonultrarelativistic effects are significant and in the ultrarelativistic regime at both small and large frequencies. Since our algorithm requires the boundary conditions at the beam pipe wall to be provided as linear relations between the transverse components of the electromagnetic field, we discuss a general algorithm to calculate these boundary conditions for multilayer beam pipes with arbitrary cross section.

Macridin, Alexandru↗

Combinatorial theory of the semiclassical evaluation of transport moments II: Algorithmic approach for moment generating functions

Electronic transport through chaotic quantum dots exhibits universal behaviour which can be understood through the semiclassical approximation. Within the approximation, calculation of transport moments reduces to codifying classical correlations between scattering trajectories. These can be represented as ribbon graphs and we develop an algorithmic combinatorial method to generate all such graphs with a given genus. This provides an expansion of the linear transport moments for systems both with and without time reversal symmetry. The computational implementation is then able to progress several orders further than previous semiclassical formulae as well as those derived from an asymptotic expansion of random matrix results. The patterns observed also suggest a general form for the higher orders.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Compressed-sensing-based content-driven hierarchical reconstruction: Theory and application to C-arm cone-beam tomography

Purpose: This paper addresses the reconstruction of x-ray cone-beam computed tomography (CBCT) for interventional C-arm systems. Subsampling of CBCT is a significant issue with C-arms due to their slow rotation and to the low frame rate of their flat panel x-ray detectors. The aim of this work is to propose a novel method able to handle the subsampling artifacts generally observed with analytical reconstruction, through a content-driven hierarchical reconstruction based on compressed sensing. Methods: The central idea is to proceed with a hierarchical method where the most salient features (high intensities or gradients) are reconstructed first to reduce the artifacts these features induce. These artifacts are addressed first because their presence contaminates less salient features. Several hierarchical schemes aiming at streak artifacts reduction are introduced for C-arm CBCT: the empirical orthogonal matching pursuit approach with the ℓ{sub 0} pseudonorm for reconstructing sparse vessels; a convex variant using homotopy with the ℓ{sub 1}-norm constraint of compressed sensing, for reconstructing sparse vessels over a nonsparse background; homotopy with total variation (TV); and a novel empirical extension to nonlinear diffusion (NLD). Such principles are implemented with penalized iterative filtered backprojection algorithms. For soft-tissue imaging, the authors compare the use of TV and NLD filters as sparsity constraints, both optimized with the alternating direction method of multipliers, using a threshold for TV and a nonlinear weighting for NLD. Results: The authors show on simulated data that their approach provides fast convergence to good approximations of the solution of the TV-constrained minimization problem introduced by the compressed sensing theory. Using C-arm CBCT clinical data, the authors show that both TV and NLD can deliver improved image quality by reducing streaks. Conclusions: A flexible compressed-sensing-based algorithmic approach is proposed that is able to accommodate for a wide range of constraints. It is successfully applied to C-arm CBCT images that may not be so well approximated by piecewise constant functions.

60 APPLIED LIFE SCIENCES↗

VEXT: A Virtual Observatory Exploration Toolkit

This final report consists of two main parts. The first is taken from a paper by the PiCA (Pittsburgh Computational Astrostatistics) Group which describes our ongoing work in fast computation of n-point correlation functions. We present here a new algorithm for the fast computation of N-point correlation functions in large astronomical data sets. The algorithm is based on kd-trees which are decorated with cached sufficient statistics thus allowing for orders of magnitude speed-ups over the naive non-tree-based implementation of correlation functions. We further discuss the use of controlled approximations within the computation which allows for further acceleration. In summary, our algorithm now makes it possible to compute exact, all-pairs, measurements of the two, three and four-point correlation functions for cosmological data sets like the Sloan Digital Sky Survey and the next generation of Cosmic Microwave Background experiments. The second part summarizes the progress made by the PiCA Group in this area through the AISR grant.

Schneider, Jeff↗

Localized overlap algorithm for unexpanded dispersion energies

First-principles-based, linearly scaling algorithm has been developed for calculations of dispersion energies from frequency-dependent density susceptibility (FDDS) functions with account of charge-overlap effects. The transition densities in FDDSs are fitted by a set of auxiliary atom-centered functions. The terms in the dispersion energy expression involving products of such functions are computed using either the unexpanded (exact) formula or from inexpensive asymptotic expansions, depending on the location of these functions relative to the dimer configuration. This approach leads to significant savings of computational resources. In particular, for a dimer consisting of two elongated monomers with 81 atoms each in a head-to-head configuration, the most favorable case for our algorithm, a 43-fold speedup has been achieved while the approximate dispersion energy differs by less than 1% from that computed using the standard unexpanded approach. In contrast, the dispersion energy computed from the distributed asymptotic expansion differs by dozens of percent in the van der Waals minimum region. A further increase of the size of each monomer would result in only small increased costs since all the additional terms would be computed from the asymptotic expansion.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Prototype acoustic positioning system for the Pacific Ocean Neutrino Experiment

We present the design and initial performance characterization of the prototype acoustic positioning system intended for the Pacific Ocean Neutrino Experiment. It comprises novel piezo-acoustic receivers with dedicated filtering- and amplification electronics installed in P-ONE instruments and is complemented by a commercial system comprised of cabled and autonomous acoustic pingers for sub-sea installation manufactured by Sonardyne Ltd. We performed an in-depth characterization of the acoustic receiver electronics and their acoustic sensitivity when integrated into P-ONE pressure housings. These show absolute sensitivities of up to -125 dB re V2/μPa2 in a frequency range of 10–40 kHz. We furthermore conducted a positioning measurement campaign in the ocean by deploying three autonomous acoustic pingers on the seafloor, as well as a cabled acoustic interrogator and a P-ONE prototype module deployed from a ship. Using a simple peak-finding detection algorithm, we observe high accuracy in the tracking of relative ranging times at approximately 230–280 μs at distances of up to 1600 m, which is sufficient for positioning detectors in a cubic-kilometer detector and which can be further improved with more involved detection algorithms. The tracking accuracy is further confirmed by independent ranging of the Sonardyne system and closely follows the ship's drift in the wind measured by GPS. The absolute positioning shows the same tracking accuracy with its absolute precision only limited by the large uncertainties of the deployed pinger positions on the seafloor.

Data analysis↗

Technique for atmospheric rate chemistry calculations

The possibility that predictions of atmospheric photochemistry/transport models are sensitive to uncertainties in reaction rates and other inputs stresses the need for rapid numerical integration schemes in rate photochemistry problems. Reducing the computational burden has a major merit in facilitating sensitivity studies to assess the effect of uncertainties on predicted ozone diminutions from NOx (NO + NO2) in the exhaust plume of SST engines. The paper discusses the validity of an algorithmic approach to integration of rate chemistry problems in combustion, developed by Rubel and Baronti for an approximate calculation of the production rate of the i-th chemical species involved. An analysis of two projected SST engines confirms the validity of the proposed algorithm. Because of the relative arithmetical simplicity, it may be easier to treat diffusion rate chemistry calculations using the Rubel and Baronti approximation than would be possible by other approaches.

Matloff, G. L.↗

Accelerating multilevel Markov Chain Monte Carlo using machine learning models

Here, this work presents an efficient approach for accelerating multilevel Markov Chain Monte Carlo (MCMC) sampling for large-scale problems using low-fidelity machine learning models. While conventional techniques for large-scale Bayesian inference often substitute computationally expensive high-fidelity models with machine learning models, thereby introducing approximation errors, our approach offers a computationally efficient alternative by augmenting high-fidelity models with low-fidelity ones within a hierarchical framework. The multilevel approach utilizes the low-fidelity machine learning model (MLM) for inexpensive evaluation of proposed samples thereby improving the acceptance of samples by the high-fidelity model. The hierarchy in our multilevel algorithm is derived from geometric multigrid hierarchy. We utilize an MLM to accelerate the coarse level sampling. Training machine learning model for the coarsest level significantly reduces the computational cost associated with generating training data and training the model. We present an MCMC algorithm to accelerate the coarsest level sampling using MLM and account for the approximation error introduced. We provide theoretical proofs of detailed balance and demonstrate that our multilevel approach constitutes a consistent MCMC algorithm. Additionally, we derive the expression for cost reduction due to machine learning model to facilitate cost analysis of the hierarchical sampling algorithm. Our technique is demonstrated on a standard benchmark inference problem in groundwater flow, where we estimate the probability density of a quantity of interest using a four-level MCMC algorithm. Our proposed algorithm accelerates multilevel sampling by a factor of two while achieving similar accuracy compared to sampling using the standard multilevel algorithm.

97 MATHEMATICS AND COMPUTING↗