Search NASA⌕ Search

SEARCH · Search NASA

Results for “Computer algorithm”

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

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

At least 1,765 records · Page 98
All sourcesNASA NTRSDOE OSTI
DOE OSTI2018

Quantum-classical computation of Schwinger model dynamics using quantum computers

We present a quantum-classical algorithm to study the dynamics of the two-spatial-site Schwinger model on IBM's quantum computers. Using rotational symmetries, total charge, and parity, the number of qubits needed to perform computation is reduced by a factor of ~5, removing exponentially large unphysical sectors from the Hilbert space. Our work opens an avenue for exploration of other lattice quantum field theories, such as quantum chromodynamics, where classical computation is used to find symmetry sectors in which the quantum computer evaluates the dynamics of quantum fluctuations.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Validating Extreme Scale Resilience with Veracity (Final Project Report)

As semiconductor technology continues to scale to smaller dimensions and as power-consumption of processor chips continues to increase in importance, there is significant uncertainty about the reliability of future large-scale computers. This uncertainty impacts algorithm design and application development, as well as decisions about system operation policy and provisioning decisions. The Veracity endeavored to answer pertinent questions regarding system reliability and resilience with the goal of enabling reliable science on future leadership machines while keeping overprovisioning low.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2015

Efficient traveltime solutions of the acoustic TI eikonal equation

Numerical solutions of the eikonal (Hamilton–Jacobi) equation for transversely isotropic (TI) media are essential for imaging and traveltime tomography applications. Such solutions, however, suffer from the inherent higher-order nonlinearity of the TI eikonal equation, which requires solving a quartic polynomial for every grid point. Analytical solutions of the quartic polynomial yield numerically unstable formulations. Thus, it requires a numerical root finding algorithm, adding significantly to the computational load. Using perturbation theory we approximate, in a first order discretized form, the TI eikonal equation with a series of simpler equations for the coefficients of a polynomial expansion of the eikonal solution, in terms of the anellipticity anisotropy parameter. Such perturbation, applied to the discretized form of the eikonal equation, does not impose any restrictions on the complexity of the perturbed parameter field. Therefore, it provides accurate traveltime solutions even for models with complex distribution of velocity and anisotropic anellipticity parameter, such as that for the complicated Marmousi model. The formulation allows for large cost reduction compared to using the direct TI eikonal solver. Furthermore, comparative tests with previously developed approximations illustrate remarkable gain in accuracy in the proposed algorithm, without any addition to the computational cost.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2015

Modeling Rare Events in High Dimensional Stochastics Systems

The main issue addressed in this note is the study of an algorithm to accelerate the computation of kinetic rates in the context of molecular dynamics(MD). It is based on parallel simulations of short-time trajectories and its main components are: a decomposition of phase space into macrostates or cells, a resampling procedure that ensures that the number of parallel replicas (MD simulations) in each macro-state remains constant, the use of multiple populations (colored replicas) to compute multiple rates (e.g., forward and backward rates) in one simulation. The method leads to enhancing the sampling of macro-states associated to the transition states, since in traditional MD these are likely to be depleted even after short-time simulations. By allowing parallel replicas to carry different probabilistic weights, the number of replicas within each macro-state can be maintained constant without introducing any bias. The empirical variance of the estimated reaction rate, defined as a probability flux, is expectedly diminished. This note is a first attempt towards a better mathematical and numerical understanding of this method. It provides first a mathematical formalization of the notion of colors. Then, the link between this algorithm and a set of closely related methods having been proposed in the literature within the past few years is discussed. Lastly, numerical results are provided that illustrate the efficiency of the method.

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2015

Π4U: A high performance computing framework for Bayesian uncertainty quantification of complex models

