Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “algorithmic efficiency”

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 307 records · Page 17

Parallel peak pruning for scalable SMP contour tree computation

As data sets grow to exascale, automated data analysis and visualisation are increasingly important, to intermediate human understanding and to reduce demands on disk storage via in situ analysis. Trends in architecture of high performance computing systems necessitate analysis algorithms to make effective use of combinations of massively multicore and distributed systems. One of the principal analytic tools is the contour tree, which analyses relationships between contours to identify features of more than local importance. Unfortunately, the predominant algorithms for computing the contour tree are explicitly serial, and founded on serial metaphors, which has limited the scalability of this form of analysis. While there is some work on distributed contour tree computation, and separately on hybrid GPU-CPU computation, there is no efficient algorithm with strong formal guarantees on performance allied with fast practical performance. Here in this paper, we report the first shared SMP algorithm for fully parallel contour tree computation, withfor-mal guarantees of O(lgnlgt) parallel steps and O(n lgn) work, and implementations with up to 10x parallel speed up in OpenMP and up to 50x speed up in NVIDIA Thrust.

97 MATHEMATICS AND COMPUTING↗

Scalable Contour Tree Computation by Data Parallel Peak Pruning

As data sets grow to exascale, automated data analysis and visualization are increasingly important, to intermediate human understanding and to reduce demands on disk storage via in situ analysis. Trends in architecture of high performance computing systems necessitate analysis algorithms to make effective use of combinations of massively multicore and distributed systems. One of the principal analytic tools is the contour tree, which analyses relationships between contours to identify features of more than local importance. Unfortunately, the predominant algorithms for computing the contour tree are explicitly serial, and founded on serial metaphors, which has limited the scalability of this form of analysis. While there is some work on distributed contour tree computation, and separately on hybrid GPU-CPU computation, there is no efficient algorithm with strong formal guarantees on performance allied with fast practical performance. Furthermore, we report the first shared SMP algorithm for fully parallel contour tree computation, with formal guarantees of O(lg V lg t) parallel steps and O(V lg V) work for data with V samples and t contour tree supernodes, and implementations with more than 30× parallel speed up on both CPU using TBB and GPU using Thrust and up 70× speed up compared to the serial sweep and merge algorithm.

97 MATHEMATICS AND COMPUTING↗

Algorithms and Statistical Models for Scientific Discovery in the Petabyte Era

The field of astronomy has arrived at a turning point in terms of size and complexity of both datasets and scientific collaboration. Commensurately, algorithms and statistical models have begun to adapt --- e.g., via the onset of artificial intelligence --- which itself presents new challenges and opportunities for growth. This white paper aims to offer guidance and ideas for how we can evolve our technical and collaborative frameworks to promote efficient algorithmic development and take advantage of opportunities for scientific discovery in the petabyte era. We discuss challenges for discovery in large and complex data sets; challenges and requirements for the next stage of development of statistical methodologies and algorithmic tool sets; how we might change our paradigms of collaboration and education; and the ethical implications of scientists' contributions to widely applicable algorithms and computational modeling. We start with six distinct recommendations that are supported by the commentary following them. This white paper is related to a larger corpus of effort that has taken place within and around the Petabytes to Science Workshops (https://petabytestoscience.github.io/).

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

Dose reconstruction for real-time patient-specific dose estimation in CT

Purpose: Many recent computed tomography (CT) dose reduction approaches belong to one of three categories: statistical reconstruction algorithms, efficient x-ray detectors, and optimized CT acquisition schemes with precise control over the x-ray distribution. The latter category could greatly benefit from fast and accurate methods for dose estimation, which would enable real-time patient-specific protocol optimization. Methods: The authors present a new method for volumetrically reconstructing absorbed dose on a per-voxel basis, directly from the actual CT images. The authors’ specific implementation combines a distance-driven pencil-beam approach to model the first-order x-ray interactions with a set of Gaussian convolution kernels to model the higher-order x-ray interactions. The authors performed a number of 3D simulation experiments comparing the proposed method to a Monte Carlo based ground truth. Results: The authors’ results indicate that the proposed approach offers a good trade-off between accuracy and computational efficiency. The images show a good qualitative correspondence to Monte Carlo estimates. Preliminary quantitative results show errors below 10%, except in bone regions, where the authors see a bigger model mismatch. The computational complexity is similar to that of a low-resolution filtered-backprojection algorithm. Conclusions: The authors present a method for analytic dose reconstruction in CT, similar to the techniques used in radiation therapy planning with megavoltage energies. Future work will include refinements of the proposed method to improve the accuracy as well as a more extensive validation study. The proposed method is not intended to replace methods that track individual x-ray photons, but the authors expect that it may prove useful in applications where real-time patient-specific dose estimation is required.

60 APPLIED LIFE SCIENCES↗

