Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “approximation algorithm”

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 271 records · Page 15
All sourcesNASA NTRSDOE OSTI
NASA NTRS2019

Study network-related optimization problems using quantum alternating optimization ansatz

Network-related connectivity optimization problems are underlying a wide range of applications and are also of high computational complexity. We consider studying network optimization problems using two types of quantum heuristics. One is quantum annealing, and the other Quantum Alternating Operator Ansatz, an extension of the Quantum Approximate Optimization Algorithms for gate-model quantum computation, in which a cost-function based unitary and a non-commuting mixing unitary are applied alternately. We present problem mappings for problems of finding the spanning-tree or spanning-graph of a graph that optimizes certain costs, and a variant that further requires the spanning-tree be degree-bounded. With quantum annealing, all constraints are cast into penalty terms in the cost Hamiltonian, and the solution is encoded as the ground state of the Hamiltonian. We provide three mappings to the quadratic unconstrained binary optimization (QUBO) form, compare the resource requirements, and analyze the tradeoffs. For QAOA, we give special focus on the design of mixers based on the constraints presented in the problem, such that the system evolution remains in a subspace of the full Hilbert space where all constraints are satisfied. In the spanning-tree problem, one such hard constraint is that a mixer applied to a spanning-tree needs also be a spanning tree. This involves checking the connectivity of a subgraph, which is a global condition common for most network-related problems. We show how this feature can be efficiently represented in the mixer in a quantum coherent way, based on manipulation of a descendant-matrix and an adjacent matrix. We further develop a mixer for the spanning-graphs based on the spanning-tree mixer.

Zhihui Wang↗
NASA NTRSDate not supplied

Dynamical Decoupling of Crosstalk on Superconducting Qubit Devices

Current NISQ devices are prone to errors. In order to be used for practical applications or achieve fault-tolerant thresholds, strategies to suppress error rates will be needed to maximize the potential of noisy devices. Dynamical decoupling (DD) is one such strategy for suppressing — or at least alleviating — the effects of decoherence, in which sequences of pulses are applied to qubits to decouple their interaction with the environment. Through experimental runs performed on several Rigetti quantum computing units (QPUs), we first demonstrate that DD is capable of improving coherence times for isolated qubits, as well as suppressing errors caused by the ZZ coupling between pairs of qubits. Extending this framework to cycles containing2-qubit gates, we show that DD can be inserted to decouple qubits from crosstalk occurring during neighboring 2-qubit gates, and demonstrate the efficacy of this procedure on quantum approximate optimization algorithm (QAOA) circuits. We also explore the usage of tailored DD sequences for the suppression of characterized error channels. We are grateful for support from the NASA Ames Research Center and from the DARPA ONISQ program under interagency agreement IAA 8839,Annex 114. HYH is supported by the USRA Feynman QuantumAcademy funded by the NAMS R&D Student Program and a UCHellman Fellowship. JS, ZGI and ZW are supported by USRA NASAAcademic Mission Service (NNA16BD14C).

Dynamical decoupling↗
DOE OSTI2023

Leverage Score Sampling for Parametric PDEs (Final Technical Report)

This final technical report summarizes the accomplishments of work performed under DOE Office of Science Award DE-SC0022266, which is titled “Leverage Score Sampling for Parametric PDEs”. The goal of the project was to extend methods from Randomized Numerical Linear Algebra (RandNLA) to tackle central computational challenges in model order reduction and uncertainty quantification (UQ) for parametric partial differential equations (PDEs). In particular, we sought to use importance sampling methods originally developed for RandNLA to develop sample efficient active learning algorithms for approximating high-dimensional scalar functions, e.g. by polynomials, Gaussian process models, and simple neural networks. Such methods can be immediately applied to developing surrogate models or to approximating quantity of interest (QoI) surfaces. In the context of PDEs, each sample used for learning equates to the solution of the differential equation for a particular set of parameters, so sample efficiency translates to improved computational efficiency for a variety of downstream tasks.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

