Search NASA⌕ Search

SEARCH · Search NASA

Results for “COMPUTING PROBLEMS”

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 163 records · Page 9

Analysis of a Computational Framework for Bayesian Inverse Problems: Ensemble Kalman Updates and MAP Estimators under Mesh Refinement

This paper analyzes a popular computational framework to solve infinite-dimensional Bayesian inverse problems, discretizing the prior and the forward model in a finite-dimensional weighted inner product space. We demonstrate the benefit of working on a weighted space by establishing operator-norm bounds for finite element and graph-based discretizations of Matérn-type priors and deconvolution forward models. For linear-Gaussian inverse problems, we develop a general theory to characterize the error in the approximation to the posterior. We also embed the computational framework into ensemble Kalman methods and MAP estimators for nonlinear inverse problems. Furthermore, our operator-norm bounds for prior discretizations guarantee the scalability and accuracy of these algorithms under mesh refinement.

Bayesian inverse problem↗

Parallel Time Integration for Constrained Optimization

The number of transistors in an average processor continues to increase, but individual clock speeds have plateaued. Those transistors are instead going into additional cores, increasing the number of different things that a processor can do at once and placing an emphasis on parallel computation. Many problems in scientific computing follow a time-evolution model, and it can be difficult to solve such problems in parallel across the temporal domain. The Multi-Grid Reduction In Time (MGRIT) algorithm, developed at Lawrence Livermore National Laboratory (LLNL), solves differential equations with a method designed specifically to take advantage of extreme numbers of processors by parallelizing across time. The Tri-diagonal MGRIT (TriMGRIT) algorithm, also developed at LLNL, is a generalization of MGRIT which enables parallel-in-time solving of a greater number of problems. Constrained optimization problems, in particular, may be solved in parallel using TriMGRIT. These consist of choosing a control function such that an objective functional is minimized, constrained by a differential-equation. We consider two such problems: applying torque to a pendulum to bring it to a gentle stop and moving a crowd of people from one distribution into another. We also perform some miscellaneous theoretical and practical research, including investigating the use of a line-search subroutine to refine intermediate TriMGRIT results and preliminary work on strategies for choosing operators for TriMGRIT to use.

97 MATHEMATICS AND COMPUTING↗

Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems

Quantum computing is a computational paradigm with the potential to outperform classical methods for a variety of problems. Proposed recently, the Quantum Approximate Optimization Algorithm (QAOA) is considered as one of the leading candidates for demonstrating quantum advantage in the near term. QAOA is a variational hybrid quantum-classical algorithm for approximately solving combinatorial optimization problems. The quality of the solution obtained by QAOA for a given problem instance depends on the performance of the classical optimizer used to optimize the variational parameters. In this paper, we formulate the problem of finding optimal QAOA parameters as a learning task in which the knowledge gained from solving training instances can be leveraged to find high-quality solutions for unseen test instances. To this end, we develop two machine-learning-based approaches. Our first approach adopts a reinforcement learning (RL) framework to learn a policy network to optimize QAOA circuits. Our second approach adopts a kernel density estimation (KDE) technique to learn a generative model of optimal QAOA parameters. In both approaches, the training procedure is performed on small-sized problem instances that can be simulated on a classical computer; yet the learned RL policy and the generative model can be used to efficiently solve larger problems. Furthermore, extensive simulations using the IBM Qiskit Aer quantum circuit simulator demonstrate that our proposed RL- and KDE-based approaches reduce the optimality gap by factors up to 30.15 when compared with other commonly used off-the-shelf optimizers.

97 MATHEMATICS AND COMPUTING↗

Efficiently embedding QUBO problems on adiabatic quantum computers

Adiabatic quantum computers like the D-Wave 2000Q can approximately solve the QUBO problem, which is an NP-hard problem, and have been shown to outperform classical computers on several instances. Solving the QUBO problem literally means solving virtually any NP-hard problem like the traveling salesman problem, airline scheduling problem, protein folding problem, genotype imputation problem, thereby enabling significant scientific progress, and potentially saving millions/billions of dollars in logistics, airlines, healthcare and many other industries. Yet, before QUBO problems are solved on quantum computers, they must be embedded (or compiled) onto the hardware of quantum computers, which in itself is a very hard problem. Here, we propose an efficient embedding algorithm, that lets us embed QUBO problems fast, uses less qubits and gets the objective function value close to the global minimum value. We then compare the performance of our embedding algorithm to that of D-Wave’s embedding algorithm, which is the current state of the art, and show that our embedding algorithm convincingly outperforms D-Wave’s embedding algorithm. Our embedding approach works with perfect Chimera graphs, i.e., Chimera graphs with no missing qubits.

97 MATHEMATICS AND COMPUTING↗

Noise Decoherence and Errors from Entanglement-function Theory for Quantum Computing

