Search NASA⌕ Search

SEARCH · Search NASA

Results for “numerical algorithm 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 451 records · Page 25
All sourcesNASA NTRSDOE OSTI
DOE OSTI2022

Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle

Recent work shows that quantum signal processing (QSP) and its multi-qubit lifted version, quantum singular value transformation (QSVT), unify and improve the presentation of most quantum algorithms. QSP/QSVT characterize the ability, by alternating ansätze, to obliviously transform the singular values of subsystems of unitary matrices by polynomial functions; these algorithms are numerically stable and analytically well-understood. That said, QSP/QSVT require consistent access to a single oracle, saying nothing about computing joint properties of two or more oracles; these can be far cheaper to determine given an ability to pit oracles against one another coherently. This work introduces a corresponding theory of QSP over multiple variables: M-QSP. Surprisingly, despite the non-existence of the fundamental theorem of algebra for multivariable polynomials, there exist necessary and sufficient conditions under which a desired stable multivariable polynomial transformation is possible. Moreover, the classical subroutines used by QSP protocols survive in the multivariable setting for non-obvious reasons, and remain numerically stable and efficient. Up to a well-defined conjecture, we give proof that the family of achievable multivariable transforms is as loosely constrained as could be expected. The unique ability of M-QSP to obliviously approximate joint functions of multiple variables coherently leads to novel speedups incommensurate with those of other quantum algorithms, and provides a bridge from quantum algorithms to algebraic geometry.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2012

Collaborative Research: Continuous Dynamic Grid Adaptation in a Global Atmospheric Model - Application and Refinement

This project had goals of advancing the performance capabilities of the numerical general circulation model EULAG and using it to produce a fully operational atmospheric global climate model (AGCM) that can employ either static or dynamic grid stretching for targeted phenomena. The resulting AGCM combined EULAG's advanced dynamics core with the "physics" of the NCAR Community Atmospheric Model (CAM). Effort discussed below shows how we improved model performance and tested both EULAG and the coupled CAM-EULAG in several ways to demonstrate the grid stretching and ability to simulate very well a wide range of scales, that is, multi-scale capability. We leveraged our effort through interaction with an international EULAG community that has collectively developed new features and applications of EULAG, which we exploited for our own work summarized here. Overall, the work contributed to over 40 peer-reviewed publications and over 70 conference/workshop/seminar presentations, many of them invited. 3a. EULAG Advances EULAG is a non-hydrostatic, parallel computational model for all-scale geophysical flows. EULAG's name derives from its two computational options: EULerian (flux form) or semi-LAGrangian (advective form). The model combines nonoscillatory forward-in-time (NFT) numerical algorithms with a robust elliptic Krylov solver. A signature feature of EULAG is that it is formulated in generalized time-dependent curvilinear coordinates. In particular, this enables grid adaptivity. In total, these features give EULAG novel advantages over many existing dynamical cores. For EULAG itself, numerical advances included refining boundary conditions and filters for optimizing model performance in polar regions. We also added flexibility to the model's underlying formulation, allowing it to work with the pseudo-compressible equation set of Durran in addition to EULAG's standard anelastic formulation. Work in collaboration with others also extended the demonstrated range of validity of soundproof models, showing that they are more broadly applicable than some had previously thought. Substantial testing of EULAG included application and extension of the Jablonowski-Williamson baroclinic wave test - an archetype of planetary weather - and further analysis of multi-scale interactions arising from collapse of temperature fronts in both the baroclinic wave test and simulations of the Held-Suarez idealized climate. These analyses revealed properties of atmospheric gravity waves not seen in previous work and further demonstrated the ability of EULAG to simulate realistic behavior over several orders of magnitude of length scales. Additional collaborative work enhanced capability for modeling atmospheric flows with adaptive moving meshes and demonstrated the ability of EULAG to move into petascale computing. 3b. CAM-EULAG Advances We have developed CAM-EULAG in collaboration with former project postdoc, now University of Cape Town Assistant Professor, Babatunde Abiodun. Initial study documented good model performance in aqua-planet simulations. In particular, we showed that the grid adaptivity (stretching) implemented in CAM-EULAG allows higher resolution in selected regions without causing anomalous behavior such as spurious wave reflection. We then used the stretched-grid version to analyze simulated extreme precipitation events in West Africa, comparing the precipitation and event environment with observed behavior. The model simulates fairly well the spatial scale and the interannual and intraseasonal variability of the extreme events, although its extreme precipitation intensity is weaker than observed. In addition, both observations and the simulations show possible forcing of extreme events by African easterly waves. 3c. Other Contributions Through our collaborations, we have made contributions to a wide range of outcomes. For research focused on terrestrial behavior, these have included (1) upwind schemes for gas dynamics, (2) a nonlinear perspective on the dynamics of the Madden-Julian Oscillation, (3) numerical realism of thermal convection, (4) extreme precipitation processes, (5) unstructured meshes, (6) porous-media analogies for simulating flow in urban environments, (7) Monge-Ampere enhancements of semi-Lagrangian methods and (8) further extensions of the generality of EULAG applications to geophysical problems. The generality of EULAG for multi-scale flow was also demonstrated through solar applications. Simulations of solar magnetohydrodynamics showed that EULAG produces the solar cycle fairly well. Although the model's solar cycle is significantly longer than observed, it shows remarkable agreement with observations in features of spatial evolution. These efforts in environments that are extreme from a geophysical perspective have helped to establish the robustness of EULAG as an all-scale code for geophysical applications.