A Preconditioned Low-Rank Projection Method with a Rank-Reduction Scheme for Stochastic Partial Differential Equations

Herein, we consider the numerical solution of large systems of linear equations obtained from the stochastic Galerkin formulation of stochastic partial differential equations. We propose an iterative algorithm that exploits the Kronecker product structure of the linear systems. The proposed algorithm efficiently approximates the solutions in low-rank tensor format. Using standard Krylov subspace methods for the data in tensor format is computationally prohibitive due to the rapid growth of tensor ranks during the iterations. To keep tensor ranks low over the entire iteration process, we devise a rank-reduction scheme that can be combined with the iterative algorithm. The proposed rank-reduction scheme identifies an important subspace in the stochastic domain and compresses tensors of high rank on-the-fly during the iterations. The proposed reduction scheme is a coarse-grid method in that the important subspace can be identified inexpensively in a coarse spatial grid setting. The efficiency of the present method is displayed by numerical experiments on benchmark problems.

97 MATHEMATICS AND COMPUTING↗

Onboard Algorithms for Data Prioritization and Summarization of Aerial Imagery

Many current and future NASA missions are capable of collecting enormous amounts of data, of which only a small portion can be transmitted to Earth. Communications are limited due to distance, visibility constraints, and competing mission downlinks. Long missions and high-resolution, multispectral imaging devices easily produce data exceeding the available bandwidth. To address this situation computationally efficient algorithms were developed for analyzing science imagery onboard the spacecraft. These algorithms autonomously cluster the data into classes of similar imagery, enabling selective downlink of representatives of each class, and a map classifying the terrain imaged rather than the full dataset, reducing the volume of the downlinked data. A range of approaches was examined, including k-means clustering using image features based on color, texture, temporal, and spatial arrangement

Chien, Steve A.↗

Accelerating parameter inference with graphics processing units

Gravitational wave Bayesian parameter inference involves repeated comparisons of GW data to generic candidate predictions. Even with algorithmically efficient methods like RIFT or reduced-order quadrature, the time needed to perform these calculations and overall computational cost can be significant compared to the minutes to hours needed to achieve the goals of low-latency multimessenger astronomy. By translating some elements of the RIFT algorithm to operate on graphics processing units (GPU), we demonstrate substantial performance improvements, enabling dramatically reduced overall cost and latency.

97 MATHEMATICS AND COMPUTING↗

Developing a novel hierarchical approach for multiscale structural reliability predictions for ultra-high consequence applications

Microstructural variabilities are among the predominant sources of uncertainty in structural performance and reliability. We seek to develop efficient algorithms for multiscale calcu- lations for polycrystalline alloys such as aluminum alloy 6061-T6 in environments where ductile fracture is the dominant failure mode. Our approach employs concurrent multiscale methods, but does not focus on their development. They are a necessary but not sufficient ingredient to multiscale reliability predictions. We have focused on how to efficiently use concurrent models for forward propagation because practical applications cannot include fine-scale details throughout the problem domain due to exorbitant computational demand. Our approach begins with a low-fidelity prediction at the engineering scale that is sub- sequently refined with multiscale simulation. The results presented in this report focus on plasticity and damage at the meso-scale, efforts to expedite Monte Carlo simulation with mi- crostructural considerations, modeling aspects regarding geometric representation of grains and second-phase particles, and contrasting algorithms for scale coupling.

36 MATERIALS SCIENCE↗

Correlated pair ansatz with a binary tree structure

We develop an efficient algorithm to implement the recently introduced binary tree state (BTS) ansatz on a classical computer. BTS allows a simple approximation to permanents arising from the computationally intractable antisymmetric product of interacting geminals and respects size-consistency. We show how to compute BTS overlap and reduced density matrices efficiently. We also explore two routes for developing correlated BTS approaches: Jastrow coupled cluster on BTS and linear combinations of BT states. Here, the resulting methods show great promise in benchmark applications to the reduced Bardeen–Cooper–Schrieffer Hamiltonian and the one-dimensional XXZ Heisenberg Hamiltonian.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Parallel Computation of Persistent Homology using the Blowup Complex

We describe a parallel algorithm that computes persistent homology, an algebraic descriptor of a filtered topological space. Our algorithm is distinguished by operating on a spatial decomposition of the domain, as opposed to a decomposition with respect to the filtration. We rely on a classical construction, called the Mayer--Vietoris blowup complex, to glue global topological information about a space from its disjoint subsets. We introduce an efficient algorithm to perform this gluing operation, which may be of independent interest, and describe how to process the domain hierarchically. We report on a set of experiments that help assess the strengths and identify the limitations of our method.

97 MATHEMATICS AND COMPUTING↗

An algorithm to locate the centers of baryon acoustic oscillations

