SEARCH · Search NASA

Results for “Optimization algorithms”

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

SourceResearch connectionFrom yearThrough year

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

At least 811 records · Page 45

All sources NASA NTRS DOE OSTI

DOE OSTI2026

Classical combinatorial optimization scaling for random Ising models on 2D heavy-hex graphs

Motivated by near term quantum computing hardware limitations, combinatorial optimization problems that can be addressed by current quantum algorithms and noisy hardware with little or no overhead are used to probe capabilities of quantum algorithms such as the quantum approximate optimization algorithm. In this study, a specific class of near term quantum computing hardware defined combinatorial optimization problems, Ising models on heavy-hex graphs both with and without geometrically local cubic terms, are examined for their classical computational hardness via empirical computation time scaling quantification. Specifically the time-to-solution (TTS) metric using the classical heuristic simulated annealing is measured for finding optimal variable assignments (ground states), as well as the time required for the optimization software Gurobi to find an optimal variable assignment. Because of the sparsity of these Ising models, the classical algorithms are able to find optimal solutions efficiently even for large instances (i.e. 100 000 spin variables). The Ising models both with and without geometrically local cubic terms exhibit average-case linear-time or weakly quadratic scaling when solved exactly using Gurobi, and the Ising models with no cubic terms show evidence of exponential-time TTS scaling when sampled using simulated annealing. These findings point to the necessity of developing and testing more complex, namely more densely connected, optimization problems in order for quantum computing to ever have a practical advantage over classical computing. Our results are another illustration that different classical algorithms can indeed have exponentially different running times, thus making the identification of the best practical classical technique important in any quantum computing vs. classical computing comparison.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

DOE OSTI2025

Quantum annealing-assisted lattice optimization

High Entropy Alloys (HEAs) have drawn great interest due to their exceptional properties compared to conventional materials. The configuration of HEA system is considered a key to their superior properties, but exhausting all possible configurations of atom coordinates and species to find the ground energy state is extremely challenging. In this work, we proposed a quantum annealing-assisted lattice optimization (QALO) algorithm, which is an active learning framework that integrates the Field-aware Factorization Machine (FFM) as the surrogate model for lattice energy prediction, Quantum Annealing (QA) as an optimizer and Machine Learning Potential (MLP) for ground truth energy calculation. By applying our algorithm to the NbMoTaW alloy, we reproduced the Nb depletion and W enrichment observed in bulk HEA. We found our optimized HEAs to have superior mechanical properties compared to the randomly generated alloy configurations. Our algorithm highlights the potential of quantum computing in materials design and discovery, laying a foundation for further exploring and optimizing structure-property relationships.

36 MATERIALS SCIENCE↗

DOE OSTI2020

Optimizing High Performance Markov Clustering for Pre-Exascale Architectures

HipMCL is a high-performance distributed memory implementation of the popular Markov Cluster Algorithm (MCL) and can cluster large-scale networks within hours using a few thousand CPU-equipped nodes. It relies on sparse matrix computations and heavily makes use of the sparse matrix-sparse matrix multiplication kernel (SpGEMM). The existing parallel algorithms in HipMCL are not scalable to Exascale architectures, both due to their communication costs dominating the runtime at large concurrencies and also due to their inability to take advantage of accelerators that are increasingly popular. In this work, we systematically remove scalability and performance bottlenecks of HipMCL. We enable GPUs by performing the expensive expansion phase of the MCL algorithm on GPU. Additionally, we propose a CPU-GPU joint distributed SpGEMM algorithm called pipelined Sparse SUMMA and integrate a probabilistic memory requirement estimator that is fast and accurate. Furthermore, we develop a new merging algorithm for the incremental processing of partial results produced by the GPUs, which improves the overlap efficiency and the peak memory usage. We also integrate a recent and faster algorithm for performing SpGEMM on CPUs. We validate our new algorithms and optimizations with extensive evaluations. With the enabling of the GPUs and integration of new algorithms, HipMCL is up to 12.4x faster, being able to cluster a network with 70 million proteins and 68 billion connections just under 15 minutes using 1024 nodes of ORNL's Summit supercomputer.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2025