54 ENVIRONMENTAL SCIENCES↗
DOE OSTI2022

Dual-map framework for noise characterization of quantum computers

In order to understand the capabilities and limitations of quantum computers, it is necessary to develop methods that efficiently characterize and benchmark error channels present on these devices. In this paper, we present a method that faithfully reconstructs a marginal (local) approximation of the effective noise (MATEN) channel, that acts as a single layer at the end of the circuit. We first introduce a dual-map framework that allows us to analytically derive expectation values of observables with respect to noisy circuits. These findings are supported by numerical simulations of the quantum approximate optimization algorithm (QAOA) that also justify the MATEN, even in the presence of nonlocal errors that occur during a circuit. Finally, we demonstrate the performance of the method on Rigetti's Aspen-11 quantum computer for QAOA circuits up to six qubits, successfully predicting the observed measurements on a majority of the qubits.

Sud, James↗
DOE OSTI2019

Component based development of computer-aided tools for different applications

Computer-aided methods and tools are used at different stages of chemical process development. However new tools are needed to meet the current and future challenges through innovative and more sustainable solutions that the currently available tools may not be able to provide. This work focuses on component-based software architecture for development of tailor-made computer-aided tools for specific application objectives. The architecture is based on “components”, which can be model-objects that are stored in a library; collection of property models; databases; numerical solvers; design-algorithms (work-flows) etc. Furthermore, the main idea of these components is to incorporate a plug & play framework, where for a specific purpose, after the work-flow and associated data-flow are established, a specific computer-aided tool can be configured through a library of software components. Also, through the use of software components that are based on predictive model-based solution techniques, the final software can be reliably used to provide innovative and more sustainable solutions over a wide range of problems.

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

A modified iterative method for split problem of variational inclusions and fixed point problems

In this paper, we study a new split problem of variational inclusions and fixed point problems. With the help of averaged mappings, we introduce a new iterative method to solve the stated split problem. Strong convergence results are obtained under mild conditions. Also, we present some preliminary numerical examples to demonstrate the convergence and efficiency of our proposed algorithms.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2019

Relative entropy minimization over Hilbert spaces via Robbins-Monro

