Search NASA⌕ Search

SEARCH · Search NASA

Results for “approximate computing”

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 55 records · Page 3

The second-generation Shifted Boundary Method and its numerical analysis

Recently, the Shifted Boundary Method (SBM) was proposed within the class of unfitted (or immersed, or embedded) finite element methods. By reformulating the original boundary value problem over a surrogate (approximate) computational domain, the SBM avoids integration over cut cells and the associated problematic issues regarding numerical stability and matrix conditioning. Accuracy is maintained by modifying the original boundary conditions using Taylor expansions. Hence the name of the method, that shifts the location and values of the boundary conditions. In this article, we present enhanced variational SBM formulations for the Poisson and Stokes problems with improved flexibility and robustness. These simplified variational forms allow to relax some of the assumptions required by the mathematical proofs of stability and convergence of earlier implementations. First, we show that these new SBM implementations can be proved asymptotically stable and convergent even without the rather restrictive assumption that the inner product between the normals to the true and surrogate boundaries is positive. Second, we show that it is not necessary to introduce a stabilization term involving the tangential derivatives of the solution at Dirichlet boundaries, therefore avoiding the calibration of an additional stabilization parameter. Finally, we prove enhanced L 2 -estimates without the cumbersome assumption – of earlier proofs – that the surrogate domain is convex. Instead we rely on a conventional assumption that the boundary of the true domain is smooth, which can also be replaced by requiring convexity of the true domain. The aforementioned improvements open the way to a more general and efficient implementation of the Shifted Boundary Method, particularly in complex three-dimensional geometries. We complement these theoretical developments with numerical experiments in two and three dimensions.

42 ENGINEERING↗

Randomized Sketching Algorithms for Low-Memory Dynamic Optimization

This paper develops a novel limited-memory method to solve dynamic optimization problems. The memory requirements for such problems often present a major obstacle, particularly for problems with PDE constraints such as optimal flow control, full waveform inversion, and optical tomography. In these problems, PDE constraints uniquely determine the state of a physical system for a given control; the goal is to find the value of the control that minimizes an objective. While the control is often low dimensional, the state is typically more expensive to store. This paper suggests using randomized matrix approximation to compress the state as it is generated and shows how to use the compressed state to reliably solve the original dynamic optimization problem. Concretely, the compressed state is used to compute approximate gradients and to apply the Hessian to vectors. The approximation error in these quantities is controlled by the target rank of the sketch. This approximate first- and second-order information can readily be used in any optimization algorithm. As an example, we develop a sketched trust-region method that adaptively chooses the target rank using a posteriori error information and provably converges to a stationary point of the original problem. Numerical experiments with the sketched trust-region method show promising performance on challenging problems such as the optimal control of an advection-reaction-diffusion equation and the optimal control of fluid flow past a cylinder.

97 MATHEMATICS AND COMPUTING↗

Frozen Gaussian series representation of the imaginary time propagator theory and numerical tests

Thawed Gaussian wavepackets have been used in recent years to compute approximations to the thermal density matrix. From a numerical point of view, it is cheaper to employ frozen Gaussian wavepackets. In this paper, we provide the formalism for the computation of thermal densities using frozen Gaussian wavepackets. We show that the exact density may be given in terms of a series, in which the zeroth order term is the frozen Gaussian. A numerical test of the methodology is presented for deep tunneling in the quartic double well potential. In all cases, the series is observed to converge. The convergence of the diagonal density matrix element is much faster than that of the antidiagonal one, suggesting that the methodology should be especially useful for the computation of partition functions. As a by product of this study, we find that the density matrix in configuration space can have more than two saddle points at low temperatures. This has implications for the use of the quantum instanton theory.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Model selection and parameter estimation in tumor growth models using approximate Bayesian computation-ABC

Cancer is one of the most fatal diseases in the world. Governments and researchers from various areas have continuously concentrated efforts to better understand the disease and propose diagnostic and treatment techniques. The use of mathematical models of tumor growth is of great importance for the development of such techniques. Due to the variety of models nowadays available in the literature, the problems of model selection and parameter estimation come into picture, aiming at suitably predicting the patient’s status of the disease. As the available data on dependent variables of existing models might not justify the use of common likelihood functions, approximate Bayesian computation (ABC) becomes a very attractive tool for model selection and model calibration (parameter estimation) in tumor growth models. In the present study, a Monte Carlo approximate Bayesian computation (ABC) algorithm is applied to select among competing models of tumor growth, with and without chemotherapy treatment. Simulated measurements are used in this work. The results obtained show that the algorithm correctly selects the model and estimates the parameters used to generate the simulated measurements.