G-Mapper: Learning a Cover in the Mapper Construction

The Mapper algorithm is a visualization technique in topological data analysis (TDA) that outputs a graph reflecting the structure of a given dataset. However, the Mapper algorithm requires tuning several parameters in order to generate a “nice” Mapper graph. This paper focuses on selecting the cover parameter. We present an algorithm that optimizes the cover of a Mapper graph by splitting a cover repeatedly according to a statistical test for normality. Our algorithm is based on G-means clustering, which searches for the optimal number of clusters in 𝑘-means by iteratively applying the Anderson–Darling test. Our splitting procedure employs a Gaussian mixture model to carefully choose the cover according to the distribution of the given data. In conclusion, experiments for synthetic and real-world datasets demonstrate that our algorithm generates covers so that the Mapper graphs retain the essence of the datasets, while also running significantly faster than a previous iterative method.

G-means clustering↗

DOE OSTI2024

Revenue Analysis of Stationary and Transportable Battery Storage for Power Systems: A Market Participant Perspective

The power system faces a growing need for increased transmission capacity and reliability with the rising integration of renewable energy resources. To tackle this challenge, Battery Energy Storage Systems (BESSs) prove effective in enhancing grid capacity and relieving transmission congestion. This paper focuses on the PJM market, conducting a thorough revenue analysis to identify and characterize highly profitable nodes for BESS market participants. A comparison between stationary and transportable BESSs reveals that the transportable BESSs can generate higher potential revenue in energy and regulation markets. Based on these findings, we propose an optimal placement algorithm to support market participants in selecting strategic sites for BESS installation, validated with real PJM market data. This paper provides valuable insights for navigating market-based power system participants and promoting the effective integration of BESSs.

25 ENERGY STORAGE↗

DOE OSTI2018

Evolutionary computation algorithms to coordinating order acceptance and batch delivery for an integrated supply chain scheduling

This paper proposes a novel approach of coordinating decisions in an integrated supply chain (ISC): coordinating order acceptance (OA) and batch delivery (BD) due to round trip transportation (RTT) and using third-party logistics (3PL) vehicles. The paper aims at trading off among accepted orders revenue, delivery costs as well as any penalties incurred in the ISC to maximize the total benefit. A novel mixed-integer programming is proposed for the problem. In addition, the paper provides a heuristic to form batches and develops a hybrid evolutionary computation algorithms based on particle swarm optimization (PSO) and genetic algorithm (GA) to solve the problem. An information sharing mechanism is improved and applied. To explore and to locate the proposed PSO in a better neighborhood, a local search is proposed. Taguchi experimental design is utilized to set the appropriate values of the algorithms’ parameters and random instances are generated to evaluate the performance of the algorithms. The paper investigates the profitability sensitivity of the problem to parameters and analyzes the effect of the changes in the parameters on the performance of our proposed algorithms. The attained results show the appropriate performance of our algorithms.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2018

Understanding Selection And Diversity For Evolution Of Spiking Recurrent Neural Networks

Evolutionary optimization or genetic algorithms have been used to optimize a variety of neural network types, including spiking recurrent neural networks, and are attractive for many reasons. However, a key impediment to their widespread use is the potential for slow training times and failure to converge to a good fitness value in a reasonable amount of time. In this work, we evaluate the effect of different selection algorithms on the performance of an evolutionary optimization method for designing spiking recurrent neural networks, including those that are meant to be deployed in a neuromorphic system. We propose a selection approach that utilizes a richer understanding of the fitness of an individual network to inform the selection process and to promote diversity in the population. We show that including this feature can provide a significant increase in performance over utilizing a standard selection approach.

Schuman, Catherine↗

DOE OSTI2024