QFw: A Quantum Framework for Large-scale HPC Ecosystems

This work extends Quantum Framework (QFw) by integrating it with Northwest Quantum Simulator (NWQ-Sim) and by introducing a lightweight python library that allows multiple frontends (e.g., Qiskit) to interact with QFw. This extension enables QFw to flexibly decouple frontends from backends (e.g., NWQ-Sim). We demonstrate this capability by executing a Greenberger-Horne-Zeilinger (GHZ) circuit using Qiskit and Pennylane with NWQ-Sim and Tensor-Network Quantum Virtual-Machine (TN-QVM). QFw enables easy scaling to multiple nodes. We showcase this with scaling tests using GHZ with up to 32 qubits for different number of nodes on the Frontier supercomputer. And, to demonstrate the use of QFw for real world problems, we solve a metamaterial optimization problem, using a Quantum Approximate Optimization Algorithm (QAOA). We observe that QFw over NWQ-Sim marginally improves Qiskit-aer’s accuracy in reaching the lowest energy state. These additions to QFw prepare it to run hybrid applications in a hybrid resource environment since it treats actual quantum hardware and simulators alike.

Chundury, Srikar↗
DOE OSTI2024

Integrating Multi-Source Data for Bi-Level Traffic Simulator Calibration: A Literature Review and Highway Case Study

Traffic simulation serves as a powerful tool for pre-evaluating policies and technologies. In this context, simulation-based Dynamic traffic assignment (DTA) models are capable of capturing traffic dynamics. They are well-known as critical tools in controlling and predicting traffic situations. The reliability of simulation results heavily depends on the calibration process. Most studies in the literature formulate and calibrate simulators based on a single source of collected data or multiple data sets with the same spatiotemporal characteristics. However, in practice, traffic data is collected by various tools with usually different spatial and temporal resolutions. This study introduces a novel approach to taking into account diverse input data from a variety of sources. An iterative bi-level solution is proposed. to equally treat traffic flow and speed data. The upper level solves flow calibration with the exact solution method, and the lower level calibrates the speed with the simultaneous perturbation stochastic approximation (SPSA) algorithm. Subsequently, the effectiveness of the proposed model is investigated using data from a six-mile section of Nashville's I-24 highway in Tennessee. The results demonstrate that our proposed model creates an effective feedback loop between the optimizer and the simulator for calibrating flow and speed to reduce the error between simulated and real data.

42 ENGINEERING↗
NASA NTRS2008

Parallel Implementation of the Recursive Approximation of an Unsupervised Hierarchical Segmentation Algorithm

The hierarchical image segmentation algorithm (referred to as HSEG) is a hybrid of hierarchical step-wise optimization (HSWO) and constrained spectral clustering that produces a hierarchical set of image segmentations. HSWO is an iterative approach to region grooving segmentation in which the optimal image segmentation is found at N(sub R) regions, given a segmentation at N(sub R+1) regions. HSEG's addition of constrained spectral clustering makes it a computationally intensive algorithm, for all but, the smallest of images. To counteract this, a computationally efficient recursive approximation of HSEG (called RHSEG) has been devised. Further improvements in processing speed are obtained through a parallel implementation of RHSEG. This chapter describes this parallel implementation and demonstrates its computational efficiency on a Landsat Thematic Mapper test scene.

Tilton, James C.↗
NASA NTRS1999

Flight Test of an Adaptive Configuration Optimization System for Transport Aircraft