We present Π4U,{sup 1} an extensible framework, for non-intrusive Bayesian Uncertainty Quantification and Propagation (UQ+P) of complex and computationally demanding physical models, that can exploit massively parallel computer architectures. The framework incorporates Laplace asymptotic approximations as well as stochastic algorithms, along with distributed numerical differentiation and task-based parallelism for heterogeneous clusters. Sampling is based on the Transitional Markov Chain Monte Carlo (TMCMC) algorithm and its variants. The optimization tasks associated with the asymptotic approximations are treated via the Covariance Matrix Adaptation Evolution Strategy (CMA-ES). A modified subset simulation method is used for posterior reliability measurements of rare events. The framework accommodates scheduling of multiple physical model evaluations based on an adaptive load balancing library and shows excellent scalability. In addition to the software framework, we also provide guidelines as to the applicability and efficiency of Bayesian tools when applied to computationally demanding physical models. Theoretical and computational developments are demonstrated with applications drawn from molecular dynamics, structural dynamics and granular flow.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2021

Peak Reduction in a Residential Community Through Bayesian Optimization of Transactive Control Signals

Daily residential power consumption in aggregate tends to have a large peak that places stress on the distribution system and induces high operational costs. This work shows that coordinated transactive control of noncritical loads within a residential community or microgrid can help to alleviate peak-time stress on the distribution system by flattening the aggregate load curve. Treating the load forecaster as a high-fidelity, expensive black-box function, a new algorithm utilizing Bayesian optimization (BO) is proposed to achieve the best solution under uncertainty with minimal computing effort. The proposed BO algorithm manipulates the shape of the load based on transactive signals sent to each home. The thermostatically controlled loads (TCLs) act out of self-interest in response to the given price while maintaining comfort, and the optimizer exploits the thermal energy retention of the homes for the benefit of the community. Simulations confirm consistent neighborhood-level peak power reduction and energy cost savings.

Schomer, Ian↗
DOE OSTI2023

Review of machine learning and deep learning models for toxicity prediction

The ever-increasing number of chemicals has raised public concerns due to their adverse effects on human health and the environment. To protect public health and the environment, it is critical to assess the toxicity of these chemicals. Traditional in vitro and in vivo toxicity assays are complicated, costly, and time-consuming and may face ethical issues. These constraints raise the need for alternative methods for assessing the toxicity of chemicals. Recently, due to the advancement of machine learning algorithms and the increase in computational power, many toxicity prediction models have been developed using various machine learning and deep learning algorithms such as support vector machine, random forest, k-nearest neighbors, ensemble learning, and deep neural network. This review summarizes the machine learning- and deep learning-based toxicity prediction models developed in recent years. Support vector machine and random forest are the most popular machine learning algorithms, and hepatotoxicity, cardiotoxicity, and carcinogenicity are the frequently modeled toxicity endpoints in predictive toxicology. It is known that datasets impact model performance. The quality of datasets used in the development of toxicity prediction models using machine learning and deep learning is vital to the performance of the developed models. The different toxicity assignments for the same chemicals among different datasets of the same type of toxicity have been observed, indicating benchmarking datasets is needed for developing reliable toxicity prediction models using machine learning and deep learning algorithms. This review provides insights into current machine learning models in predictive toxicology, which are expected to promote the development and application of toxicity prediction models in the future.

Research & Experimental Medicine↗
DOE OSTI2019

Dynamic linear response quantum algorithm

The dynamic linear response of a quantum system is critical for understanding both the structure and dynamics of strongly interacting quantum systems, including neutron scattering from materials, photon and electron scattering from atomic systems, and electron and neutrino scattering by nuclei. Here, we present a general algorithm for universal quantum computers to calculate the dynamic linear response function with controlled errors and to obtain information about specific final states that can be directly compared to experimental observations.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗
DOE OSTI2017

Thermochimica

Thermochimica is a software library that determines a unique combination of phases and their compositions at thermochemical equilibrium. Thermochimica can be used for stand-alone calculations or it can be directly coupled to other codes. This release of the software does not have a graphical user interface (GUI) and it can be executed from the command line or from an Application Programming Interface (API). Also, it is not intended for thermodynamic model development or for constructing phase diagrams. The main purpose of the software is to be directly coupled with a multi-physics code to provide material properties and boundary conditions for various physical phenomena. Significant research efforts have been dedicated to enhance computational performance through advanced algorithm development, such as improved estimation techniques and non-linear solvers. Various useful parameters can be provided as output from Thermochimica, such as: determination of which phases are stable at equilibrium, the mass of solution species and phases at equilibrium, mole fractions of solution phase constituents, thermochemical activities (which are related to partial pressures for gaseous species), chemical potentials of solution species and phases, and integral Gibbs energy (referenced relative to standard state). The overall goal is to provide an open source computational tool to enhance the predictive capability of multi-physics codes without significantly impeding computational performance.