A significant problem in quantum computing is the development of physical realizations of algorithms that are robust against noise. One way to examine and mitigate noise would be to simulate large sets of qubits coupling to the external environment on classical computers. This is extremely challenging as quantum information processing is in some sense tied to computing resources that scale exponentially with the number of computing elements (qubits). In this LDRD, we set the foundation for a computational framework potentially allowing simulations of 1000s of qubits vs. 10s now possible. Exact wave-function-based methods demand exponentially increasing resources with system size. The method proposed, entanglement-functional theory (EFT), requires vastly fewer resources. The crucial step is to map the information contained in the wave-functions into a simpler object with associated 1.) auxiliary gate operations and 2.) entanglement functionals of this object. This is similar to the Time-dependent Density Functional Theory (TDDFT) approach that has revolutionized chemistry and materials science. Instead of dealing with the exponentially large wave-function, EFT works with a polynomially large set of projections (the density) that are easily manipulated through unitary operations. For a given set of quantum gates, an isomorphism exists that relates the sequence of events to the time-dependent density. A system of entangled qubits can be simulated at drastically reduced cost relative to existing state-of-the-art vector-state simulation codes.

97 MATHEMATICS AND COMPUTING↗

An autoencoder compression approach for accelerating large-scale inverse problems

Abstract Partial differential equation (PDE)-constrained inverse problems are some of the most challenging and computationally demanding problems in computational science today. Fine meshes required to accurately compute the PDE solution introduce an enormous number of parameters and require large-scale computing resources such as more processors and more memory to solve such systems in a reasonable time. For inverse problems constrained by time-dependent PDEs, the adjoint method often employed to compute gradients and higher order derivatives efficiently requires solving a time-reversed, so-called adjoint PDE that depends on the forward PDE solution at each timestep. This necessitates the storage of a high-dimensional forward solution vector at every timestep. Such a procedure quickly exhausts the available memory resources. Several approaches that trade additional computation for reduced memory footprint have been proposed to mitigate the memory bottleneck, including checkpointing and compression strategies. In this work, we propose a close-to-ideal scalable compression approach using autoencoders to eliminate the need for checkpointing and substantial memory storage, thereby reducing the time-to-solution and memory requirements. We compare our approach with checkpointing and an off-the-shelf compression approach on an earth-scale ill-posed seismic inverse problem. The results verify the expected close-to-ideal speedup for the gradient and Hessian-vector product using the proposed autoencoder compression approach. To highlight the usefulness of the proposed approach, we combine the autoencoder compression with the data-informed active subspace (DIAS) prior showing how the DIAS method can be affordably extended to large-scale problems without the need for checkpointing and large memory.

Mathematics↗

A spectral-Lagrangian Boltzmann solver for a multi-energy level gas

In this paper a spectral-Lagrangian method is proposed for the full, non-linear Boltzmann equation for a multi-energy level gas typical of a hypersonic re-entry flow. Internal energy levels are treated as separate species and inelastic collisions (leading to internal energy excitation and relaxation) are accounted for. The formulation developed can also be used for the case of a gas mixture made of monatomic gases without internal energy (where only elastic collisions occur). The advantage of the spectral-Lagrangian method lies in the generality of the algorithm in use for the evaluation of the elastic and inelastic collision operators, as well as the conservation of mass, momentum and energy during collisions. The latter is realized through the solution of constrained optimization problems. The computational procedure is based on the Fourier transform of the partial elastic and inelastic collision operators and exploits the fact that these can be written as weighted convolutions in Fourier space with no restriction on the cross-section model. The feasibility of the proposed approach is demonstrated through numerical examples for both space homogeneous and in-homogeneous problems. Computational results are compared with those obtained by means of the DSMC method in order to assess the accuracy of the proposed spectral-Lagrangian method.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

A Study of Complex Deep Learning Networks on High Performance, Neuromorphic, and Quantum Computers

Current Deep Learning models use highly optimized convolutional neural networks (CNN) trained on large graphical processing units (GPU)-based computers with a fairly simple layered network topology, i.e., highly connected layers, without intra-layer connections. Complex topologies have been proposed, but are intractable to train on current systems. Building the topologies of the deep learning network requires hand tuning, and implementing the network in hardware is expensive in both cost and power.In this paper, we evaluate deep learning models using three different computing architectures to address these problems: quantum computing to train complex topologies, high performance computing (HPC) to automatically determine network topology, and neuromorphic computing for a low-power hardware implementation. Due to input size limitations of current quantum computers we use the MNIST dataset for our evaluation.The results show the possibility of using the three architectures in tandem to explore complex deep learning networks that are untrainable using a von Neumann architecture. We show that a quantum computer can find high quality values of intra-layer connections and weights, while yielding a tractable time result as the complexity of the network increases; a high performance computer can find optimal layer-based topologies; and a neuromorphic computer can represent the complex topology and weights derived from the other architectures in low power memristive hardware.This represents a new capability that is not feasible with current von Neumann architecture. It potentially enables the ability to solve very complicated problems unsolvable with current computing technologies.