One way of getting insight into non-Gaussian measures is to first obtain good Gaussian approximations. These best fit Gaussians can then provide a sense of the mean and variance of the distribution of interest. They can also be used to accelerate sampling algorithms. This begs the question of how one should measure optimality, and how to then obtain this optimal approximation. Here, we consider the problem of minimizing the distance between a family of Gaussians and the target measure with respect to relative entropy, or Kullback-Leibler divergence. As we are interested in applications in the infinite dimensional setting, it is desirable to have convergent algorithms that are well posed on abstract Hilbert spaces. We examine this minimization problem by seeking roots of the first variation of relative entropy, taken with respect to the mean of the Gaussian, leaving the covariance fixed. We prove the convergence of Robbins-Monro type root finding algorithms in this context, highlighting the assumptions necessary for convergence to relative entropy minimizers. Numerical examples are included to illustrate the algorithms.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2015

Efficient Algorithms for Estimating the Absorption Spectrum within Linear Response TDDFT

We present a special symmetric Lanczos algorithm and a kernel polynomial method (KPM) for approximating the absorption spectrum of molecules within the linear response time-dependent density functional theory (TDDFT) framework in the product form. In contrast to existing algorithms, the new algorithms are based on reformulating the original non-Hermitian eigenvalue problem as a product eigenvalue problem and the observation that the product eigenvalue problem is self-adjoint with respect to an appropriately chosen inner product. This allows a simple symmetric Lanczos algorithm to be used to compute the desired absorption spectrum. The use of a symmetric Lanczos algorithm only requires half of the memory compared with the nonsymmetric variant of the Lanczos algorithm. The symmetric Lanczos algorithm is also numerically more stable than the nonsymmetric version. The KPM algorithm is also presented as a low-memory alternative to the Lanczos approach, but the algorithm may require more matrix-vector multiplications in practice. We discuss the pros and cons of these methods in terms of their accuracy as well as their computational and storage cost. Applications to a set of small and medium-sized molecules are also presented.

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

Solving k –SAT problems with generalized quantum measurement

We generalize the projection–based quantum measurement–driven k –SAT algorithm of Benjamin, Zhao, and Fitzsimons to arbitrary strength quantum measurements, including the limit of continuous monitoring. In doing so, we clarify that this algorithm is a particular case of the measurement–driven quantum control strategy elsewhere referred to as “Zeno dragging”. We argue that the algorithm is most efficient with finite time and measurement resources in the continuum limit, where measurements have an infinitesimal strength and duration. Moreover, for solvable k -SAT problems, the dynamics generated by the algorithm converge deterministically towards target dynamics in the long–time (Zeno) limit, implying that the algorithm can successfully operate autonomously via Lindblad dissipation, without detection. We subsequently study both the conditional and unconditional dynamics of the algorithm implemented via generalized measurements, quantifying the advantages of detection for heralding errors. These strategies are investigated first in a computationally–trivial 2-qubit 2-SAT problem to build intuition, and then we consider the scaling of the algorithm on 3-SAT problems encoded with 4–10 qubits. We numerically investigate the scaling of 3-SAT with respect to algorithmic runtime and find that the optimized time to solution scales with qubit number n as λ n , where λ is slightly larger than $\sqrt{2}$ for unconditional dynamics and less than $\sqrt{2}$ for conditional dynamics. We assess the implications for using this analog measurement–driven approach to quantum computing in practice.

quantum information↗
DOE OSTI2015

On the Design, Development, and Analysis of Optimized Matrix-Vector Multiplication Routines for Coprocessors

