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 379 records · Page 21

An efficient particle Fokker–Planck algorithm for rarefied gas flows

This paper is devoted to the algorithmic improvement and careful analysis of the Fokker–Planck kinetic model derived by Jenny et al. [1] and Gorji et al. [2]. The motivation behind the Fokker–Planck based particle methods is to gain efficiency in low Knudsen rarefied gas flow simulations, where conventional direct simulation Monte Carlo (DSMC) becomes expensive. This can be achieved due to the fact that the resulting model equations are continuous stochastic differential equations in velocity space. Accordingly, the computational particles evolve along independent stochastic paths and thus no collision needs to be calculated. Therefore the computational cost of the solution algorithm becomes independent of the Knudsen number. In the present study, different computational improvements were persuaded in order to augment the method, including an accurate time integration scheme, local time stepping and noise reduction. For assessment of the performance, gas flow around a cylinder and lid driven cavity flow were studied. Convergence rates, accuracy and computational costs were compared with respect to DSMC for a range of Knudsen numbers (from hydrodynamic regime up to above one). In all the considered cases, the model together with the proposed scheme give rise to very efficient yet accurate solution algorithms.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Electronically nonadiabatic wave packet propagation using frozen Gaussian scattering

We present an approach, which allows to employ the adiabatic wave packet propagation technique and semiclassical theory to treat the nonadiabatic processes by using trajectory hopping. The approach developed generates a bunch of hopping trajectories and gives all additional information to incorporate the effect of nonadiabatic coupling into the wave packet dynamics. This provides an interface between a general adiabatic frozen Gaussian wave packet propagation method and the trajectory surface hopping technique. The basic idea suggested in [A. D. Kondorskiy and H. Nakamura, J. Chem. Phys. 120, 8937 (2004)] is revisited and complemented in the present work by the elaboration of efficient numerical algorithms. We combine our approach with the adiabatic Herman-Kluk frozen Gaussian approximation. The efficiency and accuracy of the resulting method is demonstrated by applying it to popular benchmark model systems including three Tully’s models and 24D model of pyrazine. It is shown that photoabsorption spectrum is successfully reproduced by using a few hundreds of trajectories. We employ the compact finite difference Hessian update scheme to consider feasibility of the ab initio “on-the-fly” simulations. It is found that this technique allows us to obtain the reliable final results using several Hessian matrix calculations per trajectory.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Learning to Predict Arbitrary Quantum Processes

We present an efficient machine-learning (ML) algorithm for predicting any unknown quantum process ℰ over 𝑛 qubits. For a wide range of distributions 𝒟 on arbitrary 𝑛-qubit states, we show that this ML algorithm can learn to predict any local property of the output from the unknown process ℰ, with a small average error over input states drawn from 𝒟. The ML algorithm is computationally efficient even when the unknown process is a quantum circuit with exponentially many gates. Our algorithm combines efficient procedures for learning properties of an unknown state and for learning a low-degree approximation to an unknown observable. The analysis hinges on proving new norm inequalities, including a quantum analogue of the classical Bohnenblust-Hille inequality, which we derive by giving an improved algorithm for optimizing local Hamiltonians. Numerical experiments on predicting quantum dynamics with evolution time up to 10 6 and system size up to 50 qubits corroborate our proof. Overall, our results highlight the potential for ML models to predict the output of complex quantum dynamics much faster than the time needed to run the process itself.

quantum computation↗

Efficient block preconditioned eigensolvers for linear response time-dependent density functional theory

We present two efficient iterative algorithms for solving the linear response eigen- value problem arising from the time dependent density functional theory. Although the matrix to be diagonalized is nonsymmetric, it has a special structure that can be exploited to save both memory and floating point operations. In particular, the nonsymmetric eigenvalue problem can be transformed into a product eigenvalue problem that is self-adjoint with respect to a K-inner product. This product eigenvalue problem can be solved efficiently by a modified Davidson algorithm and a modified locally optimal block preconditioned conjugate gradient (LOBPCG) algorithm that make use of the K-inner product. The solution of the product eigenvalue problem yields one component of the eigenvector associated with the original eigenvalue problem. However, the other component of the eigenvector can be easily recovered in a postprocessing procedure. Therefore, the algorithms we present here are more efficient than existing algorithms that try to approximate both components of the eigenvectors simultaneously. The efficiency of the new algorithms is demonstrated by numerical examples.

