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 865 records · Page 48

Vibrations of Elastic Shells of Revolution Partially Filled with Ideal Liquid

We propose an algorithm for the numerical analyses of vibrations of elastic shells of revolution partially filled with ideal incompressible liquids. In the solution of this problem, the wave motions of liquid on its free surface are taken into account. The solution of the problem of hydroelasticity is based on the application of the method of decomposition of the domain of integration of equations of the theory of shells with the use of the variational statement of the problem and on the approximate construction of the operator inverse to the operator of the hydrodynamic part of the problem. We construct a generalized functional of displacements of the shell for which the role of conditions of matching for the solutions in different subdomains is played by the natural boundary conditions. The obtained numerical results are compared with the existing exact solutions of the analyzed problem for a shell in the form of a straight circular cylinder.

42 ENGINEERING↗

An image-guidance system for dynamic dose calculation in prostate brachytherapy using ultrasound and fluoroscopy

Purpose: Brachytherapy is a standard option of care for prostate cancer patients but may be improved by dynamic dose calculation based on localized seed positions. The American Brachytherapy Society states that the major current limitation of intraoperative treatment planning is the inability to localize the seeds in relation to the prostate. An image-guidance system was therefore developed to localize seeds for dynamic dose calculation. Methods: The proposed system is based on transrectal ultrasound (TRUS) and mobile C-arm fluoroscopy, while using a simple fiducial with seed-like markers to compute pose from the nonencoded C-arm. Three or more fluoroscopic images and an ultrasound volume are acquired and processed by a pipeline of algorithms: (1) seed segmentation, (2) fiducial detection with pose estimation, (3) seed matching with reconstruction, and (4) fluoroscopy-to-TRUS registration. Results: The system was evaluated on ten phantom cases, resulting in an overall mean error of 1.3 mm. The system was also tested on 37 patients and each algorithm was evaluated. Seed segmentation resulted in a 1% false negative rate and 2% false positive rate. Fiducial detection with pose estimation resulted in a 98% detection rate. Seed matching with reconstruction had a mean error of 0.4 mm. Fluoroscopy-to-TRUS registration had a mean error of 1.3 mm. Moreover, a comparison of dose calculations between the authors’ intraoperative method and an independent postoperative method shows a small difference of 7% and 2% forD{sub 90} and V{sub 100}, respectively. Finally, the system demonstrated the ability to detect cold spots and required a total processing time of approximately 1 min. Conclusions: The proposed image-guidance system is the first practical approach to dynamic dose calculation, outperforming earlier solutions in terms of robustness, ease of use, and functional completeness.

62 RADIOLOGY AND NUCLEAR MEDICINE↗

Modeling of three-dimensional surfaces using high-level canonical piecewise-linear functions in cylindrical coordinates

In this paper, the potential application of the high-level canonical piecewise-linear model in the field of three-dimensional visualization is proposed. This idea emerges from the premise that a three-dimensional surface can be modeled by a continuous two-dimensional function. In this regard, the main contribution consists in providing a methodology for the construction of such function. For this purpose, the well-known algorithm used in the high-level canonical piecewise-linear model has been modified to achieve functions with greater graphing capability. One of the most notorious changes made with respect to the traditional methodology is the use of a new scheme of function domain partition. Contrary to the simplicial partitioning, in our proposal, an equally distributed angular partitioning is considered. With this, the resulting approximate function is expressed in cylindrical coordinates which overcome the typical limitation of graphs in Cartesian coordinates of only representing single-valued surfaces. Another remarkable change can be found in the range of evaluation of the function. Instead of using an open interval, in our approach, a closed interval from 0 to 2π is adopted. To support this proposal, illustrative case studies are reported. Numerical simulations demonstrate the effectiveness of this type of representation model not only in visual perception of three-dimensional surfaces, but also in more complex tasks like volume estimation.

97 MATHEMATICS AND COMPUTING↗

Exploring the holographic entropy cone via reinforcement learning