The cosmic structure formed from baryon acoustic oscillations (BAO) in the early universe is imprinted in the galaxy distribution observable in large-scale surveys and is used as a standard ruler in contemporary cosmology. Typically, BAOs are detected as a preferential length scale in two-point statistics, which gives little information about the location of the BAO structures in real space. The aim of the algorithm described in this paper is to find probable centers of BAOs in the cosmic matter distribution. The algorithm convolves the three-dimensional distribution of matter density with a spherical shell kernel of variable radius placed at different locations. The locations that correspond to the highest values of the convolution correspond to the probable centers of BAOs. This method is realized in an open-source, computationally efficient algorithm. Here, we describe the algorithm and present the results of applying it to the SDSS DR9 CMASS survey and associated mock catalogs. A detailed performance study demonstrates the ability of the algorithm to locate BAO centers and in doing so presents a novel detection of the BAO scale in galaxy surveys.

79 ASTRONOMY AND ASTROPHYSICS↗

Efficient Web Services Policy Combination

Large-scale Web security systems usually involve cooperation between domains with non-identical policies. The network management and Web communication software used by the different organizations presents a stumbling block. Many of the tools used by the various divisions do not have the ability to communicate network management data with each other. At best, this means that manual human intervention into the communication protocols used at various network routers and endpoints is required. Developing practical, sound, and automated ways to compose policies to bridge these differences is a long-standing problem. One of the key subtleties is the need to deal with inconsistencies and defaults where one organization proposes a rule on a particular feature, and another has a different rule or expresses no rule. A general approach is to assign priorities to rules and observe the rules with the highest priorities when there are conflicts. The present methods have inherent inefficiency, which heavily restrict their practical applications. A new, efficient algorithm combines policies utilized for Web services. The method is based on an algorithm that allows an automatic and scalable composition of security policies between multiple organizations. It is based on defeasible policy composition, a promising approach for finding conflicts and resolving priorities between rules. In the general case, policy negotiation is an intractable problem. A promising method, suggested in the literature, is when policies are represented in defeasible logic, and composition is based on rules for non-monotonic inference. In this system, policy writers construct metapolicies describing both the policy that they wish to enforce and annotations describing their composition preferences. These annotations can indicate whether certain policy assertions are required by the policy writer or, if not, under what circumstances the policy writer is willing to compromise and allow other assertions to take precedence. Meta-policies are specified in defeasible logic, a computationally efficient non-monotonic logic developed to model human reasoning. One drawback of this method is that at one point the algorithm starts an exhaustive search of all subsets of the set of conclusions of a defeasible theory. Although the propositional defeasible logic has linear complexity, the set of conclusions here may be large, especially in real-life practical cases. This phenomenon leads to an inefficient exponential explosion of complexity. The current process of getting a Web security policy from combination of two meta-policies consists of two steps. The first is generating a new meta-policy that is a composition of the input meta-policies, and the second is mapping the meta-policy onto a security policy. The new algorithm avoids the exhaustive search in the current algorithm, and provides a security policy that matches all requirements of the involved metapolicies.

Vatan, Farrokh↗

Stochastic many-body perturbation theory for anharmonic molecular vibrations

A new quantum Monte Carlo (QMC) method for anharmonic vibrational zero-point energies and transition frequencies is developed, which combines the diagrammatic vibrational many-body perturbation theory based on the Dyson equation with Monte Carlo integration. The infinite sums of the diagrammatic and thus size-consistent first- and second-order anharmonic corrections to the energy and self-energy are expressed as sums of a few m- or 2m-dimensional integrals of wave functions and a potential energy surface (PES) (m is the vibrational degrees of freedom). Each of these integrals is computed as the integrand (including the value of the PES) divided by the value of a judiciously chosen weight function evaluated on demand at geometries distributed randomly but according to the weight function via the Metropolis algorithm. In this way, the method completely avoids cumbersome evaluation and storage of high-order force constants necessary in the original formulation of the vibrational perturbation theory; it furthermore allows even higher-order force constants essentially up to an infinite order to be taken into account in a scalable, memory-efficient algorithm. The diagrammatic contributions to the frequency-dependent self-energies that are stochastically evaluated at discrete frequencies can be reliably interpolated, allowing the self-consistent solutions to the Dyson equation to be obtained. This method, therefore, can compute directly and stochastically the transition frequencies of fundamentals and overtones as well as their relative intensities as pole strengths, without fixed-node errors that plague some QMC. It is shown that, for an identical PES, the new method reproduces the correct deterministic values of the energies and frequencies within a few cm{sup −1} and pole strengths within a few thousandths. With the values of a PES evaluated on the fly at random geometries, the new method captures a noticeably greater proportion of anharmonic effects.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Minimal-memory realization of pearl-necklace encoders of general quantum convolutional codes