97 MATHEMATICS AND COMPUTING↗

A Study of Complex Deep Learning Networks on High Performance, Neuromorphic, and Quantum Computers

Current Deep Learning models use highly optimized convolutional neural networks (CNN) trained on large graphical processing units (GPU)-based computers with a fairly simple layered network topology, i.e., highly connected layers, without intra-layer connections. Complex topologies have been proposed, but are intractable to train on current systems. Building the topologies of the deep learning network requires hand tuning, and implementing the network in hardware is expensive in both cost and power. In this paper, we evaluate deep learning models using three different computing architectures to address these problems: quantum computing to train complex topologies, high performance computing (HPC) to automatically determine network topology, and neuromorphic computing for a low-power hardware implementation. Due to input size limitations of current quantum computers we use the MNIST dataset for our evaluation. The results show the possibility of using the three architectures in tandem to explore complex deep learning networks that are untrainable using a von Neumann architecture. We show that a quantum computer can find high quality values of intra-layer connections and weights, while yielding a tractable time result as the complexity of the network increases; a high performance computer can find optimal layer-based topologies; and a neuromorphic computer can represent the complex topology and weights derived from the other architectures in low power memristive hardware. This represents a new capability that is not feasible with current von Neumann architecture. It potentially enables the ability to solve very complicated problems unsolvable with current computing technologies.

Potok, Thomas E↗

A Conceptual Architecture for a Quantum-HPC Middleware

Abstract-Quantum computing promises potential for science and industry by solving certain computationally complex problems faster than classical computers. Quantum computing systems evolved from coupled to classical computing nodes (HPC). With the increasing monolithic systems towards modular architectures comprising multiple quantum processing units (QPUs) scale, middleware systems that facilitate the efficient coupling of quantum-classical computing are becoming critical. Through an in-depth analysis of quantum applications, integration patterns and systems, we identified a gap in understanding Quantum HPC middleware systems. We present a conceptual middleware to facilitate reasoning about quantum-classical integration and serve as the basis for a future middleware system. An essential contribution of this paper lies in leveraging well-established high performance computing abstractions for managing workloads, tasks, and resources to integrate quantum computing into HPC systems seamlessly

97 MATHEMATICS AND COMPUTING↗

Multi-Group Transport Methods for High-Resolution Neutron Activation Analysis

The accurate and efficient simulation of coupled neutron-photon problems is necessary for several important radiation detection applications. Examples include the detection of nuclear threats concealed in cargo containers and prompt gamma neutron activation analysis for nondestructive determination of elemental composition of unknown samples. In these applications, high-resolution gamma-ray spectrometers are used to measure the spectrum of the emitted photon flux, which consists of both continuum and characteristic gamma rays with discrete energies. Monte Carlo transport is the most commonly used simulation tool for this type of problem, but computational times for many problems can be prohibitively long. This work explores the use of multi-group deterministic methods for the simulation of coupled neutron-photon problems.

Gamma Neutron↗

Data Summarization and Inference at Scale

This is the final report for the DOE ASCR grant SC-0022260, Data Summarization and Inference at Scale, PI: Alex Pothen, Purdue University. The goal of the project was to solve data-intensive and compute-intensive problems in the physical sciences, engineering, information science, data science, etc. by designing and implementing new algorithms that could work with a subset of the data. The four subgoals were: (a) The solution of problems where the data is too large to be stored in the memory of a computer. In this streaming model of computation, the data arrives as a stream of elements to the computer, each element is processed as it arrives, and a decision is made to discard the data or to store it; only a small subset of the data proportional to the size of the output solution is stored, and when all the data has been streamed, a solution to the problem is computed from the stored subset. (b) The use of machine learning methods to compute solutions to data-intensive problems. The use of GPUs is critical to obtain high performance on machine learning tasks, but their memory sizes are smaller relative to that of CPUs. For large-scale problems, the data is sampled many times, and small samples are used with repetition, for robustness, to compute solutions to inference tasks. This sampling reduces the memory required to solve the problem, but attention is needed to avoid slow convergence to the solutions, and reduced accuracy of inference. We propose submodular optimization, Large Language Models, and physics-informed neural networks to enable GPU computations here. (c) Modeling and visualization of high-dimensional data using interpretable features. Clinical proteomic data sets from immunology for the detection of cancer and other diseases are temporal and high-dimensional, and algorithms for visualizing these data sets using clinically interpretable features are lacking. We propose methods that compute distances based on the optimal transportation problem and graph edit distances to address this problem. We also propose the use of optimal transport-based distances, spatial statistics, and network structure to classify image data sets, We apply these algorithms to electron micrographs of the peripheral nervous system in the digestive tract. (d) The design of data-intensive algorithms on emerging architectures, specifically, noisy, intermediate-scale quantum (NISQ) devices. Quantum computers offer the possibility of exploring large solution spaces due to the principle of superposition, but current quantum computers are limited by few qubits, short coherence times due to noise, poor interconections among the qubits, etc. We propose the use of the divide and conquer paradigm to solve large-scale problems, wherein collections of small subproblems are solved on the quantum devices, and the solutions to the subproblems are integrated into a solution for the original problem on a classical computer.