A NASA Dryden Flight Research Center program explores the practical application of real-time adaptive configuration optimization for enhanced transport performance on an L-1011 aircraft. This approach is based on calculation of incremental drag from forced-response, symmetric, outboard aileron maneuvers. In real-time operation, the symmetric outboard aileron deflection is directly optimized, and the horizontal stabilator and angle of attack are indirectly optimized. A flight experiment has been conducted from an onboard research engineering test station, and flight research results are presented herein. The optimization system has demonstrated the capability of determining the minimum drag configuration of the aircraft in real time. The drag-minimization algorithm is capable of identifying drag to approximately a one-drag-count level. Optimizing the symmetric outboard aileron position realizes a drag reduction of 2-3 drag counts (approximately 1 percent). Algorithm analysis of maneuvers indicate that two-sided raised-cosine maneuvers improve definition of the symmetric outboard aileron drag effect, thereby improving analysis results and consistency. Ramp maneuvers provide a more even distribution of data collection as a function of excitation deflection than raised-cosine maneuvers provide. A commercial operational system would require airdata calculations and normal output of current inertial navigation systems; engine pressure ratio measurements would be optional.

Gilyard, Glenn B.↗
NASA NTRS1984

Computing approximate random Delta v magnitude probability densities

This paper describes the development and use of an algorithm to compute approximate statistics of the magnitude of a single random trajectory correction maneuver (TCM) Delta v vector. The TCM Delta v vector is modeled as a three component Cartesian vector each of whose components is a random variable having a normal (Gaussian) distribution with zero mean and possibly unequal standard deviations. The algorithm uses these standard deviations as input to produce approximations to (1) the mean and standard deviation of the magnitude of Delta v, (2) points of the probability density function of the magnitude of Delta v, and (3) points of the cumulative and inverse cumulative distribution functions of Delta v. The approximates are based on Monte Carlo techniques developed in a previous paper by the author and extended here. The algorithm described is expected to be useful in both pre-flight planning and in-flight analysis of maneuver propellant requirements for space missions.

Chadwick, C.↗
NASA NTRS1991

Genetic algorithm based input selection for a neural network function approximator with applications to SSME health monitoring

A genetic algorithm is used to select the inputs to a neural network function approximator. In the application considered, modeling critical parameters of the space shuttle main engine (SSME), the functional relationship between measured parameters is unknown and complex. Furthermore, the number of possible input parameters is quite large. Many approaches have been used for input selection, but they are either subjective or do not consider the complex multivariate relationships between parameters. Due to the optimization and space searching capabilities of genetic algorithms they were employed to systematize the input selection process. The results suggest that the genetic algorithm can generate parameter lists of high quality without the explicit use of problem domain knowledge. Suggestions for improving the performance of the input selection process are also provided.

Peck, Charles C.↗
NASA NTRS2019

Quantum Gate-Model Approaches to Exact and Approximate Optimization

Many of the most challenging computational problems arising in practical applications are tackled by heuristic algorithms which have not been rigorously proven to outperform other approaches but rather have been empirically demonstrated to be effective. While quantum heuristics have been proposed since the early days of quantum computing, true empirical evaluation of the real-world performance of these algorithms is only becoming possible now as increasingly powerful quantum gate-model devices continue to come online.In this talk, I will give an overview of the NASA QuAIL team's ongoing investigation into quantum gate-model heuristic algorithms for exact and approximate optimization. In particular, we consider the performance of the Quantum Approximate Optimization Algorithm on NP-hard optimization problems, and describe algorithm parameter setting strategies for real-world quantum hardware. We then show a generalization of QAOA circuits, the Quantum Alternating Operator Ansatz, especially suitable for low-resource implementations of QAOA for problems with hard (feasibility) constraints. The talk will conclude with a discussion of research challenges, particularly for optimization and sampling applications of QAOA, and the potential of more general quantum heuristics to give advantages over classical computers.

Hadfield, Stuart↗
NASA NTRS1991

Fast Approximate Analysis Of Modified Antenna Structure

Abbreviated algorithms developed for fast approximate analysis of effects of modifications in supporting structures upon root-mean-square (rms) path-length errors of paraboloidal-dish antennas. Involves combination of methods of structural-modification reanalysis with new extensions of correlation analysis to obtain revised rms path-length error. Full finite-element analysis, usually requires computer of substantial capacity, necessary only to obtain responses of unmodified structure to known external loads and to selected self-equilibrating "indicator" loads. Responses used in shortcut calculations, which, although theoretically "exact", simple enough to be performed on hand-held calculator. Useful in design, design-sensitivity analysis, and parametric studies.