The manycore paradigm shift, and the resulting change in modern computer architectures, has made the development of optimal numerical routines extremely challenging. In this work, we target the development of numerical algorithms and implementations for Xeon Phi coprocessor architecture designs. In particular, we examine and optimize the general and symmetric matrix-vector multiplication routines (gemv/symv), which are some of the most heavily used linear algebra kernels in many important engineering and physics applications. We describe a successful approach on how to address the challenges for this problem, starting with our algorithm design, performance analysis and programing model and moving to kernel optimization. Our goal, by targeting low-level and easy to understand fundamental kernels, is to develop new optimization strategies that can be effective elsewhere for use on manycore coprocessors, and to show significant performance improvements compared to existing state-of-the-art implementations. Therefore, in addition to the new optimization strategies, analysis, and optimal performance results, we finally present the significance of using these routines/strategies to accelerate higher-level numerical algorithms for the eigenvalue problem (EVP) and the singular value decomposition (SVD) that by themselves are foundational for many important applications.

Kabir, Khairul↗
DOE OSTI2018

Geologic CO 2 sequestration monitoring design: A machine learning and uncertainty quantification based approach

Monitoring is a crucial aspect of geologic carbon dioxide (CO 2 ) sequestration risk management. Effective monitoring is critical to ensure CO 2 is safely and permanently stored throughout the life-cycle of a geologic CO 2 sequestration project. Effective monitoring involves deciding: (i) where is the optimal location to place the monitoring well(s), and (ii) what type of data (pressure, temperature, CO 2 saturation, etc.) should be measured taking into consideration the uncertainties at geologic sequestration sites. We have developed a filtering-based data assimilation procedure to design effective monitoring approaches. To reduce the computational cost of the filtering-based data assimilation process, a machine-learning algorithm: Multivariate Adaptive Regression Splines is used to derive computationally effcient reduced order models from results of full-physics numerical simulations of CO 2 injection in saline aquifer and subsequent multi-phase fluid flow. We use example scenarios of CO 2 leakage through legacy wellbore and demonstrate a monitoring strategy can be selected with the aim of reducing uncertainty in metrics related to CO 2 leakage. We demonstrate the proposed framework with two synthetic examples: a simple validation case and a more complicated case including multiple monitoring wells. The examples demonstrate that the proposed approach can be effective in developing monitoring approaches that take into consideration uncertainties.

58 GEOSCIENCES↗
DOE OSTI2024

On the role of Battery Energy Storage Systems in the day-ahead Contingency-Constrained Unit Commitment problem under renewable penetration

The integration of variable Renewable Energy Sources (vRES) to alleviate greenhouse gas emissions has introduced significant challenges for power systems operations. These challenges include high levels of uncertainty due to the intermittence associated with vRES and therefore impose the need to devise a reliable and cost-effective day-ahead unit commitment and power and reserves scheduling for real-time operations. Also, this increasing penetration of vRES requires higher ramping capabilities from units originally designed for other purposes (e.g., base-load generation), which might be exacerbated during contingency states. Hence, in this work, we propose a methodology to address the day-ahead Contingency-Constrained Unit Commitment (CCUC) problem that leverages the participation of Battery Energy Storage Systems (BESSs) to address load-following and post-contingency management, therefore alleviating the ramping burden on conventional thermal generators. To do so, we formulate a three-level optimization problem that represents the decision-making process of obtaining the least-cost commitment, generation and reserves scheduling, while restricting the Conditional Value-at-Risk (CVaR) of the system imbalance at real-time operations to user-defined tolerance levels. In addition, we devise a computationally efficient solution approach for the proposed problem based on the Column-and Constraint Generation (CCG) algorithmic framework. Two numerical experiments are conducted to empirically illustrate the benefits of the proposed methodology. Key results indicate a reduction in real-time ramping needs and a better usage of the system resources, with a reduction in the overall system commitment levels and reserve scheduling costs when compared to a benchmark case in which storage is not available.

Moreira, Alexandre↗
DOE OSTI2011

Numerical Polynomial Homotopy Continuation Method and String Vacua