97 MATHEMATICS AND COMPUTING↗

Dynamic Ride-Matching for Large-Scale Transportation Systems

Efficient dynamic ride-matching (DRM) in large-scale transportation systems is a key driver in transport simulations to yield answers to challenging problems. Although the DRM problem is simple to solve, it quickly becomes a computationally challenging problem in large-scale transportation system simulations. Therefore, this study thoroughly examines the DRM problem dynamics and proposes an optimization-based solution framework to solve the problem efficiently. To benefit from parallel computing and reduce computational times, the problem’s network is divided into clusters utilizing a commonly used unsupervised machine learning algorithm along with a linear programming model. Then, these sub-problems are solved using another linear program to finalize the ride-matching. At the clustering level, the framework allows users adjusting cluster sizes to balance the trade-off between the computational time savings and the solution quality deviation. A case study in the Chicago Metropolitan Area, U.S., illustrates that the framework can reduce the average computational time by 58% at the cost of increasing the average pick up time by 26% compared with a system optimum, that is, non-clustered, approach. Another case study in a relatively small city, Bloomington, Illinois, U.S., shows that the framework provides quite similar results to the system-optimum approach in approximately 62% less computational time.

33 ADVANCED PROPULSION SYSTEMS↗

Towards Quantum Computing Phase Diagrams of Gauge Theories with Thermal Pure Quantum States

The phase diagram of strong interactions in nature at finite temperature and chemical potential remains largely theoretically unexplored due to inadequacy of Monte-Carlo–based computational techniques in overcoming a sign problem. Quantum computing offers a sign-problem-free approach, but evaluating thermal expectation values is generally resource intensive on quantum computers. To facilitate thermodynamic studies of gauge theories, we propose a generalization of the thermal-pure-quantum-state formulation of statistical mechanics applied to constrained gauge-theory dynamics, and numerically demonstrate that the phase diagram of a simple low-dimensional gauge theory is robustly determined using this approach, including mapping a chiral phase transition in the model at finite temperature and chemical potential. Quantum algorithms, resource requirements, and algorithmic and hardware error analysis are further discussed to motivate future implementations. Thermal pure quantum states, therefore, may present a suitable candidate for efficient thermal simulations of gauge theories in the era of quantum computing.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Parallel Multigrid in Time and Space for Extreme-Scale Computational Science: Chaotic and Hyperbolic Problems

The coming massive parallelism of exascale computing presents a pressing challenge for the many DOE simulations of time-dependent partial differential equations (PDEs), which typically use traditional sequential time stepping methods. Since this traditional approach is inherently serial, it presents a sequential bottleneck when moving to exascale computing, because future performance gains will come through greater concurrency, not faster clock speeds. Thus, the goal of this work is to research parallelism in time, i.e., methods that compute multiple time values simultaneously, not sequentially. The focus will be on hyperbolic and chaotic problems of interest to DOE, with the goal of enabling scalable simulations of time-dependent hyperbolic and chaotic problems on future architectures. The chosen methodology for solving these problems parallel-in-time is multigrid, because multigrid (when it works) is a powerful, optimal, and scalable solver for discretized PDEs. Multigrid is already commonly used in many DOE simulations for scalably and optimally solving space-only PDE problems. The areas of hyperbolic and chaotic problems are chosen because of their relevance to problems of programmatic interest to DOE. However, these problems are also well-known to be difficult for parallelin-time methods, with the most common method, parareal, diverging in many cases. The current stateof-the-art for parallel-in-time at LLNL is the multigrid reduction in time (MGRIT) XBraid package, which also struggles for such problems, while still showing some improvement over parareal. In summary, new methods are needed for an efficient parallel-in-time scheme for hyperbolic and chaotic problems, and this work shall research promising new multigrid methods in this area. In particular, we take inspiration from the Least Squares Shadowing (LSS by Wang) approach for solving chaotic problems. Here, an optimization approach is able to find “well-conditioned” shadow trajectories/solutions to the original “ill-conditioned” chaotic problem. Thus, the new multigrid methods researched here also arise in an optimization context.

97 MATHEMATICS AND COMPUTING↗