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 1,639 records · Page 91

Running Primal-Dual Gradient Method for Time-Varying Nonconvex Problems

This paper focuses on a time-varying constrained nonconvex optimization problem, and considers the synthesis and analysis of online regularized primal-dual gradient methods to track a Karush-Kuhn-Tucker (KKT) trajectory. The proposed regularized primal-dual gradient method is implemented in a running fashion, in the sense that the underlying optimization problem changes during the execution of the algorithms. In order to study its performance, we first derive its continuous-time limit as a system of differential inclusions. We then study sufficient conditions for tracking a KKT trajectory, and also derive asymptotic bounds for the tracking error (as a function of the time-variability of a KKT trajectory). Further, we provide a set of sufficient conditions for the KKT trajectories not to bifurcate or merge, and also investigate the optimal choice of the parameters of the algorithm. Illustrative numerical results for a time-varying nonconvex problem are provided.

differential inclusion↗

EXAGRAPH: Graph and combinatorial methods for enabling exascale applications

Combinatorial algorithms in general and graph algorithms in particular play a critical enabling role in numerous scientific applications. However, the irregular memory access nature of these algorithms makes them one of the hardest algorithmic kernels to implement on parallel systems. With tens of billions of hardware threads and deep memory hierarchies, the exascale computing systems in particular pose extreme challenges in scaling graph algorithms. The codesign center on combinatorial algorithms, ExaGraph, was established to design and develop methods and techniques for efficient implementation of key combinatorial (graph) algorithms chosen from a diverse set of exascale applications. Algebraic and combinatorial methods have a complementary role in the advancement of computational science and engineering, including playing an enabling role on each other. In this paper, we survey the algorithmic and software development activities performed under the auspices of ExaGraph from both a combinatorial and an algebraic perspective. In particular, we detail our recent efforts in porting the algorithms to manycore accelerator (GPU) architectures. We also provide a brief survey of the applications that have benefited from the scalable implementations of different combinatorial algorithms to enable scientific discovery at scale. We believe that several applications will benefit from the algorithmic and software tools developed by the ExaGraph team.

97 MATHEMATICS AND COMPUTING↗

Distributed Optimal Power Management for Battery Energy Storage Systems: A Novel Accelerated Tracking ADMM Approach

Optimal power management (OPM) is critical for large-scale battery energy storage systems. Today’s methods often require formidable computational effort due to the design based on centralized numerical optimization. Thus, this paper investigates computationally distributed OPM where the agents based on the cells communicate over a network to cooperatively solve the OPM problem. We propose an accelerated tracking alternating direction method of multipliers (ADMM) algorithm to solve the distributed OPM. The proposed algorithm embeds dynamic average consensus and Nesterov’s acceleration technique in the ADMM algorithm. Not only is the proposed algorithm fully distributed without a need for fusion or aggregating nodes, but it also accelerates convergence. The paper formulates the OPM in a model predictive control framework where it seeks to regulate the charging/discharging power of each battery cell to minimize the total power losses and promote balanced use of the constituent cells while complying with the safety constraints. The paper provides ample simulation results to demonstrate the effectiveness and advantages of the proposed distributed OPM in terms of computation and convergence.

Farakhor, Amir↗

Revisiting matrix-based inversion of scanning mobility particle sizer (SMPS) and humidified tandem differential mobility analyzer (HTDMA) data

Abstract. Tikhonov regularization is a tool for reducing noise amplification during data inversion. This work introduces RegularizationTools.jl, a general-purpose software package for applying Tikhonov regularization to data. The package implements well-established numerical algorithms and is suitable for systems of up to ∼ 1000 equations. Included is an abstraction to systematically categorize specific inversion configurations and their associated hyperparameters. A generic interface translates arbitrary linear forward models defined by a computer function into the corresponding design matrix. This obviates the need to explicitly write out and discretize the Fredholm integral equation, thus facilitating fast prototyping of new regularization schemes associated with measurement techniques. Example applications include the inversion involving data from scanning mobility particle sizers (SMPSs) and humidified tandem differential mobility analyzers (HTDMAs). Inversion of SMPS size distributions reported in this work builds upon the freely available software DifferentialMobilityAnalyzers.jl. The speed of inversion is improved by a factor of ∼ 200, now requiring between 2 and 5 ms per SMPS scan when using 120 size bins. Previously reported occasional failure to converge to a valid solution is reduced by switching from the L-curve method to generalized cross-validation as the metric to search for the optimal regularization parameter. Higher-order inversions resulting in smooth, denoised reconstructions of size distributions are now included in DifferentialMobilityAnalyzers.jl. This work also demonstrates that an SMPS-style matrix-based inversion can be applied to find the growth factor frequency distribution from raw HTDMA data while also accounting for multiply charged particles. The outcome of the aerosol-related inversion methods is showcased by inverting multi-week SMPS and HTDMA datasets from ground-based observations, including SMPS data obtained at Bodega Marine Laboratory during the CalWater 2/ACAPEX campaign and co-located SMPS and HTDMA data collected at the US Department of Energy observatory located at the Southern Great Plains site in Oklahoma, USA. Results show that the proposed approaches are suitable for unsupervised, nonparametric inversion of large-scale datasets as well as inversion in real time during data acquisition on low-cost reduced-instruction-set architectures used in single-board computers. The included software implementation of Tikhonov regularization is freely available, general, and domain-independent and thus can be applied to many other inverse problems arising in atmospheric measurement techniques and beyond.