Levy, Roy↗
NASA NTRS1987

Unsteady transonic algorithm improvements for realistic aircraft applications

Improvements to a time-accurate approximate factorization (AF) algorithm were implemented for steady and unsteady transonic analysis of realistic aircraft configurations. These algorithm improvements were made to the CAP-TSD (Computational Aeroelasticity Program - Transonic Small Disturbance) code developed at the Langley Research Center. The code permits the aeroelastic analysis of complete aircraft in the flutter critical transonic speed range. The AF algorithm of the CAP-TSD code solves the unsteady transonic small-disturbance equation. The algorithm improvements include: an Engquist-Osher (E-O) type-dependent switch to more accurately and efficiently treat regions of supersonic flow; extension of the E-O switch for second-order spatial accuracy in these regions; nonreflecting far field boundary conditions for more accurate unsteady applications; and several modifications which accelerate convergence to steady-state. Calculations are presented for several configurations including the General Dynamics one-ninth scale F-16C aircraft model to evaluate the algorithm modifications. The modifications have significantly improved the stability of the AF algorithm and hence the reliability of the CAP-TSD code in general.

Batina, John T.↗
NASA NTRS1988

Unsteady transonic algorithm improvements for realistic aircraft applications

Improvements to a time-accurate approximate factorization (AF) algorithm have been implemented for steady and unsteady transonic analysis of realistic aircraft configurations. The algorithm improvements include: an Engquist-Osher (E-O) type-dependent switch to more accurately and efficiently treat regions of supersonic flow, extension of the E-O switch for second-order spatial accuracy in these regions, nonreflecting far field boundary conditions for more accurate unsteady applications, and several modifications which accelerate convergence to steady-state. Calculations are presented for several configurations to evaluate the algorithm modifications. The modifications have significantly improved the stability of the AF algorithm and hence the reliability of the CAP-TSD code in general.

Batina, John T.↗
DOE OSTI2023

On the Approximability of Random-Hypergraph MAX-3-XORSAT Problems with Quantum Algorithms

Constraint satisfaction problems are an important area of computer science. Many of these problems are in the complexity class NP which is exponentially hard for all known methods, both for worst cases and often typical. Fundamentally, the lack of any guided local minimum escape method ensures the hardness of both exact and approximate optimization classically, but the intuitive mechanism for approximation hardness in quantum algorithms based on Hamiltonian time evolution is poorly understood. We explore this question using the prototypically hard MAX-3-XORSAT problem class. We conclude that the mechanisms for quantum exact and approximation hardness are fundamentally distinct. We qualitatively identify why traditional methods such as quantum adiabatic optimization are not good approximation algorithms. We propose a new spectral folding optimization method that does not suffer from these issues and study it analytically and numerically. We consider random rank-3 hypergraphs including extremal planted solution instances, where the ground state satisfies an anomalously high fraction of constraints compared to truly random problems. We show that, if we define the energy to be $E = N_{unsat}-N_{sat}$, then spectrally folded quantum optimization will return states with energy $E \leq A E_{GS}$ (where $E_{GS}$ is the ground state energy) in polynomial time, where conservatively, $A \simeq 0.6$. We thoroughly benchmark variations of spectrally folded quantum optimization for random classically approximation-hard (planted solution) instances in simulation, and find performance consistent with this prediction. We do not claim that this approximation guarantee holds for all possible hypergraphs, though our algorithm's mechanism can likely generalize widely. These results suggest that quantum computers are more powerful for approximate optimization than had been previously assumed.

Kapit, Eliot↗
NASA NTRS1989

Optimal aeroassisted guidance using Loh's term approximations