Simunovic, Srdjan↗
DOE OSTI2016

Computing Maximum Cardinality Matchings in Parallel on Bipartite Graphs via Tree-Grafting

It is difficult to obtain high performance when computing matchings on parallel processors because matching algorithms explicitly or implicitly search for paths in the graph, and when these paths become long, there is little concurrency. In spite of this limitation, we present a new algorithm and its shared-memory parallelization that achieves good performance and scalability in computing maximum cardinality matchings in bipartite graphs. This algorithm searches for augmenting paths via specialized breadth-first searches (BFS) from multiple source vertices, hence creating more parallelism than single source algorithms. Algorithms that employ multiple-source searches cannot discard a search tree once no augmenting path is discovered from the tree, unlike algorithms that rely on single-source searches. We describe a novel tree-grafting method that eliminates most of the redundant edge traversals resulting from this property of multiple-source searches. We also employ the recent direction-optimizing BFS algorithm as a subroutine to discover augmenting paths faster. Our algorithm compares favorably with the current best algorithms in terms of the number of edges traversed, the average augmenting path length, and the number of iterations. Here, we provide a proof of correctness for our algorithm. Our NUMA-aware implementation is scalable to 80 threads of an Intel multiprocessor and to 240 threads on an Intel Knights Corner coprocessor. On average, our parallel algorithm runs an order of magnitude faster than the fastest algorithms available. The performance improvement is more significant on graphs with small matching number.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2018

Distributed Louvain Algorithm for Graph Community Detection

In most real-world networks, the nodes/vertices tend to be organized into tightly-knit modules known as communities or clusters, such that nodes within a community are more likely to be “related” to one another than they are to the rest of the network. The goodness of partitioning into communities is typically measured using a well known measure called modularity. However, modularity optimization is an NP-complete problem. In 2008, Blondel, et al. introduced a multi-phase, iterative heuristic for modularity optimization, called the Louvain method. Owing to its speed and ability to yield high quality communities, the Louvain method continues to be one of the most widely used tools for serial community detection. In this paper, we present the design of a distributed memory implementation of the Louvain algorithm for parallel community detection. Our approach begins with an arbitrarily partitioned distributed graph input, and employs several heuristics to speedup the computation of the different steps of the Louvain algorithm. We evaluate our implementation and its different variants using real-world networks from various application domains (including internet, biology, social networks). Our MPI+OpenMP implementation yields about 7x speedup (on 4K processes) for soc-friendster network (1.8B edges) over a state-of-the-art shared-memory multicore implementation (on 64 threads), without compromising output quality. Furthermore, our distributed implementation was able to process a larger graph (uk-2007; 3.3B edges) in 32 seconds on 1K cores (64 nodes) of NERSC Cori, when the state-of-the-art shared-memory implementation failed to run due to insufficient memory on a single Cori node containing 128 GB.

High performance computing, graph algorithms, Dist↗
DOE OSTI2013

Numerical modeling of laser tunneling ionization in explicit particle-in-cell codes

Methods for the calculation of laser tunneling ionization in explicit particle-in-cell codes used for modeling laser–plasma interactions are compared and validated against theoretical predictions. Improved accuracy is obtained by using the direct current form for the ionization rate. Multi level ionization in a single time step and energy conservation have been considered during the ionization process. The effects of grid resolution and number of macro-particles per cell are examined. Implementation of the ionization algorithm in two different particle-in-cell codes is compared for the case of ionization-based electron injection in a laser–plasma accelerator.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2016

Adaptive local learning in sampling based motion planning for protein folding