60 APPLIED LIFE SCIENCES↗

HD-Bind: Encoding of Molecular Structure with Low Precision, Hyperdimensional Binary Representations

Publicly available collections of drug-like molecules have grown to comprise tens of billions of compounds due to advances in combinatorial chemistry. Traditional methods for identifying "hit" molecules from a large collection of potential drug-like candidates have relied on biophysical theory to compute approximations to the Gibbs free energy of the binding interaction between the drug and its protein target. These approaches have the major drawback that they require exceptional computing capabilities for even relatively small collections of molecules. Hyperdimensional Computing (HDC) is a recently-proposed learning paradigm that represents data with high-dimension binary vectors; this allows the use of low-precision binary vector arithmetic to create models of the data that can be learned without the need for the gradient-based optimization required in many conventional machine learning and deep learning methods. This algorithmic simplicity allows for acceleration in hardware that has been previously demonstrated in a range of application areas. We consider existing HDC approaches for molecular property classification and introduce two novel encodings of a commonly-used molecular representation, the extended connectivity fingerprint (ECFP). We show that HDC-based inference methods are as much as 91 times more efficient than traditional machine learning methods, and achieve an acceleration of nearly nine orders of magnitude compared to molecular docking. Our results show that HDC accelerated methods retain competitive accuracy on a number of well-studied tasks such as molecular property predictions using the MoleculeNet dataset, and bind/no-bind activity classification using the DUD-E and LIT-PCBA datasets. Our work thus motivates further investigation into molecular representation learning to develop ultraefficient pre-screening tools.

Jones, William↗

HDBind: encoding of molecular structure with hyperdimensional binary representations

Traditional methods for identifying “hit” molecules from a large collection of potential drug-like candidates rely on biophysical theory to compute approximations to the Gibbs free energy of the binding interaction between the drug and its protein target. These approaches have a significant limitation in that they require exceptional computing capabilities for even relatively small collections of molecules. Increasingly large and complex state-of-the-art deep learning approaches have gained popularity with the promise to improve the productivity of drug design, notorious for its numerous failures. However, as deep learning models increase in their size and complexity, their acceleration at the hardware level becomes more challenging. Hyperdimensional Computing (HDC) has recently gained attention in the computer hardware community due to its algorithmic simplicity relative to deep learning approaches. The HDC learning paradigm, which represents data with high-dimension binary vectors, allows the use of low-precision binary vector arithmetic to create models of the data that can be learned without the need for the gradient-based optimization required in many conventional machine learning and deep learning methods. This algorithmic simplicity allows for acceleration in hardware that has been previously demonstrated in a range of application areas (computer vision, bioinformatics, mass spectrometery, remote sensing, edge devices, etc.). To the best of our knowledge, our work is the first to consider HDC for the task of fast and efficient screening of modern drug-like compound libraries. We also propose the first HDC graph-based encoding methods for molecular data, demonstrating consistent and substantial improvement over previous work. We compare our approaches to alternative approaches on the well-studied MoleculeNet dataset and the recently proposed LIT-PCBA dataset derived from high quality PubChem assays. We demonstrate our methods on multiple target hardware platforms, including Graphics Processing Units (GPUs) and Field Programmable Gate Arrays (FPGAs), showing at least an order of magnitude improvement in energy efficiency versus even our smallest neural network baseline model with a single hidden layer. Our work thus motivates further investigation into molecular representation learning to develop ultra-efficient pre-screening tools. We make our code publicly available at https://github.com/LLNL/hdbind.

59 BASIC BIOLOGICAL SCIENCES↗

Extending the eigCG algorithm to non-symmetric linear systems with multiple right-hand sides