Non-smooth Bayesian optimization in tuning scientific applications

Tuning algorithmic parameters to optimize the performance of large, complicated computational codes is an important problem involving finding the optima and identifying regimes defined by non-smooth boundaries in black-box functions. Within the Bayesian optimization framework, the Gaussian process surrogate model produces smooth mean functions, but functions in the tuning problem are often non-smooth, which is exacerbated by the fact that we usually have limited sequential samples from the black-box function. Here, motivated by these issues encountered in tuning, we propose a novel Gaussian process model called a clustered Gaussian process (cGP), where the components are dynamically updated by clustering. In our studies, the performance of cGP can be better than stationary GPs in nearly 90% of the experiments and better than non-stationary GPs in nearly 70% of the repeated experiments while requiring less computational cost. cGP provides a novel approach for dynamic GP, computes more efficiently than recursive partitioning, and discovers non-smoothness regimes. We provide extensive experiments including high-performance computing (HPC) and industrial simulation functions to show the effectiveness of our methods.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2026

Translation-Invariant Quantum Algorithms for Ordered Search are Optimal

Ordered search is the task of finding an item in an ordered list using comparison queries. The best exact classical algorithm for this fundamental problem uses [log 2 n] queries for a list of length n. Quantum computers can achieve a constant-factor speedup, but the best possible coefficient of log 2 n for exact quantum algorithms is only known to lie between (ln2)/π ≈ 0.221 and 4/log 2 605 ≈ 0.4333. We consider a special class of translation-invariant algorithms with no workspace, introduced by Farhi, Goldstone, Gutmann, and Sipser, that has been used to find the best known upper bounds. First, we show that any bounded-error, k-query quantum algorithm for ordered search can be implemented by a k-query algorithm in this special class. Second, we use linear programming to show that the best exact 5-query quantum algorithm can search a list of length 7265, giving an ordered search algorithm that asymptotically uses 5 log 7265 n ≈ 0.390 log 2 n quantum queries.

Translation-invariant quantum algorithms↗

DOE OSTI2021

A TTL-based Approach for Content Placement in Edge Networks

Edge networks are promising to provide better services to users by provisioning computing and storage resources at the edge of networks. However, due to the uncertainty and diversity of user interests, content popularity, distributed network structure, cache sizes, it is challenging to decide where to place the content, and how long it should be cached. In this paper, we study the utility optimization of content placement at edge networks through timer-based (TTL) policies. We propose provably optimal distributed algorithms that operate at each network cache to maximize the overall network utility. Our TTL-based optimization model provides theoretical answers to how long each content must be cached, and where it should be placed in the edge network. Extensive evaluations show that our algorithm significantly outperforms path replication with conventional caching algorithms over some network topologies.

Panigrahy, Nitish K.↗

DOE OSTI2025

Acceleration of the particle-in-cell code Osiris with graphics processing units

Fully relativistic particle-in-cell (PIC) simulations are crucial for advancing our knowledge of plasma physics. Modern supercomputers based on graphics processing units (GPUs) offer the potential to perform PIC simulations of unprecedented scale, but require robust and feature-rich codes that can fully leverage their computational resources. In this work, this demand is addressed by adding GPU acceleration to the PIC code Osiris. An overview of the algorithm, which features a CUDA extension to the underlying Fortran architecture, is given. Detailed performance benchmarks for thermal plasmas are presented, which demonstrate excellent weak scaling on NERSC's Perlmutter supercomputer and high levels of absolute performance. The robustness of the code to model a variety of physical systems is demonstrated via simulations of Weibel filamentation and laser-wakefield acceleration run with dynamic load balancing. Finally, measurements and analysis of energy consumption are provided that indicate that the GPU algorithm is up to ~14 times faster and ~7 times more energy efficient than the optimized CPU algorithm on a node-to-node basis. The described development addresses the PIC simulation community's computational demands both by contributing a robust and performant GPU-accelerated PIC code and by providing insight into efficient use of GPU hardware.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