54 ENVIRONMENTAL SCIENCES↗

IBM system/360 assembly language interval arithmetic software

Computer software designed to perform interval arithmetic is described. An interval is defined as the set of all real numbers between two given numbers including or excluding one or both endpoints. Interval arithmetic consists of the various elementary arithmetic operations defined on the set of all intervals, such as interval addition, subtraction, union, etc. One of the main applications of interval arithmetic is in the area of error analysis of computer calculations. For example, it has been used sucessfully to compute bounds on sounding errors in the solution of linear algebraic systems, error bounds in numerical solutions of ordinary differential equations, as well as integral equations and boundary value problems. The described software enables users to implement algorithms of the type described in references efficiently on the IBM 360 system.

Phillips, E. J.↗

Numerical construction of the Hill functions.

As an aid in the numerical construction of Hill functions and their derivatives, an algorithm using local coordinates and an expansion in Legendre polynomials is proposed. The algorithm is shown to possess sufficient stability, and the orthogonality of the Legendre polynomials simplifies the computation when the Ritz-Galerkin technique is used.

Segethova, J.↗

An implicit solution of the three-dimensional Navier-Stokes equations for an airfoil spanning a wind tunnel

An implicit finite-difference algorithm is developed for the numerical solution of the incompressible three dimensional Navier-Stokes equations in the non-conservative primitive-variable formulation. The flow field about an airfoil spanning a wind-tunnel is computed. The coordinate system is generated by an extension of the two dimensional body-fitted coordinate generation techniques of Thompson, as well as that of Sorenson, into three dimensions. Two dimensional grids are stacked along a spanwise coordinate defined by a simple analytical function. A Poisson pressure equation for advancing the pressure in time is arrived at by performing a divergence operation on the momentum equations. The pressure at each time-step is calculated on the assumption that continuity be unconditionally satisfied. An eddy viscosity coefficient, computed according to the algebraic turbulence formulation of Baldwin and Lomax, simulates the effects of turbulence.

Moitra, A.↗

Development of numerical procedures for analysis of complex structures

The paper is concerned with the development of novel numerical procedures for the solution of static, stability, free vibration and dynamic response analysis of large, complex practical structures. Thus, details of numerical algorithms evolved for dynamic analysis of usual non-rotating and also rotating structures as well as finite dynamic elements are presented in the paper. Furthermore, the article provides some description of a general-purpose computer program STARS specifically developed for efficient analysis of complex practical structures.

Gupta, K. K.↗

Numerical Arc Segmentation Algorithm for a Radio Conference-NASARC, Version 2.0: User's Manual

The information contained in the NASARC (Version 2.0) Technical Manual (NASA TM-100160) and the NASARC (Version 2.0) User's Manual (NASA TM-100161) relates to the state of the Numerical Arc Segmentation Algorithm for a Radio Conference (NASARC) software development through October 16, 1987. The technical manual describes the NASARC concept and the algorithms which are used to implement it. The User's Manual provides information on computer system considerations, installation instructions, description of input files, and program operation instructions. Significant revisions have been incorporated in the Version 2.0 software over prior versions. These revisions have enhanced the modeling capabilities of the NASARC procedure while greatly reducing the computer run time and memory requirements. Array dimensions within the software have been structured to fit into the currently available 6-megabyte memory capacity of the International Frequency Registration Board (IFRB) computer facility. A piecewise approach to predetermined arc generation in NASARC (Version 2.0) allows worldwide scenarios to be accommodated within these memory constraints while at the same time reducing computer run time.