For Hermitian positive definite linear systems and eigenvalue problems, the eigCG algorithm is a memory efficient algorithm that solves the linear system and simultaneously computes some of its eigenvalues. The algorithm is based on the Conjugate-Gradient (CG) algorithm, however, it uses only a window of the vectors generated by the CG algorithm to compute approximate eigenvalues. The number and accuracy of the eigenvectors can be increased by solving more right-hand sides. For Hermitian systems with multiple right-hand sides, the computed eigenvectors can be used to speed up the solution of subsequent systems. The algorithm was tested on Lattice QCD problems by solving the normal equations and was shown to give large speed up factors and to remove the critical slowing down as we approach light quark masses. Here, an extension to the non-symmetric case based on the two-sided Lanczos algorithm is given. The new algorithm is tested on Lattice QCD problems and is shown to give promising results. We also study the removal of the critical slowing down and compare results with those of the eigCG algorithm. We also discuss the case when the system is gamma5-Hermitian.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Scalable implementation of polynomial filtering for density functional theory calculation in PARSEC

In this work, we present an efficient implementation of polynomial filtering methods in PARSEC, a real-space pseudopotential based Kohn–Sham density functional theory solver. The implementation described here improves upon a Chebyshev-filtered subspace iteration algorithm used in the previous version of PARSEC. We present a hybrid polynomial filtering scheme that combines Chebyshev-filtered subspace iteration and a spectrum slicing method that partitions the spectrum into several spectral slices and uses bandpass-filtered subspace iteration to compute approximate eigenpairs within each interior slice simultaneously. We describe a procedure to partition a spectrum and construct polynomial filters. We also discuss a number of practical issues such as the use of appropriate data layouts for carrying out the computation on a two-dimensional process grid and how to achieve good load balance by allocating an appropriate number of process groups to each spectral slice. Numerical examples are presented to demonstrate the effectiveness of the hybrid polynomial filtering method as well as the superior parallel scalability of spectrum slicing in comparison to that of Chebyshev-filtered subspace iteration.

97 MATHEMATICS AND COMPUTING↗

A Faster Parallel Algorithm and Efficient Multithreaded Implementations for Evaluating Betweenness Centrality on Massive Datasets

We present a new lock-free parallel algorithm for computing betweenness centralityof massive small-world networks. With minor changes to the data structures, ouralgorithm also achieves better spatial cache locality compared to previous approaches. Betweenness centrality is a key algorithm kernel in HPCS SSCA#2, a benchmark extensively used to evaluate the performance of emerging high-performance computing architectures for graph-theoretic computations. We design optimized implementations of betweenness centrality and the SSCA#2 benchmark for two hardware multithreaded systems: a Cray XMT system with the Threadstorm processor, and a single-socket Sun multicore server with the UltraSPARC T2 processor. For a small-world network of 134 million vertices and 1.073 billion edges, the 16-processor XMT system and the 8-core Sun Fire T5120 server achieve TEPS scores (an algorithmic performance count for the SSCA#2 benchmark) of 160 million and 90 million respectively, which corresponds to more than a 2X performance improvement over the previous parallel implementations. To better characterize the performance of these multithreaded systems, we correlate the SSCA#2 performance results with data from the memory-intensive STREAM and RandomAccess benchmarks. Finally, we demonstrate the applicability of our implementation to analyze massive real-world datasets by computing approximate betweenness centrality for a large-scale IMDb movie-actor network.

97 MATHEMATICS AND COMPUTING↗

Balanced truncation-rational Krylov methods for model reduction in large scale dynamical systems

In this paper, we consider the balanced truncation method for model reductions in large-scale linear and time-independent dynamical systems with multi-inputs and multi-outputs. The method is based on the solutions of two large coupled Lyapunov matrix equations when the system is stable or on the computation of stabilizing positive and semi-definite solutions of some continuous-time algebraic Riccati equations when the dynamical system is not stable. Using the rational block Arnoldi, we show how to compute approximate solutions to these large Lyapunov or algebraic Riccati equations. The obtained approximate solutions are given in a factored form and used to build the reduced order model. We give some theoretical results and present numerical examples with some benchmark models.

97 MATHEMATICS AND COMPUTING↗

Final Report: Quantification of Uncertainty in Extreme Scale Computations (QUEST)