DOE OSTI2018

A Machine Learning-Genetic Algorithm (ML-GA) Approach for Rapid Optimization Using High-Performance Computing

A Machine Learning-Genetic Algorithm (ML-GA) approach was developed to virtually discover optimum designs using training data generated from multi-dimensional simulations. Machine learning (ML) presents a pathway to transform complex physical processes that occur in a combustion engine into compact informational processes. In the present work, a total of over 2000 sector-mesh computational fluid dynamics (CFD) simulations of a heavy-duty engine were performed. These were run concurrently on a supercomputer to reduce overall turnaround time. The engine being optimized was run on a low-octane (RON70) gasoline fuel under partially premixed compression ignition (PPCI) mode. A total of nine input parameters were varied, and the CFD simulation cases were generated by randomly sampling points from this nine-dimensional input space. These input parameters included fuel injection strategy, injector design, and various in-cylinder flow and thermodynamic conditions at intake valve closure (IVC). The outputs (targets) of interest from these simulations included five metrics related to engine performance and emissions. Over 2000 samples generated from CFD were then used to train an ML model that could predict these five targets based on the nine input features. A robust super learner approach was employed to build the ML model, where results from a collection of different ML algorithms were pooled together. Thereafter, a stochastic global optimization genetic algorithm (GA) was used, with the ML model as the objective function, to optimize the input parameters based on a merit function so as to minimize fuel consumption while satisfying CO and NOx emissions constraints. The optimized configuration from ML-GA was found to be very close to that obtained from a sequentially performed CFD-GA approach, where a CFD simulation served as the objective function. In addition, the overall turnaround time was (at least) 75% lower with the ML-GA approach, as the training data was generated from concurrent CFD simulations and employing the ML model as the objective function significantly accelerated the GA optimization. Finally, this study demonstrates the potential of ML-GA and high-performance computing (HPC) to reduce the number of CFD simulations to be performed for optimization problems without loss in accuracy, thereby providing significant cost savings compared to traditional approaches.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2022

Multi-objective optimization of root phenotypes for nutrient capture using evolutionary algorithms

Root phenotypes are avenues to the development of crop cultivars with improved nutrient capture, which is an important goal for global agriculture. The fitness landscape of root phenotypes is highly complex and multidimensional. It is difficult to predict which combinations of traits (phene states) will create the best performing integrated phenotypes in various environments. Brute force methods to map the fitness landscape by simulating millions of phenotypes in multiple environments are computationally challenging. Evolutionary optimization algorithms may provide more efficient avenues to explore high dimensional domains such as the root phenotypic space. We coupled the three-dimensional functional–structural plant model, SimRoot, to the Borg Multi-Objective Evolutionary Algorithm (MOEA) and the evolutionary search over several generations facilitated the identification of optimal root phenotypes balancing trade-offs across nutrient uptake, biomass accumulation, and root carbon costs in environments varying in nutrient availability. Our results show that several combinations of root phenes generate optimal integrated phenotypes where performance in one objective comes at the cost of reduced performance in one or more of the remaining objectives, and such combinations differed for mobile and non-mobile nutrients and for maize (a monocot) and bean (a dicot). Functional–structural plant models can be used with multi-objective optimization to identify optimal root phenotypes under various environments, including future climate scenarios, which will be useful in developing the more resilient, efficient crops urgently needed in global agriculture.

59 BASIC BIOLOGICAL SCIENCES↗

DOE OSTI2017

CEED-MS8:Initial Integration of CEED Software in ECP Applications