We develop a reinforcement learning algorithm to study the holographic entropy cone. Given a target entropy vector, our algorithm searches for a graph realization whose min-cut entropies match the target vector. If the target vector does not admit such a graph realization, it must lie outside the cone, in which case the algorithm finds a graph whose corresponding entropy vector most nearly approximates the target and allows us to probe the location of the facets. For the N = 3 cone, we confirm that our algorithm successfully rediscovers monogamy of mutual information beginning with a target vector outside the holographic entropy cone. We then apply the algorithm to the N = 6 cone, analyzing the 6 mystery extreme rays of the subadditivity cone from [1] that satisfy all known holographic entropy inequalities yet lacked graph realizations. We found realizations for 3 of them, proving they are genuine extreme rays of the holographic entropy cone, while providing evidence that the remaining 3 are not realizable, implying unknown holographic inequalities exist for N = 6.

AdS-CFT correspondence↗

Solvers for $\mathcal{O} (N)$ Electronic Structure in the Strong Scaling Limit

Here we present a hybrid OpenMP/Charm\tt++ framework for solving the $\mathcal{O} (N)$ self-consistent-field eigenvalue problem with parallelism in the strong scaling regime, $P\gg{N}$, where $P$ is the number of cores, and $N$ is a measure of system size, i.e., the number of matrix rows/columns, basis functions, atoms, molecules, etc. This result is achieved with a nested approach to spectral projection and the sparse approximate matrix multiply [Bock and Challacombe, SIAM J. Sci. Comput., 35 (2013), pp. C72--C98], and involves a recursive, task-parallel algorithm, often employed by generalized $N$-Body solvers, to occlusion and culling of negligible products in the case of matrices with decay. Lastly, employing classic technologies associated with generalized $N$-Body solvers, including overdecomposition, recursive task parallelism, orderings that preserve locality, and persistence-based load balancing, we obtain scaling beyond hundreds of cores per molecule for small water clusters ([H${}_2$O]${}_N$, $N \in \{ 30, 90, 150 \}$, $P/N \approx \{ 819, 273, 164 \}$) and find support for an increasingly strong scalability with increasing system size $N$.

97 MATHEMATICS AND COMPUTING↗

Manifold Sampling for Optimization of Nonconvex Functions That Are Piecewise Linear Compositions of Smooth Components

Here, we develop a manifold sampling algorithm for the minimization of a nonsmooth composite function $f \triangleq \psi + h \circ F$ when $\psi$ is smooth with known derivatives, $h$ is a known, nonsmooth, piecewise linear function, and $F$ is smooth but expensive to evaluate. The trust-region algorithm classifies points in the domain of $h$ as belonging to different manifolds and uses this knowledge when computing search directions. Since $h$ is known, classifying objective manifolds using only the values of $F$ is simple. We prove that all cluster points of the sequence of the manifold sampling algorithm iterates are Clarke stationary; this holds although points evaluated by the algorithm are not assumed to be differentiable and when only approximate derivatives of $F$ are available. Numerical results show that manifold sampling using zeroth-order information about $F$ is competitive with algorithms that employ exact subgradient values from $\partial f$.

97 MATHEMATICS AND COMPUTING↗

Fluid dynamic design and experimental study of an aspirated temperature measurement platform used in climate observation

Due to the solar radiation effect, current air temperature sensors inside a thermometer screen or radiation shield may produce measurement errors that are 0.8 °C or higher. To improve the observation accuracy, an aspirated temperature measurement platform is designed. A computational fluid dynamics (CFD) method is implemented to analyze and calculate the radiation error of the aspirated temperature measurement platform under various environmental conditions. Then, a radiation error correction equation is obtained by fitting the CFD results using a genetic algorithm (GA) method. In order to verify the performance of the temperature sensor, the aspirated temperature measurement platform, temperature sensors with a naturally ventilated radiation shield, and a thermometer screen are characterized in the same environment to conduct the intercomparison. The average radiation errors of the sensors in the naturally ventilated radiation shield and the thermometer screen are 0.44 °C and 0.25 °C, respectively. In contrast, the radiation error of the aspirated temperature measurement platform is as low as 0.05 °C. This aspirated temperature sensor allows the radiation error to be reduced by approximately 88.6% compared to the naturally ventilated radiation shield, and allows the error to be reduced by a percentage of approximately 80% compared to the thermometer screen. The mean absolute error and root mean square error between the correction equation and experimental results are 0.032 °C and 0.036 °C, respectively, which demonstrates the accuracy of the CFD and GA methods proposed in this research.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