QUEST (\url{www.quest-scidac.org}) is a SciDAC Institute that is focused on uncertainty quantification (UQ) in large-scale scientific computations. Our goals are to (1) advance the state of the art in UQ mathematics, algorithms, and software; and (2) provide modeling, algorithmic, and general UQ expertise, together with software tools, to other SciDAC projects, thereby enabling and guiding a broad range of UQ activities in their respective contexts. QUEST is a collaboration among six institutions (Sandia National Laboratories, Los Alamos National Laboratory, the University of Southern California, Massachusetts Institute of Technology, the University of Texas at Austin, and Duke University) with a history of joint UQ research. Our vision encompasses all aspects of UQ in leadership-class computing. This includes the well-founded setup of UQ problems; characterization of the input space given available data/information; local and global sensitivity analysis; adaptive dimensionality and order reduction; forward and inverse propagation of uncertainty; handling of application code failures, missing data, and hardware/software fault tolerance; and model inadequacy, comparison, validation, selection, and averaging. The nature of the UQ problem requires the seamless combination of data, models, and information across this landscape in a manner that provides a self-consistent quantification of requisite uncertainties in predictions from computational models. Accordingly, our UQ methods and tools span an interdisciplinary space across applied math, information theory, and statistics. The MIT QUEST effort centers on statistical inference and methods for surrogate or reduced-order modeling. MIT personnel have been responsible for the development of adaptive sampling methods, methods for approximating computationally intensive models, and software for both forward uncertainty propagation and statistical inverse problems. A key software product of the MIT QUEST effort is the MIT Uncertainty Quantification library, called MUQ (\url{muq.mit.edu}).

97 MATHEMATICS AND COMPUTING↗

Estimates of Quantum Tunneling Effects for Hydrogen Diffusion in PuO 2

We detail the estimation of activation energies and quantum nuclear vibrational tunneling effects for hydrogen diffusion in PuO 2 based on Density Functional Theory calculations and a quantum double well approximation. We find that results are relatively insensitive to choice of exchange correlation functional. In addition, the representation of spin in the system and use of an extended Hubbard U correction has only a small effect on hydrogen point defect formation energies when the PuO 2 lattice is held fixed at the experimental density. We then compute approximate activation energies for transitions between hydrogen interstitial sites seeded by a semi-empirical quantum model and determine the quantum tunneling enhancement relative to classical kinetic rates. Our model indicates that diffusion rates in H/PuO 2 systems could be enhanced by more than one order of magnitude at ambient conditions and that these effects persist at high temperature. The method we propose here can be used as a fast screening tool for assessing possible quantum nuclear vibrational effects in any number of condensed phase materials and surfaces, where hydrogen hopping tends to follow well defined minimum energy pathways.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗

OBSERVATIONS AND MODELING OF H{sub 2} FLUORESCENCE WITH PARTIAL FREQUENCY REDISTRIBUTION IN GIANT PLANET ATMOSPHERES

Partial frequency redistribution (PRD), describing the formation of the line profile, has negligible observational effects for optical depths smaller than {approx}10{sup 3}, at the resolving power of most current instruments. However, when the spectral resolution is sufficiently high, PRD modeling becomes essential in interpreting the line shapes and determining the total line fluxes. We demonstrate the effects of PRD on the H{sub 2} line profiles observed at high spectral resolution by the Far-Ultraviolet Spectroscopic Explorer (FUSE) in the atmospheres of Jupiter and Saturn. In these spectra, the asymmetric shapes of the lines in the Lyman (v''-6) progression pumped by the solar Ly{beta} are explained by coherent scattering of the photons in the line wings. We introduce a simple computational approximation to mitigate the numerical difficulties of radiative transfer with PRD and show that it reproduces the exact radiative transfer solution to better than 10%. The lines predicted by our radiative transfer model with PRD, including the H{sub 2} density and temperature distribution as a function of height in the atmosphere, are in agreement with the line profiles observed by FUSE. We discuss the observational consequences of PRD and show that this computational method also allows us to include PRD in modeling the continuum pumped H{sub 2} fluorescence treating about 4000 lines simultaneously.

79 ASTRONOMY AND ASTROPHYSICS↗

Uncertainty Quantification in Scale-Dependent Models of Flow in Porous Media