97 MATHEMATICS AND COMPUTING↗

A Posteriori Error Analysis of Two-Stage Computation Methods with Application to Efficient Discretization and the Parareal Algorithm

We consider numerical methods for initial value problems that employ a two stage approach consisting of solution on a relatively coarse discretization followed by solution on a relatively fine discretization. Examples include adaptive error control, parallel-in-time solution schemes, and efficient solution of adjoint problems for computing a posteriori error estimates. We describe a general formulation of two stage computations then perform a general a posteriori error analysis based on computable residuals and solution of an adjoint problem. The analysis accommodates various variations in the two stage computation and in formulation of the adjoint problems. We apply the analysis to compute “dual-weighted” a posteriori error estimates, to develop novel algorithms for efficient solution that take into account cancellation of error, and to the Parareal Algorithm. We test the various results using several numerical examples.

97 MATHEMATICS AND COMPUTING↗

A Linear-Complexity Tensor Butterfly Algorithm for Compressing High-Dimensional Oscillatory Integral Operators

This paper presents a multilevel tensor compression algorithm called tensor butterfly algorithm for efficiently representing large-scale and high-dimensional oscillatory integral operators, including Green's functions for wave equations and integral transforms such as Radon transforms and Fourier transforms. The proposed algorithm leverages a tensor extension of the so-called complementary low-rank property of existing matrix butterfly algorithms. The algorithm partitions the discretized integral operator tensor into subtensors of multiple levels and factorizes each subtensor at the middle level as a Tucker-type interpolative decomposition, whose factor matrices are formed in a multilevel fashion. For a d-dimensional (d > 1) integral operator discretized into a 2d-mode tensor with n2d entries, the overall CPU time and memory requirement scale as O(nd), in stark contrast to the O(nd log n) complexity of existing matrix algorithms such as matrix butterfly algorithms and fast Fourier transforms (FFTs), where n is the number of points per direction. When comparing with other tensor algorithms such as quantized tensor train (QTT), the proposed algorithm also shows superior CPU and memory performance for tensor contraction. Remarkably, the tensor butterfly algorithm can efficiently model high-frequency Green's function interactions between two unit cubes, each spanning 512 wavelengths per direction, which represents problems of scale over 512× larger than that existing butterfly algorithms can handle, with the same amount of computation resources. On the other hand, for a problem representing 64 wavelengths per direction, which is the largest size existing algebraic matrix algorithms can handle, our tensor butterfly algorithm exhibits 200x speedups and 30× memory reduction compared with existing ones. Moreover, the tensor butterfly algorithm also permits O(nd)-complexity FFTs and Radon transforms up to d = 6 dimensions.

Kielstra, P Michael↗

Provably efficient machine learning for quantum many-body problems

Classical machine learning (ML) provides a potentially powerful approach to solving challenging quantum many-body problems in physics and chemistry. However, the advantages of ML over traditional methods have not been firmly established. In this work, we prove that classical ML algorithms can efficiently predict ground-state properties of gapped Hamiltonians after learning from other Hamiltonians in the same quantum phase of matter. By contrast, under a widely accepted conjecture, classical algorithms that do not learn from data cannot achieve the same guarantee. We also prove that classical ML algorithms can efficiently classify a wide range of quantum phases. Extensive numerical experiments corroborate our theoretical results in a variety of scenarios, including Rydberg atom systems, two-dimensional random Heisenberg models, symmetry-protected topological phases, and topologically ordered phases.

Science & Technology - Other Topics↗

Self-learning Monte Carlo method

Monte Carlo simulation is an unbiased numerical tool for studying classical and quantum many-body systems. One of its bottlenecks is the lack of a general and efficient update algorithm for large size systems close to the phase transition, for which local updates perform badly. In this Rapid Communication, we propose a general-purpose Monte Carlo method, dubbed self-learning Monte Carlo (SLMC), in which an efficient update algorithm is first learned from the training data generated in trial simulations and then used to speed up the actual simulation. Lastly, we demonstrate the efficiency of SLMC in a spin model at the phase transition point, achieving a 10–20 times speedup.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

MetaBAT 2: an adaptive binning algorithm for robust and efficient genome reconstruction from metagenome assemblies