Finding vacua for the four-dimensional effective theories for supergravity which descend from flux compactifications and analyzing them according to their stability is one of the central problems in string phenomenology. Except for some simple toy models, it is, however, difficult to find all the vacua analytically. Recently developed algorithmic methods based on symbolic computer algebra can be of great help in the more realistic models. However, they suffer from serious algorithmic complexities and are limited to small system sizes. In this paper, we review a numerical method called the numerical polynomial homotopy continuation (NPHC) method, first used in the areas of lattice field theories, which by construction finds all of the vacua of a given potential that is known to have only isolated solutions. The NPHC method is known to suffer from no major algorithmic complexities and is embarrassingly parallelizable , and hence its applicability goes way beyond the existing symbolic methods. We first solve a simple toy model as a warm-up example to demonstrate the NPHC method at work. We then show that all the vacua of a more complicated model of a compactified M theory model, which has an S U ( 3 ) structure, can be obtained by using a desktop machine in just about an hour, a feat which was reported to be prohibitively difficult by the existing symbolic methods. Finally, we compare the various technicalities between the two methods.

Mehta, Dhagash↗
DOE OSTI2016

Numerically stable, scalable formulas for parallel and online computation of higher-order multivariate central moments with arbitrary weights

Formulas for incremental or parallel computation of second order central moments have long been known, and recent extensions of these formulas to univariate and multivariate moments of arbitrary order have been developed. Such formulas are of key importance in scenarios where incremental results are required and in parallel and distributed systems where communication costs are high. We survey these recent results, and improve them with arbitrary-order, numerically stable one-pass formulas which we further extend with weighted and compound variants. We also develop a generalized correction factor for standard two-pass algorithms that enables the maintenance of accuracy over nearly the full representable range of the input, avoiding the need for extended-precision arithmetic. We then empirically examine algorithm correctness for pairwise update formulas up to order four as well as condition number and relative error bounds for eight different central moment formulas, each up to degree six, to address the trade-offs between numerical accuracy and speed of the various algorithms. Finally, we demonstrate the use of the most elaborate among the above mentioned formulas, with the utilization of the compound moments for a practical large-scale scientific application.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Spectral Mesh-Free Quadrature for Planar Regions Bounded by Rational Parametric Curves

This article presents spectral, mesh-free, Green’s theorem-based numerical quadrature schemes for integrating functions over planar regions bounded by rational parametric curves. Our algorithm proceeds in two steps: (1) We first find intermediate quadrature rules for line integrals along the region’s boundary curves corresponding to Green’s theorem. (2) We then use a high-order quadrature rule to compute the numerical antiderivative of the integrand along a coordinate axis, which is used to evaluate the Green’s theorem line integral. We present two methods to compute the intermediate quadrature rule. The first is spectrally accurate (it converges faster than any algebraic order with respect to number of quadrature points) and is relatively easy to implement, but has no guarantee of polynomial exactness. The second guarantees exactness for polynomial integrands up to a pre-specified degree with an a priori-known number of quadrature points and retains the convergence properties of the first, but is slightly more complicated. The quadrature schemes have applications to computation of geometric moments, immersogeometric analysis, conservative field transfer between high-order meshes, and initialization of multi-material simulations with rational geometry. We compare the quadrature schemes produced using our method to other methods in the literature and show that they are much more efficient both in terms of number of quadrature points and computational time. We provide an open-source implementation of the algorithm in MATLAB.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2017

Prediction-Correction Algorithms for Time-Varying Constrained Optimization

This article develops online algorithms to track solutions of time-varying constrained optimization problems. Particularly, resembling workhorse Kalman filtering-based approaches for dynamical systems, the proposed methods involve prediction-correction steps to provably track the trajectory of the optimal solutions of time-varying convex problems. The merits of existing prediction-correction methods have been shown for unconstrained problems and for setups where computing the inverse of the Hessian of the cost function is computationally affordable. This paper addresses the limitations of existing methods by tackling constrained problems and by designing first-order prediction steps that rely on the Hessian of the cost function (and do not require the computation of its inverse). In addition, the proposed methods are shown to improve the convergence speed of existing prediction-correction methods when applied to unconstrained problems. Numerical simulations corroborate the analytical results and showcase performance and benefits of the proposed algorithms. A realistic application of the proposed method to real-time control of energy resources is presented.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Extracting and Interpreting Electrochemical Impedance Spectra (EIS) from Physics-Based Models of Lithium-Ion Batteries