Background: Simulating protein folding motions is an important problem in computational biology. Motion planning algorithms, such as Probabilistic Roadmap Methods, have been successful in modeling the folding landscape. Probabilistic Roadmap Methods and variants contain several phases (i.e., sampling, connection, and path extraction). Most of the time is spent in the connection phase and selecting which variant to employ is a difficult task. Global machine learning has been applied to the connection phase but is inefficient in situations with varying topology, such as those typical of folding landscapes. Results: We develop a local learning algorithm that exploits the past performance of methods within the neighborhood of the current connection attempts as a basis for learning. It is sensitive not only to different types of landscapes but also to differing regions in the landscape itself, removing the need to explicitly partition the landscape. We perform experiments on 23 proteins of varying secondary structure makeup with 52–114 residues. We compare the success rate when using our methods and other methods. We demonstrate a clear need for learning (i.e., only learning methods were able to validate against all available experimental data) and show that local learning is superior to global learning producing, in many cases, significantly higher quality results than the other methods. Conclusions: We present an algorithm that uses local learning to select appropriate connection methods in the context of roadmap construction for protein folding. Our method removes the burden of deciding which method to use, leverages the strengths of the individual input methods, and it is extendable to include other future connection methods.

Mathematical & Computational Biology↗
DOE OSTI2024

Probabilistic Context Neighborhood model for lattices

Here we present the Probabilistic Context Neighborhood model designed for two-dimensional lattices as a variation of a Markov random field assuming discrete values. In this model, the neighborhood structure has a fixed geometry but a variable order, depending on the neighbors’ values. Our model extends the Probabilistic Context Tree model, originally applicable to one-dimensional space. It retains advantageous properties, such as representing the dependence neighborhood structure as a graph in a tree format, facilitating an understanding of model complexity. Furthermore, we adapt the algorithm used to estimate the Probabilistic Context Tree to estimate the parameters of the proposed model. We illustrate the accuracy of our estimation methodology through simulation studies. Additionally, we apply the Probabilistic Context Neighborhood model to spatial real-world data, showcasing its practical utility.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2017

Unbiased simulation of near-Clifford quantum circuits

Modeling and simulation are essential for predicting and verifying the behavior of fabricated quantum circuits, but existing simulation methods are either impractically costly or require an unrealistic simplification of error processes. In this paper, we present a method of simulating noisy Clifford circuits that is both accurate and practical in experimentally relevant regimes. In particular, the cost is weakly exponential in the size and the degree of non-Cliffordness of the circuit. Our approach is based on the construction of exact representations of quantum channels as quasiprobability distributions over stabilizer operations, which are then sampled, simulated, and weighted to yield unbiased statistical estimates of circuit outputs and other observables. As a demonstration of these techniques, we simulate a Steane [[7,1,3]]-encoded logical operation with non-Clifford errors and compute its fault tolerance error threshold. Finally, we expect that the method presented here will enable studies of much larger and more realistic quantum circuits than was previously possible.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2013

Efficient Screening of Climate Model Sensitivity to a Large Number of Perturbed Input Parameters [plus supporting information]

Modern climate models contain numerous input parameters, each with a range of possible values. Since the volume of parameter space increases exponentially with the number of parameters N, it is generally impossible to directly evaluate a model throughout this space even if just 2-3 values are chosen for each parameter. Sensitivity screening algorithms, however, can identify input parameters having relatively little effect on a variety of output fields, either individually or in nonlinear combination.This can aid both model development and the uncertainty quantification (UQ) process. Here we report results from a parameter sensitivity screening algorithm hitherto untested in climate modeling, the Morris one-at-a-time (MOAT) method. This algorithm drastically reduces the computational cost of estimating sensitivities in a high dimensional parameter space because the sample size grows linearly rather than exponentially with N. It nevertheless samples over much of the N-dimensional volume and allows assessment of parameter interactions, unlike traditional elementary one-at-a-time (EOAT) parameter variation. We applied both EOAT and MOAT to the Community Atmosphere Model (CAM), assessing CAM’s behavior as a function of 27 uncertain input parameters related to the boundary layer, clouds, and other subgrid scale processes. For radiation balance at the top of the atmosphere, EOAT and MOAT rank most input parameters similarly, but MOAT identifies a sensitivity that EOAT underplays for two convection parameters that operate nonlinearly in the model. MOAT’s ranking of input parameters is robust to modest algorithmic variations, and it is qualitatively consistent with model development experience. Supporting information is also provided at the end of the full text of the article.