Key components of CEED software development involve fast finite element operator storage and evaluation, architecture optimizations, performant algorithms for all orders, global kernels for finite element operators, efficient use of the memory sub-system, optimal data locality and motion, enhanced scalability and parallelism, and fast tensor contractions. As ultimate goals of the project, CEED is exploring and identifying the best algorithms for the full range of discretizations and applying algorithmic and software development to support ECP applications’ needs. In this milestone we report on the initial integration of CEED software in the selected first-wave ECP/CEED apps and the continued exploration of other ECP applications as second-wave (milestone CEED-MS23) and third-wave (milestone CEED-MS35) ECP/CEED application candidates. An extensive evaluation of various approaches for GPU acceleration of the CEED computational motives is also a major focus of the report, both in the settings of CEED’s Nekbone and Laghos miniapps, as well as versions of CEED’s bake-off problems (introduced in milestone CEED-MS6). The first-wave ECP applications targeted for coupling with CEED software include the ExaSMR and MARBL applications. We also report on near-term collaboration with the seed-funded Urban Systems project, as well as engagements with ACME, ExaAM, GEOS and the Application Assessment and Proxy App projects. The ExaSMR project involves coupled thermal-hydraulics/neutronics, with the latter based on Monte Carlo methods and the former based on high-order discretizations of the Navier-Stokes and energy equations for accurate simulation of turbulent transport. The project requires fast and efficient turbulence simulation capabilities that will scale to exascale platforms. Work within CEED will ensure that all aspects of the Nek5000 workflow scale to the target problem space, which involves > 10 10 degrees of freedom in typical production runs. CEED’s goal is to provide implementations that perform with maximum attainable efficiency and deliver low turn-around times. A deliverable for this milestone is beta-release of the GPU-based variant of Nek5000. MARBL is targeting high-energy-density physics problems, including single fluid multi-material hydrodynamics and radiation/magnetic diffusion simulation, with applications in inertial confined fusion, pulsed power experiments, and equation of state/material strength analysis. The code uses high-order methods based arbitrary Lagrangian-Eulerian, direct Eulerian, and unstructured adaptive mesh refinement. A deliverable for this milestone is collaboration with MARBL for improved performance based on partially-assembled operators. The Urban exascale project is planning to couple real-time data with high performance simulations to study particulate transport in cities. Nek5000 will be used for large eddy and RANS (Reynolds-averaged Navier-Stokes) simulations of turbulent transport in these domains. Areas where the CEED team is aiding the Urban Canyon group include creating high-order meshes for urban geometries and developing boundary conditions appropriate for simulations close to real-life urban conditions. The software artifacts delivered as part of this milestone include GPU-enabled versions of the Nekbone and Laghos miniapps, which are provided through the CEED website, http://ceed.exascaleproject.org and the CEED GitHub organization, http://github.com/ceed. In addition to details and results from the above R&D efforts, in this document we are also reporting on other project-wide activities performed in Q4 of FY17, including: the CEED first annual meeting and participation of CEED researchers in a variety of outreach activities.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2017

Initial CEED API (CEED-MS10)