We previously reported MetaBAT, an automated metagenome binning software tool to reconstruct single genomes from microbial communities for subsequent analyses of uncultivated microbial species. MetaBAT has become one of the most popular binning tools largely due to its computational efficiency and ease of use, especially in binning experiments with a large number of samples and a large assembly. MetaBAT requires users to choose parameters to fine-tune its sensitivity and specificity. If those parameters are not chosen properly, binning accuracy can suffer, especially on assemblies of poor quality. Here we developed MetaBAT 2 to overcome this problem. MetaBAT 2 uses a new adaptive binning algorithm to eliminate manual parameter tuning. We also performed extensive software engineering optimization to increase both computational and memory efficiency. Comparing MetaBAT 2 to alternative software tools on over 100 real world metagenome assemblies shows superior accuracy and computing speed. Binning a typical metagenome assembly takes only a few minutes on a single commodity workstation. We therefore recommend the community adopts MetaBAT 2 for their metagenome binning experiments. MetaBAT 2 is open source software and available at https://bitbucket.org/berkeleylab/metabat .

Kang, Dongwan↗

MetaBAT 2: an adaptive binning algorithm for robust and efficient genome reconstruction from metagenome assemblies

We previously reported on MetaBAT, an automated metagenome binning software tool to reconstruct single genomes from microbial communities for subsequent analyses of uncultivated microbial species. MetaBAT has become one of the most popular binning tools largely due to its computational efficiency and ease of use, especially in binning experiments with a large number of samples and a large assembly. MetaBAT requires users to choose parameters to fine-tune its sensitivity and specificity. If those parameters are not chosen properly, binning accuracy can suffer, especially on assemblies of poor quality. Here, we developed MetaBAT 2 to overcome this problem. MetaBAT 2 uses a new adaptive binning algorithm to eliminate manual parameter tuning. We also performed extensive software engineering optimization to increase both computational and memory efficiency. Comparing MetaBAT 2 to alternative software tools on over 100 real world metagenome assemblies shows superior accuracy and computing speed. Binning a typical metagenome assembly takes only a few minutes on a single commodity workstation. We therefore recommend the community adopts MetaBAT 2 for their metagenome binning experiments. MetaBAT 2 is open source software and available at https://bitbucket.org/berkeleylab/metabat .

59 BASIC BIOLOGICAL SCIENCES↗

Discovery of a meta-stable Al-Sm phase with unknown stoichiometry using a genetic algorithm

Unknown crystalline phases observed during the devitrification process of glassy metal alloys significantly limit our ability to understand and control phase selection in these systems driven far from equilibrium. Here, we report a new meta-stable Al 5 Sm phase identified by simultaneously searching Al-rich compositions of the Al–Sm system, using an efficient genetic algorithm. The excellent match between calculated and experimental X-ray diffraction patterns confirms that this new phase appeared in the crystallization of melt-spun Al 90 Sm 10 alloys.

Zhang, Feng↗

Occupancy-Based HVAC Control with Short-Term Occupancy Prediction Algorithms for Energy-Efficient Buildings

This study aims to develop a concrete occupancy prediction as well as an optimal occupancy-based control solution for improving the efficiency of Heating, Ventilation, and Air-Conditioning (HVAC) systems. Accurate occupancy prediction is a key enabler for demand-based HVAC control so as to ensure HVAC is not run needlessly when when a room/zone is unoccupied. In this paper, we propose simple yet effective algorithms to predict occupancy alongside an algorithm for automatically assigning temperature set-points. Utilizing past occupancy observations, we introduce three different techniques for occupancy prediction. Firstly, we propose an identification-based approach, which identifies the model via Expectation Maximization (EM) algorithm. Secondly, we study a novel finite state automata (FSA) which can be reconstructed by a general systems problem solver (GSPS). Thirdly, we introduce an alternative stochastic model based on uncertain basis functions. The results show that all the proposed occupancy prediction techniques could achieve around 70% accuracy. Then, we have proposed a scheme to adaptively adjust the temperature set-points according to a novel temperature set algorithm with customers’ different discomfort tolerance indexes. By cooperating with the temperature set algorithm, our occupancy-based HVAC control shows 20% energy saving while still maintaining building comfort requirements.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗

Robust Importance Sampling for Bayesian Model Calibration with Spatio-Temporal Data