This paper implements a highly efficient algorithm to extract electrochemical impedance spectra (EIS) from physics-based battery models (e.g., a P2D model). The mathematical approach is different from how EIS is practiced experimentally. Experimentally, the voltage (current) is harmonically perturbed over a wide range of frequencies and the amplitude and phase shift of the corresponding current (voltage) is measured. The experimental approach can be implemented in simulation software, but is computationally expensive. The approach here is to determine locally linear state-space models from the full physical model. The four Jacobian matrices that are the basis of the state-space models can be derived by numerical differentiation of the physical model. The EIS is then extracted from the state-space model using computationally efficient matrix-manipulation techniques. The algorithm can evaluate the full EIS at an instant in time during a transient, independent of whether the battery is in a stationary state. The approach is also able to separate the full-cell impedance to evaluate partial EIS, such as for a battery anode alone. Although such partial EIS is difficult to measure experimentally, the partial EIS provides valuable insights in interpreting the full-cell EIS.

25 ENERGY STORAGE↗
DOE OSTI2015

A general framework of noise suppression in material decomposition for dual-energy CT

Purpose: As a general problem of dual-energy CT (DECT), noise amplification in material decomposition severely reduces the signal-to-noise ratio on the decomposed images compared to that on the original CT images. In this work, the authors propose a general framework of noise suppression in material decomposition for DECT. The method is based on an iterative algorithm recently developed in their group for image-domain decomposition of DECT, with an extension to include nonlinear decomposition models. The generalized framework of iterative DECT decomposition enables beam-hardening correction with simultaneous noise suppression, which improves the clinical benefits of DECT. Methods: The authors propose to suppress noise on the decomposed images of DECT using convex optimization, which is formulated in the form of least-squares estimation with smoothness regularization. Based on the design principles of a best linear unbiased estimator, the authors include the inverse of the estimated variance–covariance matrix of the decomposed images as the penalty weight in the least-squares term. Analytical formulas are derived to compute the variance–covariance matrix for decomposed images with general-form numerical or analytical decomposition. As a demonstration, the authors implement the proposed algorithm on phantom data using an empirical polynomial function of decomposition measured on a calibration scan. The polynomial coefficients are determined from the projection data acquired on a wedge phantom, and the signal decomposition is performed in the projection domain. Results: On the Catphan{sup ®}600 phantom, the proposed noise suppression method reduces the average noise standard deviation of basis material images by one to two orders of magnitude, with a superior performance on spatial resolution as shown in comparisons of line-pair images and modulation transfer function measurements. On the synthesized monoenergetic CT images, the noise standard deviation is reduced by a factor of 2–3. By using nonlinear decomposition on projections, the authors’ method effectively suppresses the streaking artifacts of beam hardening and obtains more uniform images than their previous approach based on a linear model. Similar performance of noise suppression is observed in the results of an anthropomorphic head phantom and a pediatric chest phantom generated by the proposed method. With beam-hardening correction enabled by their approach, the image spatial nonuniformity on the head phantom is reduced from around 10% on the original CT images to 4.9% on the synthesized monoenergetic CT image. On the pediatric chest phantom, their method suppresses image noise standard deviation by a factor of around 7.5, and compared with linear decomposition, it reduces the estimation error of electron densities from 33.3% to 8.6%. Conclusions: The authors propose a general framework of noise suppression in material decomposition for DECT. Phantom studies have shown the proposed method improves the image uniformity and the accuracy of electron density measurements by effective beam-hardening correction and reduces noise level without noticeable resolution loss.

60 APPLIED LIFE SCIENCES↗