Equations governing flow and transport in heterogeneous porous media are scale-dependent. We demonstrate that it is possible to identify a support scale $\eta^*$, such that the typically employed approximate formulations of Moment Equations (ME) yield accurate (statistical) moments of a target environmental state variable. Under these circumstances, the ME approach can be used as an alternative to the Monte Carlo (MC) method for Uncertainty Quantification in diverse fields of Earth and environmental sciences. MEs are directly satisfied by the leading moments of the quantities of interest and are defined on the same support scale as the governing stochastic partial differential equations (PDEs). Computable approximations of the otherwise exact MEs can be obtained through perturbation expansion of moments of the state variables in orders of the standard deviation of the random model parameters. As such, their convergence is guaranteed only for the standard deviation smaller than one. Furthermore, we demonstrate our approach in the context of steady-state groundwater flow in a porous medium with a spatially random hydraulic conductivity.

42 ENGINEERING↗

Near-Optimal Performance of Stochastic Model Predictive Control

Here, this article presents a regret analysis for stochastic model predictive control (SMPC) in linear systems with quadratic performance index and additive and multiplicative uncertainties. Under a finite support assumption, the problem can be cast as a finite-dimensional quadratic program, but the problem becomes quickly intractable as the problem size grows exponentially in the horizon length. SMPC aims to compute approximate solutions by solving a sequence of problems with truncated prediction horizons and committing the solution in a receding-horizon fashion. Although this approach is widely used in practice, its performance relative to the optimal solution is not well understood. This article reports for the first time a rigorous near-optimal performance guarantee of SMPC: under stabilizability and detectability conditions, the regret of SMPC is exponentially small in the prediction horizon length, allowing SMPC to achieve near-optimal performance at a substantially reduced computational expense.

93E20, 93B45↗

Infinite quantum signal processing

Quantum signal processing (QSP) represents a real scalar polynomial of degree d using a product of unitary matrices of size 2 × 2 , parameterized by ( d + 1 ) real numbers called the phase factors. This innovative representation of polynomials has a wide range of applications in quantum computation. When the polynomial of interest is obtained by truncating an infinite polynomial series, a natural question is whether the phase factors have a well defined limit as the degree d → ∞ . While the phase factors are generally not unique, we find that there exists a consistent choice of parameterization so that the limit is well defined in the ℓ 1 space. This generalization of QSP, called the infinite quantum signal processing, can be used to represent a large class of non-polynomial functions. Our analysis reveals a surprising connection between the regularity of the target function and the decay properties of the phase factors. Our analysis also inspires a very simple and efficient algorithm to approximately compute the phase factors in the ℓ 1 space. The algorithm uses only double precision arithmetic operations, and provably converges when the ℓ 1 norm of the Chebyshev coefficients of the target function is upper bounded by a constant that is independent of d . This is also the first numerically stable algorithm for finding phase factors with provable performance guarantees in the limit d → ∞ .

Dong, Yulong [Department of Mathematics, Universit↗

Efficient quantum trajectory representation of wavefunctions evolving in imaginary time

The Boltzmann evolution of a wavefunction can be recast as imaginary-time dynamics of the quantum trajectory ensemble. The quantum effects arise from the momentum-dependent quantum potential - computed approximately to be practical in high-dimensional systems - influencing the trajectories in addition to the external classical potential [S. Garashchuk, J. Chem. Phys. 132, 014112 (2010)]. For a nodeless wavefunction represented as {psi}(x, t) = exp ( -S(x, t)/({Dirac_h}/2{pi})) with the trajectory momenta defined by {nabla}S(x, t), analysis of the Lagrangian and Eulerian evolution shows that for bound potentials the former is more accurate while the latter is more practical because the Lagrangian quantum trajectories diverge with time. Introduction of stationary and time-dependent components into the wavefunction representation generates new Lagrangian-type dynamics where the trajectory spreading is controlled improving efficiency of the trajectory description. As an illustration, different types of dynamics are used to compute zero-point energy of a strongly anharmonic well and low-lying eigenstates of a high-dimensional coupled harmonic system.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

MCNPs Easy Sources for (α,n) (MESA):Verification with Sources4c

MESA is intended to be a direct re-implementation of the algorithms documented in the Sources manual in C++. However, some fundamental changes to the computational structure and logic were made to avoid the use of goto, require consistency in input definition, and reduce computational approximations in later steps of three-layer problems. In addition, MESA uses α-decay information from ISC libraries (based on ENDF). In most cases, differences between Sources4c and MESA are dominated by differences in decay energy spectra and intensities. To verify this we have reproduced 6 problems that are documented examples or samples in Sources4c. These problems cover the three types of problems MESA currently supports: homogeneous, interface, and three-layer.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