This paper presents three guidance algorithms for aerocapture and/or aeroassisted orbital transfer with plane change. All three algorithms are based on the approximate solution of an optimal control problem at each guidance update. The chief assumption is that Loh's term may be modeled as a function of the independent variable only. The first two algorithms maximize exit speed for fixed exit altitude, flight path angle and heading angle. The third minimizes, in one sense, the control effort for fixed exit altitude, flight path angle, heading angle and speed. Results are presented which indicate the near optimality of the solutions generated by the first two algorithms. Results are also presented which indicate the performance of the third algorithm in a simulation with unmodeled atmospheric density disturbances.

Mceneaney, W. M.↗
NASA NTRS1975

Spline function approximation techniques for image geometric distortion representation

Least squares approximation techniques were developed for use in computer aided correction of spatial image distortions for registration of multitemporal remote sensor imagery. Polynomials were first used to define image distortion over the entire two dimensional image space. Spline functions were then investigated to determine if the combination of lower order polynomials could approximate a higher order distortion with less computational difficulty. Algorithms for generating approximating functions were developed and applied to the description of image distortion in aircraft multispectral scanner imagery. Other applications of the techniques were suggested for earth resources data processing areas other than geometric distortion representation.

Anuta, P. E.↗
NASA NTRS1979

A fast, conservative algorithm for solving the transonic full-potential equation

A fast, fully implicit approximate factorization (AF) algorithm designed to solve the conservative transonic full-potential equation in either two or three dimensions is described. The algorithm uses an upwind bias of the density coefficient for stability in supersonic regions. This provides an effective upwind difference of the streamwise terms for any orientation of the velocity vector (i.e., 'rotated differencing'), and thereby greatly enhances the reliability of the present algorithm. A numerical transformation is used to establish an arbitrary body-fitted finite-difference mesh. Computed results for both airfoils and simplified wings demonstrate substantial improvement in convergence speed for the new algorithm relative to standard successive-line overrelaxation algorithms.

Holst, T. L.↗
DOE OSTI2024

Streaming Matching and Edge Cover in Practice

Graph algorithms with polynomial space and time requirements often become infeasible for massive graphs with billions of edges or more. State-of-the-art approaches therefore employ approximate serial, parallel, and distributed algorithms to tackle these challenges. However, such approaches require storing the entire graph in memory and thus need access to costly computing resources such as clusters and supercomputers. In this paper, we present practical streaming approaches for solving massive graph problems using limited memory for two prototypical graph problems: maximum weighted matching and minimum weighted edge cover. For matching, we conduct a thorough computational study on two of the semi-streaming algorithms including a recent breakthrough result that achieves a $1/(2+\varepsilon)$-approximation of the weight while using $O( n \log W /\epsilon)$ memory (here $n$ is the number of vertices and $W$ is the maximum edge weight), designed by Paz and Schwartzman [SODA, 2017]. Empirically, we show that the semi-streaming algorithms produce matchings whose weight is close to the best $1/2$-approximate offline algorithm while requiring less time and an order-of-magnitude less memory. For minimum weighted edge cover, we develop three novel semi-streaming algorithms. Two of these algorithms require a single pass through the input graph, require $O(n \log n)$ memory, and provide a 2-approximation guarantee on the objective. We also leverage a relationship between approximate maximum weighted matching and approximate minimum weighted edge cover to develop a two-pass $3/2+\epsilon$-approximate algorithm with the memory requirement of Paz and Schwartzman's semi-streaming matching algorithm. These streaming approaches are compared against the state-of-the-art 3/2-approximate offline algorithm. The semi-streaming matching and the novel edge cover algorithms proposed in this paper can process graphs with several billions of edges in under 30 minutes using 6 GB of memory, which is at least an order of magnitude improvement from the offline (non-streaming) algorithms. For the largest graph, the best alternative offline parallel approximation algorithm (GPA+ROMA) could not finish in three hours even while employing hundreds of processors and 1 TB of memory. We also demonstrate an application of the semi-streaming algorithm by computing a matching using linearly bounded memory on item intersection graphs derived from three machine learning datasets, whereas the existing offline algorithms could not complete on one of these datasets since their memory requirements exceeded 1TB.

Ferdous, S M.↗