This paper addresses two challenges in Bayesian calibration: 1) computational speed of existing sampling algorithms, and 2) calibration with spatio-temporal responses. The commonly used Markov Chain Monte Carlo (MCMC) approaches require many sequential model evaluations making the computational expense prohibitive. This paper proposes an efficient sampling algorithm: iterative importance sampling with genetic algorithm (IISGA). While iterative importance sampling enables computational efficiency, the genetic algorithm enables robustness by preventing sample degeneration and avoids getting stuck in multimodal search spaces. An inflated likelihood further enables robustness in high-dimensional parameter spaces by enlarging the target distribution. Spatio-temporal data complicate both surrogate modeling, which is necessary for expensive computational models, and the likelihood estimation. In this work, singular value decomposition is investigated for reducing the high-dimensional field data to a lower-dimensional space prior to Bayesian calibration. Then the likelihood is formulated and Bayesian inference is performed in the lower-dimension, latent space. An illustrative example is provided to demonstrate IISGA relative to existing sampling methods, and then IISGA is employed to calibrate a thermal battery model with 26 uncertain calibration parameters and spatio-temporal response data.

97 MATHEMATICS AND COMPUTING↗

Differentiating the shape of stellarator coils with respect to the plasma boundary

The task of designing the geometry of a set of current-carrying coils that produce the magnetic field required to confine a given plasma equilibrium in stellarators is expressed as a minimization principle, namely that the coils minimize a suitably defined error expressed as a surface integral, which is recognized as the quadratic-flux. A penalty on the coil length is included to avoid pathological solutions. A simple expression for how the quadratic-flux and coil length vary as the coil geometry varies is derived, and an expression describing how this varies with variations in the surface geometry is derived. In conclusion, these expressions allow efficient coil-design algorithms to be implemented, and also enable efficient algorithms for varying the shape of the plasma surface in order to simplify the coil geometry, and a numerical illustration of this is given.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

Addressing quantum’s “fine print” with efficient state preparation and information extraction for quantum algorithms and geologic fracture networks

Abstract Quantum algorithms provide an exponential speedup for solving certain classes of linear systems, including those that model geologic fracture flow. However, this revolutionary gain in efficiency does not come without difficulty. Quantum algorithms require that problems satisfy not only algorithm-specific constraints, but also application-specific ones. Otherwise, the quantum advantage carefully attained through algorithmic ingenuity can be entirely negated. Previous work addressing quantum algorithms for geologic fracture flow has illustrated core algorithmic approaches while incrementally removing assumptions. This work addresses two further requirements for solving geologic fracture flow systems with quantum algorithms: efficient system state preparation and efficient information extraction. Our approach to addressing each is consistent with an overall exponential speed-up.

58 GEOSCIENCES↗

Discovery of a metastable Al{sub 20}Sm{sub 4} phase

We present an efficient genetic algorithm, integrated with experimental diffraction data, to solve a nanoscale metastable Al{sub 20}Sm{sub 4} phase that evolves during crystallization of an amorphous magnetron sputtered Al{sub 90}Sm{sub 10} alloy. The excellent match between calculated and experimental X-ray diffraction patterns confirms an accurate description of this metastable phase. Molecular dynamic simulations of crystal growth from the liquid phase predict the formation of disordered defects in the devitrified crystal.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗

Multiparticle cumulant mapping for Coulomb explosion imaging: Calculations and algorithm

We present a versatile cumulant mapping algorithm for analyzing correlated particle emission, offering insights into complex electronic and nuclear dynamics. Recently, we have demonstrated the use of cumulant mapping to extract information-rich correlations between the momenta of multiple fragments produced in Coulomb explosion imaging experiments [C. Cheng et al., Phys. Rev. Lett. 130, 093001 (2023)]. We define cumulant mapping in terms of histograms, enabling fast computation of linear (additive) observables. However, applying the same algorithm to nonlinear (nonadditive) observables poses challenges, as the computation time of conventional estimators scales nonlinearly with data size. To overcome this, we develop estimators and an accompanying algorithm to enable computationally efficient estimation of the cumulant of interest. Comparisons of computation times and signal-to-noise ratios reveal the superior performance of our approach. This method is demonstrated on the (D+, D+, C+, O+) dissociation channel of CD 2 ⁢O 4+ produced in a strong-field ionization experiment. Additionally, Poisson statistics are used to simulate the two methods and provide insights into the efficiency of our algorithm. The proposed methodology unlocks efficient computation of cumulant mapping for a broader range of complex systems and observables, such as the laser pulse dependence of ionization dynamics.

74 ATOMIC AND MOLECULAR PHYSICS↗