54 ENVIRONMENTAL SCIENCES↗
DOE OSTI2024

Radiation-Induced Noise Resilience of Neuromorphic Architectures

Neuromorphic event-based networks use asynchronous time-dependent information to extract features from input data that can allow for edge-based distributed applications such as object recognition. The noise resilience properties of such networks, especially in the context of space applications, are yet to be explored. In this paper, we use the hierarchy of time surfaces (HOTS) algorithm, which is one of the neuromorphic algorithms, to understand the least and most resilient modules in a neuromorphic network. The HOTS algorithm relies on the computing of time surfaces that maps the temporal delays between neighboring pixels into normalized features that involve many computations that are also found in other neuromorphic networks such as exponential decays, distance computations, etcetera. We implemented HOTS on a Digilent PYNQ board with a Xilinx Zynq 7020 system on a chip, and we subjected the boards running the HOTS network inference to neutron radiation at the Los Alamos Neutron Science Center. Furthermore, we used simulation models from our previous similar experiments on the event-based sensor to create a neutron induced noise model to quantify the effect of this noise on the overall performance of the network. This experiment provides the preliminary measurements of the reliability of the HOTS algorithm and proposes methods to create a more reliable HOTS architecture in future spacecraft missions.

Engineering↗
DOE OSTI2015

Improving Limit Surface Search Algorithms in RAVEN Using Acceleration Schemes: Level II Milestone

The RAVEN code is becoming a comprehensive tool to perform Probabilistic Risk Assessment (PRA); Uncertainty Quantification (UQ) and Propagation; and Verification and Validation (V&V). The RAVEN code is being developed to support the Risk-Informed Safety Margin Characterization (RISMC) pathway by developing an advanced set of methodologies and algorithms for use in advanced risk analysis. The RISMC approach uses system simulator codes applied to stochastic analysis tools. The fundamental idea behind this coupling approach to perturb (by employing sampling strategies) timing and sequencing of events, internal parameters of the system codes (i.e., uncertain parameters of the physics model) and initial conditions to estimate values ranges and associated probabilities of figures of merit of interest for engineering and safety (e.g. core damage probability, etc.). This approach applied to complex systems such as nuclear power plants requires performing a series of computationally expensive simulation runs. The large computational burden is caused by the large set of (uncertain) parameters characterizing those systems. Consequently, exploring the uncertain/parametric domain, with a good level of confidence, is generally not affordable, considering the limited computational resources that are currently available. In addition, the recent tendency to develop newer tools, characterized by higher accuracy and larger computational resources (if compared with the presently used legacy codes, that have been developed decades ago), has made this issue even more compelling. In order to overcome to these limitations, the strategy for the exploration of the uncertain/parametric space needs to use at best the computational resources focusing the computational effort in those regions of the uncertain/parametric space that are “interesting” (e.g., risk-significant regions of the input space) with respect the targeted Figures Of Merit (FOM): for example, the failure of the system, subject of the analysis. These methodologies are named, in the RAVEN environment, adaptive sampling strategies. These methodologies infer system responses from surrogate models constructed from already existing samples (produced using high fidelity simulations) and suggest the most relevant location (coordinate in the input space) of the next sampling point to be explored in the uncertain/parametric domain. When using those methodologies, it is possible to understand features of the system response with a small number of carefully selected samples. This report focuses on the development and improvement of the limit surface search. The limit surface is an important concept in system reliability analysis. Without going into the details, which will be covered later in the report, the limit surface could be briefly described as an hyper-surface in the system uncertainty/parametric space separating the regions leading to a prescribed system outcome. For example, if the uncertainty/parametric space is the one generated by the reactor power level and the duration of the batteries, the system is a nuclear power plant and the system outcome discriminating variable is the clad failure in a station blackout scenario, then the limit surface separates the combinations of reactor power level and battery duration that lead to clad failure from the ones that do not.

21 SPECIFIC NUCLEAR REACTORS AND ASSOCIATED PLANTS↗