Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “computational complexity”

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 199 records · Page 11
All sourcesNASA NTRSDOE OSTI
DOE OSTI2017

Pececillo

Pececillo is a proxy-app for the open source Truchas metal processing code (LA-CC-15-097). It implements many of the physics models used in Truchas: free-surface, incompressible Navier-Stokes fluid dynamics (e.g., water waves); heat transport, material phase change, view factor thermal radiation; species advection-diffusion; quasi-static, elastic/plastic solid mechanics with contact; electomagnetics (Maxwell's equations). The models are simplified versions that retain the fundamental computational complexity of the Truchas models while omitting many non-essential features and modeling capabilities. The purpose is to expose Truchas algorithms in a greatly simplified context where computer science problems related to parallel performance on advanced architectures can be more easily investigated. While Pececillo is capable of performing simulations representative of typical Truchas metal casting, welding, and additive manufacturing simulations, it lacks many of the modeling capabilites needed for real applications.

Carlson, Neil↗
DOE OSTI2015

Real-Time Corrective Switching in Response to Simultaneous Contingencies

The standard optimal power flow (OPF) problem is an economic dispatch (ED) problem combined with transmission constraints, which are based on a static topology. Prior research has demonstrated that cooptimization of generation dispatch and transmission topology results in cost savings. However, the computational complexity associated with topology control (TC) has been a major deterrent to its implementation. The proposed work investigates the application of a heuristic, a greedy algorithm, to improve the computational time for the TC problem while still maintaining the ability to find quality solutions. An expression is derived, which indicates the impact on the objective for a marginal change in the state of a transmission line. This expression is used to generate a priority list with potential candidate lines for switching, which may provide huge improvements to the system. The advantage of this method is that it is a fast heuristic as compared to using mixed integer programming (MIP) to find a solution. The heuristic is tested on real-time applications such as N-1 events, N - m events (m simultaneous contingencies), and cascading events. The proposed algorithm specifically targets cases that lead to load shedding in the system and provides a quick and efficient method to restore the loads by improving the deliverability of reserves via TC. Simulation results on the IEEE 73 bus test system and the IEEE 118 bus test system suggest a significant improvement in the amount of load served to the system with TC as opposed to without TC with minimal time and computation.

Electric power systems↗
DOE OSTI2015

A multilevel stochastic collocation method for SPDEs

We present a multilevel stochastic collocation method that, as do multilevel Monte Carlo methods, uses a hierarchy of spatial approximations to reduce the overall computational complexity when solving partial differential equations with random inputs. For approximation in parameter space, a hierarchy of multi-dimensional interpolants of increasing fidelity are used. Rigorous convergence and computational cost estimates for the new multilevel stochastic collocation method are derived and used to demonstrate its advantages compared to standard single-level stochastic collocation approximations as well as multilevel Monte Carlo methods.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2025

Exact signed distance fields using parallel Fast Sweeping Method

Signed distance fields are often used in multiphysics simulations to track material interfaces. We present a simple methodology based on the fast sweeping method to generate the exact signed distance from triangular meshes and linear paths on Cartesian grids. The methodology propagates the closest primitive to the boundary to the rest of the domain following the characteristics. A local upwind criterion is used to decide between the new and existing closest primitive at each grid point while capturing the correct sign of the global function. The methodology has optimal computational complexity and runs efficiently in distributed-memory architectures. We include 2D and 3D test cases along with a resolution study up to 0.512 trillion zones and 1,000 computer cores. The solution strategy can also be applied to other types of meshes or collections of primitives.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

An Ensemble Approach to Computationally Efficient Radiological Anomaly Detection and Isotope Identification

Radiological source search is a challenging task involving detection and identification of weak sources in a constantly changing radiological background. As of now, many radiological source detection algorithms have been proposed; however, their computational complexity, and hence reliance on power intensive processing units inhibit low-power applications of radiological source search systems. In this work, we introduce the anomaly filter (AF) algorithm; a computationally light, yet effective time-series source detection algorithm based on exponential weighted moving average (EWMA) and Poisson deviance statistics. Then, we demonstrate that the proposed algorithm can be used in ensemble with other more computationally intensive source detection and identification algorithms to achieve both increased detection performance and reduced power consumption. The proposed AF algorithm and the ensemble algorithms were thoroughly benchmarked against several existing source detection and identification algorithms. The results show that the AF algorithm outperforms existing conventional source detection algorithms, and the ensemble approach improves the overall performance of existing source detection and isotope identification algorithms. Furthermore, the AF algorithm and the Non-negative Matrix Factorization approach based source identification (NMF-ID) algorithm were combined and implemented on a singleboard microcontroller and the power consumption was measured. This ensemble algorithm reduced the power consumption of the NMF-ID algorithm almost by a factor of 100, while improving the detection performance of the overall system.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗
DOE OSTI2014

Design of Experiments, Model Calibration and Data Assimilation

This presentation provides an overview of emulation, calibration and experiment design for computer experiments. Emulation refers to building a statistical surrogate from a carefully selected and limited set of model runs to predict unsampled outputs. The standard kriging approach to emulation of complex computer models is presented. Calibration refers to the process of probabilistically constraining uncertain physics/engineering model inputs to be consistent with observed experimental data. An initial probability distribution for these parameters is updated using the experimental information. Markov chain Monte Carlo (MCMC) algorithms are often used to sample the calibrated parameter distribution. Several MCMC algorithms commonly employed in practice are presented, along with a popular diagnostic for evaluating chain behavior. Space-filling approaches to experiment design for selecting model runs to build effective emulators are discussed, including Latin Hypercube Design and extensions based on orthogonal array skeleton designs and imposed symmetry requirements. Optimization criteria that further enforce space-filling, possibly in projections of the input space, are mentioned. Designs to screen for important input variations are summarized and used for variable selection in a nuclear fuels performance application. This is followed by illustration of sequential experiment design strategies for optimization, global prediction, and rare event inference.

22 GENERAL STUDIES OF NUCLEAR REACTORS↗
DOE OSTI2024

A finite difference informed random walker (FDiRW) solver for strongly inhomogeneous diffusion problems

In nature, many complex multi-physics coupling problems exhibit strong diffusivity inhomogeneity. For instance, in the context of radionuclide absorption by porous wasteform materials within a flowing waste stream, the difference of species’ diffusivity in solid and liquid phases spans by 3~8 orders of magnitude. To solve the diffusion equations with strongly inhomogeneous diffusivity, traditional discretization-based methods, such as the Finite Difference Method (FDM), require infinitesimally small time steps (<10 -10 ) as high spatial resolutions are employed in most microstructure evolution processes, leading to prohibitively high computational costs. Here, this work developed an integrated numerical approach (FDiRW: Finite Difference informed Random Walk) to tackle this challenge. The idea is that utilizing the Random Walk concept, the fast diffusion is modeled as a superposition of point source’s solution for a concentration distribution while FDM is used to obtain the point source’s solution at each node. A mesh-coarsening algorithm is developed to generate an exclusive coarse mesh for FDiRW approach to maximize its efficiency. The effectiveness of the coarse mesh-based FDiRW approach is validated by benchmarking Finite Difference solutions. Numerical results demonstrated that FDiRW achieves a remarkable 1000x computational efficiency improvement over FDM while preserving desired accuracy for a medium-sized model of 192 × 192 × 192 grids. Finally, as models scale up, a floating-point operations (PLOPs) analysis of the FDiRW algorithm reveals that its computational complexity grows quadratically in terms of the number of nodes employed in computation.

36 MATERIALS SCIENCE↗
DOE OSTI2023

Benchmarks and results of the two-band Hubbard model from the Gutzwiller conjugate gradient minimization theory

Ground-state properties, such as energies and double occupancies, of a one-dimensional two-band Hubbard model are calculated using a first-principles Gutzwiller conjugate gradient minimization theory. The favorable agreement with the results from the density matrix renormalization group theory demonstrates the accuracy of our method. A rotationally invariant approach is further incorporated into the method to greatly reduce the computational complexity with a speedup of approximately 50 times. Moreover, we investigate the Mott transition between a metal and a Mott insulator by evaluating the charge gap. In conclusion, with greatly reduced computational effort, our method reproduces the phase diagram in reasonable agreement with the density matrix renormalization group theory.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗
DOE OSTI2014

Diverse Power Iteration Embeddings and Its Applications

Abstract—Spectral Embedding is one of the most effective dimension reduction algorithms in data mining. However, its computation complexity has to be mitigated in order to apply it for real-world large scale data analysis. Many researches have been focusing on developing approximate spectral embeddings which are more efficient, but meanwhile far less effective. This paper proposes Diverse Power Iteration Embeddings (DPIE), which not only retains the similar efficiency of power iteration methods but also produces a series of diverse and more effective embedding vectors. We test this novel method by applying it to various data mining applications (e.g. clustering, anomaly detection and feature selection) and evaluating their performance improvements. The experimental results show our proposed DPIE is more effective than popular spectral approximation methods, and obtains the similar quality of classic spectral embedding derived from eigen-decompositions. Moreover it is extremely fast on big data applications. For example in terms of clustering result, DPIE achieves as good as 95% of classic spectral clustering on the complex datasets but 4000+ times faster in limited memory environment.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2017

A fast parallel 3D Poisson solver with longitudinal periodic and transverse open boundary conditions for space-charge simulations

A three-dimensional (3D) Poisson solver with longitudinal periodic and transverse open boundary conditions can have important applications in beam physics of particle accelerators. Here, we present a fast efficient method to solve the Poisson equation using a spectral finite-difference method. This method uses a computational domain that contains the charged particle beam only and has a computational complexity of $O(N_u (logN_{mode}))$, where $N_u$ is the total number of unknowns and $N_{mode}$ is the maximum number of longitudinal or azimuthal modes. This saves both the computational time and the memory usage of using an artificial boundary condition in a large extended computational domain. The new 3D Poisson solver is parallelized using a message passing interface (MPI) on multi-processor computers and shows a reasonable parallel performance up to hundreds of processor cores.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2017

Security and Cloud Outsourcing Framework for Economic Dispatch

The computational complexity and problem sizes of power grid applications have increased significantly with the advent of renewable resources and smart grid technologies. The current paradigm of solving these issues consist of inhouse high performance computing infrastructures, which have drawbacks of high capital expenditures, maintenance, and limited scalability. Cloud computing is an ideal alternative due to its powerful computational capacity, rapid scalability, and high cost-effectiveness. A major challenge, however, remains in that the highly confidential grid data is susceptible for potential cyberattacks when outsourced to the cloud. In this work, a security and cloud outsourcing framework is developed for the Economic Dispatch (ED) linear programming application. As a result, the security framework transforms the ED linear program into a confidentiality-preserving linear program, that masks both the data and problem structure, thus enabling secure outsourcing to the cloud. Results show that for large grid test cases the performance gain and costs outperforms the in-house infrastructure.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2016

SU-F-T-256: 4D IMRT Planning Using An Early Prototype GPU-Enabled Eclipse Workstation

Purpose: True 4D IMRT planning, based on simultaneous spatiotemporal optimization has been shown to significantly improve plan quality in lung radiotherapy. However, the high computational complexity associated with such planning represents a significant barrier to widespread clinical deployment. We introduce an early prototype GPU-enabled Eclipse workstation for inverse planning. To our knowledge, this is the first GPUintegrated Eclipse system demonstrating the potential for clinical translation of GPU computing on a major commercially-available TPS. Methods: The prototype system comprised of four NVIDIA Tesla K80 GPUs, with a maximum processing capability of 8.5 Tflops per K80 card. The system architecture consisted of three key modules: (i) a GPU-based inverse planning module using a highly-parallelizable, swarm intelligence-based global optimization algorithm, (ii) a GPU-based open-source b-spline deformable image registration module, Elastix, and (iii) a CUDA-based data management module. For evaluation, aperture fluence weights in an IMRT plan were optimized over 9 beams,166 apertures and 10 respiratory phases (14940 variables) for a lung cancer case (GTV = 95 cc, right lower lobe, 15 mm cranio-caudal motion). Sensitivity of the planning time and memory expense to parameter variations was quantified. Results: GPU-based inverse planning was significantly accelerated compared to its CPU counterpart (36 vs 488 min, for 10 phases, 10 search agents and 10 iterations). The optimized IMRT plan significantly improved OAR sparing compared to the original internal target volume (ITV)-based clinical plan, while maintaining prescribed tumor coverage. The dose-sparing improvements were: Esophagus Dmax 50%, Heart Dmax 42% and Spinal cord Dmax 25%. Conclusion: Our early prototype system demonstrates that through massive parallelization, computationally intense tasks such as 4D treatment planning can be accomplished in clinically feasible timeframes. With further optimization, such systems are expected to enable the eventual clinical translation of higher-dimensional and complex treatment planning strategies to significantly improve plan quality. This work was partially supported through research funding from National Institutes of Health (R01CA169102) and Varian Medical Systems, Palo Alto, CA, USA.

60 APPLIED LIFE SCIENCES↗
DOE OSTI2023

Comparison of Equilibrium and Nonequilibrium Approaches for Relative Binding Free Energy Predictions

Alchemical relative binding free energy calculations have recently found important applications in drug optimization. A series of congeneric compounds are generated from a preidentified lead compound, and their relative binding affinities to a protein are assessed in order to optimize candidate drugs. While methods based on equilibrium thermodynamics have been extensively studied, an approach based on nonequilibrium methods has recently been reported together with claims of its superiority. However, these claims pay insufficient attention to the basis and reliability of both methods. Here we report a comparative study of the two approaches across a large data set, comprising more than 500 ligand transformations spanning in excess of 300 ligands binding to a set of 14 diverse protein targets. Ensemble methods are essential to quantify the uncertainty in these calculations, not only for the reasons already established in the equilibrium approach but also to ensure that the nonequilibrium calculations reside within their domain of validity. If and only if ensemble methods are applied, we find that the nonequilibrium method can achieve accuracy and precision comparable to those of the equilibrium approach. Compared to the equilibrium method, the nonequilibrium approach can reduce computational costs but introduces higher computational complexity and longer wall clock times. There are, however, cases where the standard length of a nonequilibrium transition is not sufficient, necessitating a complete rerun of the entire set of transitions. This significantly increases the computational cost and proves to be highly inconvenient during large-scale applications. Our findings provide a key set of recommendations that should be adopted for the reliable implementation of nonequilibrium approaches to relative binding free energy calculations in ligand-protein systems.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2024

A hybrid Monte Carlo, discontinuous Galerkin method for linear kinetic transport equations

Here we present a hybrid method for time-dependent particle transport problems that combines Monte Carlo (MC) estimation with deterministic solutions based on discrete ordinates. For spatial discretizations, the MC algorithm computes a piecewise constant solution and the discrete ordinates use bilinear discontinuous finite elements. From the hybridization of the problem, the resulting problem solved by Monte Carlo is scattering free, resulting in a simple, efficient solution procedure. Between time steps, we use a projection approach to “relabel” collided particles as uncollided particles. In conclusion, from a series of standard 2-D Cartesian test problems we observe that our hybrid method has improved accuracy and reduction in computational complexity of approximately an order of magnitude relative to standard discrete ordinates solutions.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2017

Self-learning Monte Carlo method: Continuous-time algorithm

The recently introduced self-learning Monte Carlo method is a general-purpose numerical method that speeds up Monte Carlo simulations by training an effective model to propose uncorrelated configurations in the Markov chain. We implement this method in the framework of a continuous-time Monte Carlo method with an auxiliary field in quantum impurity models. We introduce and train a diagram generating function (DGF) to model the probability distribution of auxiliary field configurations in continuous imaginary time, at all orders of diagrammatic expansion. Furthermore, by using DGF to propose global moves in configuration space, we show that the self-learning continuous-time Monte Carlo method can significantly reduce the computational complexity of the simulation.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2024

Learning Quantum States and Unitaries of Bounded Gate Complexity

While quantum state tomography is notoriously hard, most states hold little interest to practically minded tomographers. Given that states and unitaries appearing in nature are of bounded gate complexity, it is natural to ask if efficient learning becomes possible. In this work, we prove that to learn a state generated by a quantum circuit with G two-qubit gates to a small trace distance, a sample complexity scaling linearly in G is necessary and sufficient. We also prove that the optimal query complexity to learn a unitary generated by G gates to a small average-case error scales linearly in G . While sample-efficient learning can be achieved, we show that under reasonable cryptographic conjectures, the computational complexity for learning states and unitaries of gate complexity G must scale exponentially in G . We illustrate how these results establish fundamental limitations on the expressivity of quantum machine-learning models and provide new perspectives on no-free-lunch theorems in unitary learning. Together, our results answer how the complexity of learning quantum states and unitaries relate to the complexity of creating these states and unitaries. Published by the American Physical Society 2024

Zhao, Haimeng (ORCID:0000000166751489)↗
DOE OSTI2021

Co-Optimization of Velocity and Charge-Depletion for Plug-In Hybrid Electric Vehicles: Accounting for Acceleration and Jerk Constraints

Abstract Recent advances in vehicle connectivity and automation technologies promote advanced control algorithms that co-optimize the longitudinal dynamics and powertrain operation of hybrid electric vehicles. Typically, a sequential optimization with the vehicle dynamics optimized followed by powertrain optimization is adopted to manage a number of complexities such as the inherent mixed-integer nature of the hybrid powertrain, the numerous state and control variables, the differing time scales of vehicle and powertrain subsystems, time-varying state constraints, and large horizon lengths. Instead, we solve the offline optimization problem in a centralize manner assuming exact knowledge of the lead vehicle's position over the entire trip by applying a discrete-time single shooting-based numerical approach, Discrete Mixed-Integer Shooting (DMIS), including a linearly increasing computational complexity to the problem horizon. In particular, the hierarchical problem structure is exploited to decompose the computationally intensive Hamiltonian minimization step into a set of low-dimensional optimizations. DMIS allows us to compute the direct fuel minimization problem including the vehicle and powertrain dynamics in a centralized manner to its full horizon while systematically tuning weighting factors that penalize passenger discomfort. For the first time, this study reveals that practically implemented sequential optimization exhibits similar fuel optimality as co-optimization when a certain level of passenger comfort is required.

Automation & Control Systems↗
DOE OSTI2023

CHGNet as a pretrained universal neural network potential for charge-informed atomistic modelling

Large-scale simulations with complex electron interactions remain one of the greatest challenges for atomistic modelling. Although classical force fields often fail to describe the coupling between electronic states and ionic rearrangements, the more accurate ab initio molecular dynamics suffers from computational complexity that prevents long-time and large-scale simulations, which are essential to study technologically relevant phenomena. Here we present the Crystal Hamiltonian Graph Neural Network (CHGNet), a graph neural network-based machine-learning interatomic potential (MLIP) that models the universal potential energy surface. CHGNet is pretrained on the energies, forces, stresses and magnetic moments from the Materials Project Trajectory Dataset, which consists of over 10 years of density functional theory calculations of more than 1.5 million inorganic structures. The explicit inclusion of magnetic moments enables CHGNet to learn and accurately represent the orbital occupancy of electrons, enhancing its capability to describe both atomic and electronic degrees of freedom. We demonstrate several applications of CHGNet in solid-state materials, including charge-informed molecular dynamics in Li x MnO 2 , the finite temperature phase diagram for Li x FePO 4 and Li diffusion in garnet conductors. We highlight the significance of charge information for capturing appropriate chemistry and provide insights into ionic systems with additional electronic degrees of freedom that cannot be observed by previous MLIPs.

36 MATERIALS SCIENCE↗