Key components of CEED software development involve fast finite element operator storage and evaluation, architecture optimizations, performant algorithms for all orders, global kernels for finite element operators, efficient use of the memory sub-system, optimal data locality and motion, enhanced scalability and parallelism, and fast tensor contractions. As ultimate goals of the project, CEED is exploring and identifying the best algorithms for the full range of discretizations and applying algorithmic and software development to support ECP applications’ needs. In this milestone, we initiated the development and implementation of a common CEED API consisting of two main components: low-level and high-level APIs. We accomplished the goal of having the low-level component ready for the release of CEED v1.0 in the next quarter, see CEED-MS13. In this report we also provide a highlight from CEED’s integration with the MARBL app and the corresponding Laghos miniapp. A main theme in this work has been the systematic transition of advanced algorithms, developed and tested in Laghos, to the large-scale multi-physics settings of the MARBL code. The low-level CEED API provides a set of FE kernels and components for writing new low-level kernels. Examples include: vector and sparse linear algebra, element matrix assembly over a batch of elements, partial assembly and action for efficient high-order operators like mass, diffusion, advection, etc. The main goal of the low-level API is to establish the basis for the high-level API. Also, identifying such low-level kernels and providing a reference implementation for them serves as the basis for collaboration with vendors and STs. Another goal for the low-level API is to make it easy for applications with their own discretization infrastructure, who do not want to switch directly to using the high-level CEED API, to still evaluate and use the core operations provided by the low-level API. One of the challenges with high-order methods is that a global sparse matrix is no longer a good representation of a high-order linear operator, both with respect to the FLOPs needed for its evaluation, as well as the memory transfer needed for a matvec. Thus, another important question we tried to address while developing the low-level API is: is it possible to abstract out in a natural and efficient way the different implementations and data structures that arise when dealing with various computational device types: CPUs, GPUs, etc. Fully answering this question is beyond the scope of this particular milestone, since that requires longer time as we develop and expand the devices we support. The future high-level API will be the frontend provided by CEED consisting of high-level abstractions such as meshes, finite element spaces and solutions, bilinear forms, solvers, etc. At this high-level, an important aspect of the API will be to provide a uniform abstraction layer for writing code in a portable manner. To achieve that, we plan to utilize the MPI programming model combined with a device abstraction layer (DAL) for finite element computations that we will develop. The DAL will serve as the bridge between the low- and the high-level APIs, allowing a variety of programming models to be used for the low-level kernel implementations. The software artifacts delivered as part of this milestone include an initial CEED API software implementation (libCEED) provided through the CEED website, http://ceed.exascaleproject.org and the CEED GitHub organization, http://github.com/ceed. In addition to details and results from the above R&D efforts, in this document we are also reporting on other project-wide activities performed in Q1 of FY18, including: the Nek5000 v17.0 MFEM v3.3.2 and PETSc v3.8 releases, collaborations with ECP/ST and SciDAC projects, the inaugural Nek5000 hackathon and various outreach activities.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2024

Optimization on Manifolds via Graph Gaussian Processes

This paper integrates manifold learning techniques within a Gaussian process upper confidence bound algorithm to optimize an objective function on a manifold. Our approach is motivated by applications where a full representation of the manifold is not available and querying the objective is expensive. We rely on a point cloud of manifold samples to define a graph Gaussian process surrogate model for the objective. Query points are sequentially chosen using the posterior distribution of the surrogate model given all previous queries. We establish regret bounds in terms of the number of queries and the size of the point cloud. Several numerical examples complement the theory and illustrate the performance of our method.

Bayesian optimization↗

DOE OSTI2021

Dakota A Multilevel Parallel Object-Oriented Framework for Design Optimization Parameter Estimation Uncertainty Quantification and Sensitivity Analysis (V.6.14) (Theory Manual)

The Dakota toolkit provides a flexible and extensible interface between simulation codes and iterative analysis methods. Dakota contains algorithms for optimization with gradient and nongradient-based methods; uncertainty quantification with sampling, reliability, and stochastic expansion methods; parameter estimation with nonlinear least squares methods; and sensitivity/variance analysis with design of experiments and parameter study methods. These capabilities may be used on their own or as components within advanced strategies such as surrogate-based optimization, mixed integer nonlinear programming, or optimization under uncertainty. By employing object-oriented design to implement abstractions of the key components required for iterative systems analyses, the Dakota toolkit provides a flexible and extensible problem-solving environment for design and performance analysis of computational models on high performance computers. This report serves as a theoretical manual for selected algorithms implemented within the Dakota software. It is not intended as a comprehensive theoretical treatment, since a number of existing texts cover general optimization theory, statistical analysis, and other introductory topics. Rather, this manual is intended to summarize a set of Dakota-related research publications in the areas of surrogate-based optimization, uncertainty quantification, and optimization under uncertainty that provide the foundation for many of Dakota's iterative analysis capabilities.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2021

Dakota, A Multilevel Parallel Object-Oriented Framework for Design Optimization, Parameter Estimation, Uncertainty Quantification, and Sensitivity Analysis: Theory Manual (V.6.15)

97 MATHEMATICS AND COMPUTING↗