An efficient reconstruction algorithm for differential phase-contrast tomographic images from a limited number of views

The main focus of this paper is reconstruction of tomographic phase-contrast image from a set of projections. We propose an efficient reconstruction algorithm for differential phase-contrast computed tomography that can considerably reduce the number of projections required for reconstruction. The key result underlying this research is a projection theorem that states that the second derivative of the projection set is linearly related to the Laplacian of the tomographic image. The proposed algorithm first reconstructs the Laplacian image of the phase-shift distribution from the second-derivative of the projections using total variation regularization. The second step is to obtain the phase-shift distribution by solving a Poisson equation whose source is the Laplacian image previously reconstructed under the Dirichlet condition. We demonstrate the efficacy of this algorithm using both synthetically generated simulation data and projection data acquired experimentally at a synchrotron. The experimental phase data were acquired from a human coronary artery specimen using dark-field-imaging optics pioneered by our group. Our results demonstrate that the proposed algorithm can reduce the number of projections to approximately 33% as compared with the conventional filtered backprojection method, without any detrimental effect on the image quality.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

A PARALLEL MONTE CARLO CODE FOR SIMULATING COLLISIONAL N-BODY SYSTEMS

We present a new parallel code for computing the dynamical evolution of collisional N-body systems with up to N {approx} 10{sup 7} particles. Our code is based on the Henon Monte Carlo method for solving the Fokker-Planck equation, and makes assumptions of spherical symmetry and dynamical equilibrium. The principal algorithmic developments involve optimizing data structures and the introduction of a parallel random number generation scheme as well as a parallel sorting algorithm required to find nearest neighbors for interactions and to compute the gravitational potential. The new algorithms we introduce along with our choice of decomposition scheme minimize communication costs and ensure optimal distribution of data and workload among the processing units. Our implementation uses the Message Passing Interface library for communication, which makes it portable to many different supercomputing architectures. We validate the code by calculating the evolution of clusters with initial Plummer distribution functions up to core collapse with the number of stars, N, spanning three orders of magnitude from 10{sup 5} to 10{sup 7}. We find that our results are in good agreement with self-similar core-collapse solutions, and the core-collapse times generally agree with expectations from the literature. Also, we observe good total energy conservation, within {approx}< 0.04% throughout all simulations. We analyze the performance of the code, and demonstrate near-linear scaling of the runtime with the number of processors up to 64 processors for N = 10{sup 5}, 128 for N = 10{sup 6} and 256 for N = 10{sup 7}. The runtime reaches saturation with the addition of processors beyond these limits, which is a characteristic of the parallel sorting algorithm. The resulting maximum speedups we achieve are approximately 60 Multiplication-Sign , 100 Multiplication-Sign , and 220 Multiplication-Sign , respectively.

79 ASTRONOMY AND ASTROPHYSICS↗

Multi-jet Merging with NLO Matrix Elements