Quantum convolutional codes, like their classical counterparts, promise to offer higher error correction performance than block codes of equivalent encoding complexity, and are expected to find important applications in reliable quantum communication where a continuous stream of qubits is transmitted. Grassl and Roetteler devised an algorithm to encode a quantum convolutional code with a ''pearl-necklace'' encoder. Despite their algorithm's theoretical significance as a neat way of representing quantum convolutional codes, it is not well suited to practical realization. In fact, there is no straightforward way to implement any given pearl-necklace structure. This paper closes the gap between theoretical representation and practical implementation. In our previous work, we presented an efficient algorithm to find a minimal-memory realization of a pearl-necklace encoder for Calderbank-Shor-Steane (CSS) convolutional codes. This work is an extension of our previous work and presents an algorithm for turning a pearl-necklace encoder for a general (non-CSS) quantum convolutional code into a realizable quantum convolutional encoder. We show that a minimal-memory realization depends on the commutativity relations between the gate strings in the pearl-necklace encoder. We find a realization by means of a weighted graph which details the noncommutative paths through the pearl necklace. The weight of the longest path in this graph is equal to the minimal amount of memory needed to implement the encoder. The algorithm has a polynomial-time complexity in the number of gate strings in the pearl-necklace encoder.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Dynamic model-based sensor network design algorithm for system efficiency maximization

Here, a dynamic model-based sensor network design (DMSND) algorithm has been developed for maximizing system efficiency for an estimator-based control system. The algorithm synthesizes the optimal sensor network in the face of disturbances or set point changes. Computational expense of the large-scale combinatorial optimization problem is significantly reduced by parallel computing and by using combination of three novel strategies: multi-rate sampling frequency, model order reduction, and use of an incumbent solution that enables early termination of evaluation of infeasible sensor sets. The developed algorithm is applied to an acid gas removal unit as part of an integrated gasification combined cycle power plant with carbon capture. Even though there are more than thousand process states and more than hundred candidate sensor locations, the optimal sensor network design problem for maximizing process efficiency could be solved within couple of hours for a given budget.

47 OTHER INSTRUMENTATION↗

Exploration of efficient reduced-order modeling and a posteriori error estimation

Efficient algorithms are considered for the computation of a reduced-order model based on the proper orthogonal decomposition methodology for the solution of parameterized elliptic partial differential equations. The method relies on partitioning the parameter space into subdomains based on the properties of the solution space and then forming a reduced basis for each of the subdomains. This yields more efficient offline and online stages for the proper orthogonal decomposition method. We extend these ideas for inexpensive adjoint based a posteriori error estimation of both the expensive finite element method solutions and the reduced-order model solutions, for a single and multiple quantities of interest. Finally, various numerical results indicate the efficacy of the approach.

42 ENGINEERING↗

Toward the Minimal Floating Operation Count Cholesky Decomposition of Electron Repulsion Integrals

As quantum chemistry calculations deal with molecular systems of increasing size, the memory requirement to store electron-repulsion integrals (ERIs) greatly outpaces the physical memory available in computing hardware. Here, the Cholesky decomposition of ERIs provides a convenient yet accurate technique to reduce the storage requirement of integrals. Recent developments of a two-step algorithm have drastically reduced the memory operation (MOP) count, leaving the floating operation (FLOP) count as the last frontier of cost reduction in the Cholesky ERI algorithm. In this report, we introduce a dynamic integral tracking, reusing, and compression/elimination protocol embedded in the two-step Cholesky ERI method. Benchmark studies suggest that this technique becomes particularly advantageous when the basis set consists of many computationally expensive high-angular-momentum basis functions. With this dynamic ERI improvement, the Cholesky ERI approach proves to be a highly efficient algorithm with minimal FLOP and MOP count.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Joint Bayesian Component Separation and CMB Power Spectrum Estimation

We describe and implement an exact, flexible, and computationally efficient algorithm for joint component separation and CMB power spectrum estimation, building on a Gibbs sampling framework. Two essential new features are (1) conditional sampling of foreground spectral parameters and (2) joint sampling of all amplitude-type degrees of freedom (e.g., CMB, foreground pixel amplitudes, and global template amplitudes) given spectral parameters. Given a parametric model of the foreground signals, we estimate efficiently and accurately the exact joint foreground- CMB posterior distribution and, therefore, all marginal distributions such as the CMB power spectrum or foreground spectral index posteriors. The main limitation of the current implementation is the requirement of identical beam responses at all frequencies, which restricts the analysis to the lowest resolution of a given experiment. We outline a future generalization to multiresolution observations. To verify the method, we analyze simple models and compare the results to analytical predictions. We then analyze a realistic simulation with properties similar to the 3 yr WMAP data, downgraded to a common resolution of 3 deg FWHM. The results from the actual 3 yr WMAP temperature analysis are presented in a companion Letter.

numerical↗