Whyte, Wayne A., Jr.↗

Lattice Boltzmann model for simulation of magnetohydrodynamics

A numerical method, based on a discrete Boltzmann equation, is presented for solving the equations of magnetohydrodynamics (MHD). The algorithm provides advantages similar to the cellular automaton method in that it is local and easily adapted to parallel computing environments. Because of much lower noise levels and less stringent requirements on lattice size, the method appears to be more competitive with traditional solution methods. Examples show that the model accurately reproduces both linear and nonlinear MHD phenomena.

Chen, Shiyi↗

A Fully Implicit Time Accurate Method for Hypersonic Combustion: Application to Shock-induced Combustion Instability

A new fully implicit, time accurate algorithm suitable for chemically reacting, viscous flows in the transonic-to-hypersonic regime is described. The method is based on a class of Total Variation Diminishing (TVD) schemes and uses successive Gauss-Siedel relaxation sweeps. The inversion of large matrices is avoided by partitioning the system into reacting and nonreacting parts, but still maintaining a fully coupled interaction. As a result, the matrices that have to be inverted are of the same size as those obtained with the commonly used point implicit methods. In this paper we illustrate the applicability of the new algorithm to hypervelocity unsteady combustion applications. We present a series of numerical simulations of the periodic combustion instabilities observed in ballistic-range experiments of blunt projectiles flying at subdetonative speeds through hydrogen-air mixtures. The computed frequencies of oscillation are in excellent agreement with experimental data.

Yungster, Shaye↗

Recent advances in Euler and Navier-Stokes methods for calculating helicopter rotor aerodynamics and acoustics

This paper outlines some recent advances in the application of the Euler and Navier-Stokes computational fluid dynamics methods to analyze nonlinear problems of helicopter aerodynamics and acoustics. A complete flowfield simulation of helicopters is currently not feasible with these methods. However, the use of the state-of-the-art numerical algorithms in conjunction with powerful supercomputers, like the Cray-2, have enabled notable progress to be made in modeling several individual components of this complex flow in hover and forward flight.

Srinivasan, G. R.↗

REACTIVE TRANSPORT MODELING USING A PARALLEL FULLY-COUPLED SIMULATOR BASED ON PRECONDITIONED JACOBIAN-FREE NEWTON-KRYLOV

Systems of multicomponent reactive transport in porous media that are large, highly nonlinear, and tightly coupled due to complex nonlinear reactions and strong solution-media interactions are often described by a system of coupled nonlinear partial differential algebraic equations (PDAEs). A preconditioned Jacobian-Free Newton-Krylov (JFNK) solution approach is applied to solve the PDAEs in a fully coupled, fully implicit manner. The advantage of the JFNK method is that it avoids explicitly computing and storing the Jacobian matrix during Newton nonlinear iterations for computational efficiency considerations. This solution approach is also enhanced by physics-based blocking preconditioning and multigrid algorithm for efficient inversion of preconditioners. Based on the solution approach, we have developed a reactive transport simulator named RAT. Numerical results are presented to demonstrate the efficiency and massive scalability of the simulator for reactive transport problems involving strong solution-mineral interactions and fast kinetics. It has been applied to study the highly nonlinearly coupled reactive transport system of a promising in situ environmental remediation that involves urea hydrolysis and calcium carbonate precipitation.

58 GEOSCIENCES↗

Model-based tomographic reconstruction

A model-based approach to estimating wall positions for a building is developed and tested using simulated data. It borrows two techniques from geophysical inversion problems, layer stripping and stacking, and combines them with a model-based estimation algorithm that minimizes the mean-square error between the predicted signal and the data. The technique is designed to process multiple looks from an ultra wideband radar array. The processed signal is time-gated and each section processed to detect the presence of a wall and estimate its position, thickness, and material parameters. The floor plan of a building is determined by moving the array around the outside of the building. In this paper we describe how the stacking and layer stripping algorithms are combined and show the results from a simple numerical example of three parallel walls.

97 MATHEMATICS AND COMPUTING↗

Exact charge and energy conservation in implicit PIC with mapped computational meshes