In the algorithm presented here, the ME+PS approach to merge samples of tree-level matrix elements into inclusive event samples is combined with the POWHEG method, which includes exact next-to-leading order matrix elements in the parton shower. The advantages of the method are discussed and the quality of its implementation in SHERPA is exemplified by results for e{sup +}e{sup -} annihilation into hadrons at LEP, for deep-inelastic lepton-nucleon scattering at HERA, for Drell-Yan lepton-pair production at the Tevatron and for W{sup +}W{sup -}-production at LHC energies. The simulation of hard QCD radiation in parton-shower Monte Carlos has seen tremendous progress over the last years. It was largely stimulated by the need for more precise predictions at LHC energies where the large available phase space allows additional hard QCD radiation alongside known Standard Model processes or even signals from new physics. Two types of algorithms have been developed, which allow to improve upon the soft-collinear approximations made in the parton shower, such that hard radiation is simulated according to exact matrix elements. In the ME+PS approach [1] higher-order tree-level matrix elements for different final-state jet multiplicity are merged with each other and with subsequent parton shower emissions to generate an inclusive sample. Such a prescription is invaluable for analyses which are sensitive to final states with a large jet multiplicity. The only remaining deficiency of such tree-level calculations is the large uncertainty stemming from scale variations. The POWHEG method [2] solves this problem for the lowest multiplicity subprocess by combining full NLO matrix elements with the parton shower. While this leads to NLO accuracy in the inclusive cross section and the exact radiation pattern for the first emission, it fails to describe higher-order emissions with improved accuracy. Thus it is not sufficient if final states with high jet multiplicities are considered. With the complementary advantages of these two approaches, the question arises naturally whether it would be possible to combine them into an even more powerful one. Such a combined algorithm was independently developed in [5] and [6]. Here a summary of the algorithm is given and predictions from corresponding Monte-Carlo predictions are presented.

43 PARTICLE ACCELERATORS↗

Multi-Scale Initial Conditions For Cosmological Simulations

We discuss a new algorithm to generate multi-scale initial conditions with multiple levels of refinements for cosmological 'zoom-in' simulations. The method uses an adaptive convolution of Gaussian white noise with a real-space transfer function kernel together with an adaptive multi-grid Poisson solver to generate displacements and velocities following first- (1LPT) or second-order Lagrangian perturbation theory (2LPT). The new algorithm achieves rms relative errors of the order of 10{sup -4} for displacements and velocities in the refinement region and thus improves in terms of errors by about two orders of magnitude over previous approaches. In addition, errors are localized at coarse-fine boundaries and do not suffer from Fourier-space-induced interference ringing. An optional hybrid multi-grid and Fast Fourier Transform (FFT) based scheme is introduced which has identical Fourier-space behaviour as traditional approaches. Using a suite of re-simulations of a galaxy cluster halo our real-space-based approach is found to reproduce correlation functions, density profiles, key halo properties and subhalo abundances with per cent level accuracy. Finally, we generalize our approach for two-component baryon and dark-matter simulations and demonstrate that the power spectrum evolution is in excellent agreement with linear perturbation theory. For initial baryon density fields, it is suggested to use the local Lagrangian approximation in order to generate a density field for mesh-based codes that is consistent with the Lagrangian perturbation theory instead of the current practice of using the Eulerian linearly scaled densities.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

Faster Tensor Network Decoding for Topological Quantum Codes

We present a fast and Bayes-optimal-approximating tensor network decoder for planar quantum LDPC codes based on the tensor renormalization group algorithm, originally proposed by Levin, and Nave. By precomputing the renormalization group flow for the null syndrome, we need only recompute tensor contractions in the causal cone of the measured syndrome at the time of decoding. This allows us to achieve an overall runtime complexity of ($pnχ^6$) where p is the depolarizing noise rate, and χ is the cutoff value used to control singular value decomposition approximations used in the algorithm. We apply our decoder to the surface code in the code capacity noise model and compare its performance to the original matrix product state (MPS) tensor network decoder introduced by Bravyi, Suchara, and Vargo. The MPS decoder has a p-independent runtime complexity of $\mathcal{O}(nχ^3)$ resulting in significantly slower decoding times compared to our algorithm in the low-p regime.

97 MATHEMATICS AND COMPUTING↗

Cholesky-based experimental design for Gaussian process and kernel-based emulation and calibration.

Gaussian processes and other kernel-based methods are used extensively to construct approximations of multivariate data sets. The accuracy of these approximations is dependent on the data used. This paper presents a computationally efficient algorithm to greedily select training samples that minimize the weighted L p error of kernel-based approximations for a given number of data. The method successively generates nested samples, with the goal of minimizing the error in high probability regions of densities specified by users. The algorithm presented is extremely simple and can be implemented using existing pivoted Cholesky factorization methods. Training samples are generated in batches which allows training data to be evaluated (labeled) in parallel. For smooth kernels, the algorithm performs comparably with the greedy integrated variance design but has significantly lower complexity. Numerical experiments demonstrate the efficacy of the approach for bounded, unbounded, multi-modal and non-tensor product densities. We also show how to use the proposed algorithm to efficiently generate surrogates for inferring unknown model parameters from data using Bayesian inference.

97 MATHEMATICS AND COMPUTING↗

LOCALIZATION OF SHORT DURATION GRAVITATIONAL-WAVE TRANSIENTS WITH THE EARLY ADVANCED LIGO AND VIRGO DETECTORS

The Laser Interferometer Gravitational wave Observatory (LIGO) and Virgo advanced ground-based gravitational-wave detectors will begin collecting science data in 2015. With first detections expected to follow, it is important to quantify how well generic gravitational-wave transients can be localized on the sky. This is crucial for correctly identifying electromagnetic counterparts as well as understanding gravitational-wave physics and source populations. We present a study of sky localization capabilities for two search and parameter estimation algorithms: coherent WaveBurst, a constrained likelihood algorithm operating in close to real-time, and LALInferenceBurst, a Markov chain Monte Carlo parameter estimation algorithm developed to recover generic transient signals with latency of a few hours. Furthermore, we focus on the first few years of the advanced detector era, when we expect to only have two (2015) and later three (2016) operational detectors, all below design sensitivity. These detector configurations can produce significantly different sky localizations, which we quantify in detail. We observe a clear improvement in localization of the average detected signal when progressing from two-detector to three-detector networks, as expected. Although localization depends on the waveform morphology, approximately 50% of detected signals would be imaged after observing 100-200 deg{sup 2} in 2015 and 60-110 deg{sup 2} in 2016, although knowledge of the waveform can reduce this to as little as 22 deg{sup 2}. This is the first comprehensive study on sky localization capabilities for generic transients of the early network of advanced LIGO and Virgo detectors, including the early LIGO-only two-detector configuration.

79 ASTRONOMY AND ASTROPHYSICS↗

The metric of the cosmos from luminosity and age data

This paper presents the algorithm for determining the Lemaître-Tolman model that best fits given datasets for maximum stellar ages, and SNIa luminosities, both as functions of redshift. It then applies it to current cosmological data. Special attention must be given to the handling of the origin, and the region of the maximum diameter distances. As with a previous combination of datasets (galaxy number counts and luminosity distances versus redshift), there are relationships that must hold at the region of the maximum diameter distance, which are unlikely to be obeyed exactly by real data. We show how to make corrections that enable a self-consistent solution to be found. We address the questions of the best way to approximate discrete data with smooth functions, and how to estimate the uncertainties of the output — the 3 free functions that determine a specific Lemaître-Tolman metric. While current data does not permit any confidence in our results, we show that the method works well, and reasonable Lemaître-Tolman models do fit with or without a cosmological constant.

79 ASTRONOMY AND ASTROPHYSICS↗

Exact milestoning

A new theory and an exact computer algorithm for calculating kinetics and thermodynamic properties of a particle system are described. The algorithm avoids trapping in metastable states, which are typical challenges for Molecular Dynamics (MD) simulations on rough energy landscapes. It is based on the division of the full space into Voronoi cells. Prior knowledge or coarse sampling of space points provides the centers of the Voronoi cells. Short time trajectories are computed between the boundaries of the cells that we call milestones and are used to determine fluxes at the milestones. The flux function, an essential component of the new theory, provides a complete description of the statistical mechanics of the system at the resolution of the milestones. We illustrate the accuracy and efficiency of the exact Milestoning approach by comparing numerical results obtained on a model system using exact Milestoning with the results of long trajectories and with a solution of the corresponding Fokker-Planck equation. The theory uses an equation that resembles the approximate Milestoning method that was introduced in 2004 [A. K. Faradjian and R. Elber, J. Chem. Phys. 120(23), 10880-10889 (2004)]. However, the current formulation is exact and is still significantly more efficient than straightforward MD simulations on the system studied.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Scalable Methods for Electronic Excitations and Optical Responses in Nanostructures: Mathematics to Algorithms to Observables