This paper discusses a novel fully implicit formulation for a one-dimensional electrostatic particle-in-cell (PIC) plasma simulation approach. Unlike earlier implicit electrostatic PIC approaches (which are based on a linearized Vlasov Poisson formulation), ours is based on a nonlinearly converged Vlasov Amp re (VA) model. By iterating particles and fields to a tight nonlinear convergence tolerance, the approach features superior stability and accuracy properties, avoiding most of the accuracy pitfalls in earlier implicit PIC implementations. In particular, the formulation is stable against temporal (Courant Friedrichs Lewy) and spatial (aliasing) instabilities. It is charge- and energy-conserving to numerical round-off for arbitrary implicit time steps (unlike the earlier energy-conserving explicit PIC formulation, which only conserves energy in the limit of arbitrarily small time steps). While momentum is not exactly conserved, errors are kept small by an adaptive particle sub-stepping orbit integrator, which is instrumental to prevent particle tunneling (a deleterious effect for long-term accuracy). The VA model is orbit-averaged along particle orbits to enforce an energy conservation theorem with particle sub-stepping. As a result, very large time steps, constrained only by the dynamical time scale of interest, are possible without accuracy loss. Algorithmically, the approach features a Jacobian-free Newton Krylov solver. A main development in this study is the nonlinear elimination of the new-time particle variables (positions and velocities). Such nonlinear elimination, which we term particle enslavement, results in a nonlinear formulation with memory requirements comparable to those of a fluid computation, and affords us substantial freedom in regards to the particle orbit integrator. Numerical examples are presented that demonstrate the advertised properties of the scheme. In particular, long-time ion acoustic wave simulations show that numerical accuracy does not degrade even with very large implicit time steps, and that significant CPU gains are possible.

Chen, Guangye↗

Nonlinear computation of wing-body-vertical tail-wake flows at low supersonic speeds

A numerical method based on the conservation form of the full potential equation has been applied to the problem of three-dimensional supersonic flows with embedded subsonic regions. The governing equation is cast in a nonorthogonal coordinate system, and the theory of characteristics is used to accurately monitor the type-dependent flow field. A conservative switching scheme is employed to transition from the supersonic marching procedure to a subsonic relaxation algorithm and vice versa. The newly developed computer program can handle arbitrary geometries with fuselage, wing, vertical tail and wake components at combined angle of attack and sideslip. Results are presented for a low supersonic Mach numbers flow over the Shuttle orbiter (including the OMS pods and vertical tail), and for flows over a realistic fighter type configuration. Comparisons with experimental data are shown to be in good agreement for various cases.

Szema, K.-Y.↗

Algorithm for Stabilizing a POD-Based Dynamical System

This algorithm provides a new way to improve the accuracy and asymptotic behavior of a low-dimensional system based on the proper orthogonal decomposition (POD). Given a data set representing the evolution of a system of partial differential equations (PDEs), such as the Navier-Stokes equations for incompressible flow, one may obtain a low-dimensional model in the form of ordinary differential equations (ODEs) that should model the dynamics of the flow. Temporal sampling of the direct numerical simulation of the PDEs produces a spatial time series. The POD extracts the temporal and spatial eigenfunctions of this data set. Truncated to retain only the most energetic modes followed by Galerkin projection of these modes onto the PDEs obtains a dynamical system of ordinary differential equations for the time-dependent behavior of the flow. In practice, the steps leading to this system of ODEs entail numerically computing first-order derivatives of the mean data field and the eigenfunctions, and the computation of many inner products. This is far from a perfect process, and often results in the lack of long-term stability of the system and incorrect asymptotic behavior of the model. This algorithm describes a new stabilization method that utilizes the temporal eigenfunctions to derive correction terms for the coefficients of the dynamical system to significantly reduce these errors.

Kalb, Virginia L.↗

Empirical performance bounds for quantum approximate optimization

The quantum approximate optimization algorithm (QAOA) has been put forth as a method for near-term quantum computers to solve optimization problems. However, assessments of QAOA performance have mostly focused on small structured problem instances while performance on more general instances is less clear. Here, we numerically simulate QAOA pure state dynamics for every instance of MaxCut on non-isomorphic unweighted graphs with nine or fewer vertices with depth parameters p ≤ 3. We find the approximation ratios and optimized circuit parameters concentrate across graphs of a given size and empirically show increases in concentration as graph size increases. The parameter concentration leads to two median-angle heuristics that overcome difficulties in QAOA parameter optimization and obtain mean approximation ratios within 3% and 0.2% of the optimal. We also analyze the probability to measure an optimal solution and find increasing variations between graphs as depth increases, in stark contrast to the approximation ratios which concentrate as depth increases. Furthermore, the resulting benchmark data set gives empirical bounds for on-going experimental realizations and lays groundwork for theoretical extensions to greater problem sizes and depths where QAOA may prove important for practically relevant problems.

79 ASTRONOMY AND ASTROPHYSICS↗