The work reported here took place at the University of Minnesota from September 15, 2003 to November 14, 2005. This funding resulted in 10 invited articles or book chapters, 37 articles in refereed journals and 13 invited talks. The funding helped train 5 PhD students. The research supported by this grant focused on developing theoretical methods for predicting and understanding the properties of matter at the nanoscale. Within this regime, new phenomena occur that are characteristic of neither the atomic limit, nor the crystalline limit. Moreover, this regime is crucial for understanding the emergence of macroscopic properties such as ferromagnetism. For example, elemental Fe clusters possess magnetic moments that reside between the atomic and crystalline limits, but the transition from the atomic to the crystalline limit is not a simple interpolation between the two size regimes. To capitalize properly on predicting such phenomena in this transition regime, a deeper understanding of the electronic, magnetic and structural properties of matter is required, e.g., electron correlation effects are enhanced within this size regime and the surface of a confined system must be explicitly included. A key element of our research involved the construction of new algorithms to address problems peculiar to the nanoscale. Typically, one would like to consider systems with thousands of atoms or more, e.g., a silicon nanocrystal that is 7 nm in diameter would contain over 10,000 atoms. Previous ab initio methods could address systems with hundreds of atoms whereas empirical methods can routinely handle hundreds of thousands of atoms (or more). However, these empirical methods often rely on ad hoc assumptions and lack incorporation of structural and electronic degrees of freedom. The key theoretical ingredients in our work involved the use of ab initio pseudopotentials and density functional approaches. The key numerical ingredients involved the implementation of algorithms for solving the Kohn-Sham equation without the use of an explicit basis, i.e., a real space grid. We invented algorithms for a solution of the Kohn-Sham equation based on Chebyshev 'subspace filtering'. Our filtering algorithms dramatically enhanced our ability to explore systems with thousands of atoms, i.e., we examined silicon quantum dots with approximately 11,000 atoms (or 40,000 electrons). We applied this algorithm to a number of nanoscale systems to examine the role of quantum confinement on electronic and magnetic properties: (1) Doping of nanocrystals and nanowires, including both magnetic and non-magnetic dopants and the role of self-purification; (2) Optical excitations and electronic properties of nanocrystals; (3) Intrinsic defects in nanostructures; and (4) The emergence of ferromagnetism from atoms to crystals.

36 MATERIALS SCIENCE↗

BayesCLUMPY: BAYESIAN INFERENCE WITH CLUMPY DUSTY TORUS MODELS

Our aim is to present a fast and general Bayesian inference framework based on the synergy between machine learning techniques and standard sampling methods and apply it to infer the physical properties of clumpy dusty torus using infrared photometric high spatial resolution observations of active galactic nuclei. We make use of the Metropolis-Hastings Markov Chain Monte Carlo algorithm for sampling the posterior distribution function. Such distribution results from combining all a priori knowledge about the parameters of the model and the information introduced by the observations. The main difficulty resides in the fact that the model used to explain the observations is computationally demanding and the sampling is very time consuming. For this reason, we apply a set of artificial neural networks that are used to approximate and interpolate a database of models. As a consequence, models not present in the original database can be computed ensuring continuity. We focus on the application of this solution scheme to the recently developed public database of clumpy dusty torus models. The machine learning scheme used in this paper allows us to generate any model from the database using only a factor of 10{sup -4} of the original size of the database and a factor of 10{sup -3} in computing time. The posterior distribution obtained for each model parameter allows us to investigate how the observations constrain the parameters and which ones remain partially or completely undetermined, providing statistically relevant confidence intervals. As an example, the application to the nuclear region of Centaurus A shows that the optical depth of the clouds, the total number of clouds, and the radial extent of the cloud distribution zone are well constrained using only six filters. The code is freely available from the authors.

79 ASTRONOMY AND ASTROPHYSICS↗