Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “approximation algorithms”

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 541 records · Page 30

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.↗

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.↗

An efficient algorithm for solution of the unsteady transonic small-disturbance equation

A time accurate approximate factorization (AF) algorithm is formulated for solution of the three dimensional unsteady transonic small-disturbance equation. The AF algorithm consists of a time linearization procedure coupled with a Newton iteration technique. Superior stability characteristics of the new algorithm are demonstrated through applications to steady and oscillatory flows at subsonic and supersonic freestream conditions for an F-5 fighter wing. For steady flow calculations, the size of the time step is cycled to achieve rapid convergence. For unsteady flow calculations, the AF algorithm is sufficiently robust to allow the step size to be selected based on accuracy rather than on stability considerations. Therefore, accurate solutions are obtained in only several hundred time steps yielding a significant computational cost savings when compared to alternative methods.

Batina, John T.↗

An efficient algorithm for solution of the unsteady transonic small-disturbance equation

A time accurate approximation factorization (AF) algorithm is formulated for solution of the three-dimensional unsteady transonic small-disturbance equation. The AF algorithm consists of a time linearization procedure coupled with a Newton iteration technique. Superior stability characteristics of the new algorithm are demonstrated through applications to steady and oscillatory flows at subsonic and supersonic freestream conditions for an F-5 fighter wing. For steady flow calculations, the size of the time step is cycled to achieve rapid convergence. For unsteady flow calculations, the AF algorithm is sufficiently robust to allow the step size to be selected based on accuracy rather than on stability considerations. Therefore, accurate solutions are obtained in only several hundred time steps yielding a significant computational cost savings when compared to alternative methods.

Batina, John T.↗

An implicit algorithm for the conservative transonic full potential equation using an arbitrary mesh

A new, implicit approximate factorization (AF) algorithm designed to solve the conservative full-potential equation for the transonic flow past arbitrary airfoils has been developed. The new algorithm uses an upwind bias of the density coefficient to provide stability in supersonic regions. This allows the simple two- and three-banded matrix form of the AF scheme to be retained over the entire flow field, even in regions of supersonic flow. A numerical transformation is used to establish an arbitrary body-fitted finite-difference mesh. Airfoil pressure distributions have been computed and are in good agreement with independent results.

Holst, T. L.↗

Network-Level Optimization for Unbalanced Power Distribution System: Approximation and Relaxation

The nonlinear programming (NLP) problem to solve distribution-level optimal power flow (D-OPF) poses convergence issues and does not scale well for unbalanced distribution systems. The existing scalable D-OPF algorithms either use approximations that are not valid for an unbalanced power distribution system, or apply relaxation techniques to the nonlinear power flow equations that do not guarantee a feasible power flow solution. In this paper, we propose scalable D-OPF algorithms that simultaneously achieve optimal and feasible solutions by solving multiple iterations of approximate, or relaxed, D-OPF subproblems of low complexity. The first algorithm is based on a successive linear approximation of the nonlinear power flow equations around the current operating point, where the D-OPF solution is obtained by solving multiple iterations of a linear programming (LP) problem. The second algorithm is based on the relaxation of the nonlinear power flow equations as conic constraints together with directional constraints, which achieves optimal and feasible solutions over multiple iterations of a second-order cone programming (SOCP) problem. Finally, it is demonstrated that the proposed algorithms are able to reach an optimal and feasible solution while significantly reducing the computation time as compared to an equivalent NLPD-OPF model for the same distribution system.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Pulse profiles from spinning neutron stars in the Hartle-Thorne approximation

We present a new numerical algorithm for the calculation of pulse profiles from spinning neutron stars in the Hartle-Thorne approximation. Our approach allows us to formally take into account the effects of Doppler shifts and aberration, of frame dragging, as well as of the oblateness of the stellar surface and of its quadrupole moment. We confirm an earlier result that neglecting the oblateness of the neutron-star surface leads to ≅ 5%-30% errors in the calculated profiles and further show that neglecting the quadrupole moment of its spacetime leads to ≅ 1%-5% errors at a spin frequency of ≅ 600 Hz. We discuss the implications of our results for the measurements of neutron-star masses and radii with upcoming X-ray missions, such as NASA's NICER and ESA's LOFT.

79 ASTRONOMY AND ASTROPHYSICS↗

Iterative Stability Enforcement in Adaptive Antoulas–Anderson Algorithms for \({\boldsymbol{\mathcal{H}_2}}\) Model Reduction

This paper presents an extension of the Adaptive-Antoulas-Anderson (AAA) algorithm for rational modelling. Specifically, our new stable multi-input multi-output AAA (smiAAA) algorithm builds rational approximations of multi-input signals with a common set of stable poles. A new methodology is presented for iteratively enforcing stability constraints on the poles. We demonstrate the strengths of this approach compared to the stability enforcement in the FastAAA algorithm. Results using the smiAAA algorithm are compared with the commonly used Vector Fitting algorithm and the more recently published RKFIT algorithm. Vector Fitting and RKFIT both require the user to input the number of poles to use in the approximations. If the final approximation is not accurate enough, the user must re-start Vector Fitting or RKFIT with a larger number of poles and/or a new starting location for the poles. In contrast, the smiAAA algorithm is designed to allow the user to simply input the desired accuracy of the approximations, and the necessary number of poles is detected automatically. This permits users to produce approximations of a desired accuracy with no knowledge about the underlying order of the system being approximated, preventing the algorithm from ever needing to be rerun. An additional feature for preventing extraneous poles from being returned by AAA is also discussed. The cause of these extraneous poles is efficiently detected and removed by our presented methodology. In conclusion, the examples presented demonstrate that smiAAA can efficiently produce approximations of similar or better accuracy than Vector Fitting and RKFIT while requiring less input from the user.

97 MATHEMATICS AND COMPUTING↗

Estimating Turaev-Viro three-manifold invariants is universal for quantum computation

The Turaev-Viro invariants are scalar topological invariants of compact, orientable 3-manifolds. We give a quantum algorithm for additively approximating Turaev-Viro invariants of a manifold presented by a Heegaard splitting. The algorithm is motivated by the relationship between topological quantum computers and (2+1)-dimensional topological quantum field theories. Its accuracy is shown to be nontrivial, as the same algorithm, after efficient classical preprocessing, can solve any problem efficiently decidable by a quantum computer. Thus approximating certain Turaev-Viro invariants of manifolds presented by Heegaard splittings is a universal problem for quantum computation. This establishes a relation between the task of distinguishing nonhomeomorphic 3-manifolds and the power of a general quantum computer.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Enhancing adaptive sparse grid approximations and improving refinement strategies using adjoint-based a posteriori error estimates

In this paper we present an algorithm for adaptive sparse grid approximations of quantities of interest computed from discretized partial differential equations. We use adjoint-based a posteriori error estimates of the physical discretization error and the interpolation error in the sparse grid to enhance the sparse grid approximation and to drive adaptivity of the sparse grid. Utilizing these error estimates provides significantly more accurate functional values for random samples of the sparse grid approximation. We also demonstrate that alternative refinement strategies based upon a posteriori error estimates can lead to further increases in accuracy in the approximation over traditional hierarchical surplus based strategies. Throughout this paper we also provide and test a framework for balancing the physical discretization error with the stochastic interpolation error of the enhanced sparse grid approximation.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Assignment of Freight Traffic in a Large-scale Intermodal Network under Uncertainty

This paper presents a methodology for freight traffic assignment in a large-scale road-rail intermodal network under uncertainty. Network uncertainties caused by natural disasters have dramatically increased in recent years. Several of these disasters (e.g., Hurricane Sandy, Mississippi River Flooding, and Hurricane Harvey) severely disrupted the U.S. freight transportation network, and consequently, the supply chain. To account for these network uncertainties, a stochastic freight traffic assignment model is formulated. An algorithmic framework, involving the sample average approximation and gradient projection algorithm, is proposed to solve this challenging problem. The developed methodology is tested on the U.S. intermodal network with freight flow data from the Freight Analysis Framework. The experiments consider three types of natural disasters that have different risks and impacts on transportation networks: earthquakes, hurricanes, and floods. It is found that for all disaster scenarios, freight ton-miles are higher compared to the base case without uncertainty. The increase in freight ton-miles is the highest under the flooding scenario; this is because there are more states in the flood-risk areas, and they are scattered throughout the U.S.

42 ENGINEERING↗

Diabatic quantum annealing for the frustrated ring model

Abstract Quantum annealing (QA) is a continuous-time heuristic quantum algorithm for solving or approximately solving classical optimization problems. The algorithm uses a schedule to interpolate between a driver Hamiltonian with an easy-to-prepare ground state and a problem Hamiltonian whose ground state encodes solutions to an optimization problem. The standard implementation relies on the evolution being adiabatic: keeping the system in the instantaneous ground state with high probability and requiring a time scale inversely related to the minimum energy gap between the instantaneous ground and excited states. However, adiabatic evolution can lead to evolution times that scale exponentially with the system size, even for computationally simple problems. Here, we study whether non-adiabatic evolutions with optimized annealing schedules can bypass this exponential slowdown for one such class of problems called the frustrated ring model. For sufficiently optimized annealing schedules and system sizes of up to 39 qubits, we provide numerical evidence that we can avoid the exponential slowdown. Our work highlights the potential of highly-controllable QA to circumvent bottlenecks associated with the standard implementation of QA.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Minimization versus homotopy algorithms

The relative merits and demerits of the minimization techniques are assessed using globally convergent quasi-Newton algorithms on the one hand and the homotopy algorithms on the other hand for the solution of problems of nonlinear structural analysis. Like the homotopy algorithms, the globally convergent quasi-Newton algorithms are equally suited for the solution of the nonlinear equations of structural analysis directly without having to pose the problem as an equivalent minimization problem. In the close neighborhood of the limit and bifurcation points quasi-Newton algorithms experience difficulties. Homotopy algorithms are robust for practically all types of nonlinear problems but are computationally not as cost effective since they provide an extremely accurate prediction of the response by calculating it as a large number of points. Globally convergent algorithms can perform well with very approximate Hessians, while homotopy algorithms require extremely accurate Hessians. While quasi-Newton algorithms can be very easily structured to exploit sparsity and symmetry, homotopy algorithms are not presently so structured and would require special modifications for exploitation of such features without sacrificing robustness and global convergence.

Kamat, M. P.↗

Engine With Regression and Neural Network Approximators Designed

At the NASA Glenn Research Center, the NASA engine performance program (NEPP, ref. 1) and the design optimization testbed COMETBOARDS (ref. 2) with regression and neural network analysis-approximators have been coupled to obtain a preliminary engine design methodology. The solution to a high-bypass-ratio subsonic waverotor-topped turbofan engine, which is shown in the preceding figure, was obtained by the simulation depicted in the following figure. This engine is made of 16 components mounted on two shafts with 21 flow stations. The engine is designed for a flight envelope with 47 operating points. The design optimization utilized both neural network and regression approximations, along with the cascade strategy (ref. 3). The cascade used three algorithms in sequence: the method of feasible directions, the sequence of unconstrained minimizations technique, and sequential quadratic programming. The normalized optimum thrusts obtained by the three methods are shown in the following figure: the cascade algorithm with regression approximation is represented by a triangle, a circle is shown for the neural network solution, and a solid line indicates original NEPP results. The solutions obtained from both approximate methods lie within one standard deviation of the benchmark solution for each operating point. The simulation improved the maximum thrust by 5 percent. The performance of the linear regression and neural network methods as alternate engine analyzers was found to be satisfactory for the analysis and operation optimization of air-breathing propulsion engines (ref. 4).

Patnaik, Surya N.↗

Time-dependent Navier-Stokes computations of separated flows over airfoils

The application of both a central-difference and an upwind implicit approximate factorization Navier-Stokes algorithm to highly separated flow is described. Using the thin-layer approximation, both algorithms are employed to solve the low Reynolds number laminar flow around a circular cylinder with periodic shedding. Results agree with experimental Strouhal numbers to within about 10 percent. A grid refinement study is conducted using the upwind code for both the thin-layer and complete Navier-Stokes approximations. The circular cylinder solution is shown to be highly dependent upon both grid density outward from the body and grid extent. Finally, the thin-layer central-difference code is used to predict the time-accurate unsteady flow about two stalled airfoils. The NACA 0012 airfoil turbulent solutions are periodic with Strouhal numbers of about 0.1; a strong vortex is periodically shed from the leading edge. The LS(1)-0417 airfoil turbulent solution shows a high frequency oscillatory trailing edge separation. The 20 degree NACA 0012 airfoil solution is massively separated, but shows no evidence of periodicity.

Rumsey, C. L.↗

Flow simulations about steady-complex and unsteady moving configurations using structured-overlapped and unstructured grids

The limiting factor in simulating flows past realistic configurations of interest has been the discretization of the physical domain on which the governing equations of fluid flow may be solved. In an attempt to circumvent this problem, many Computational Fluid Dynamic (CFD) methodologies that are based on different grid generation and domain decomposition techniques have been developed. However, due to the costs involved and expertise required, very few comparative studies between these methods have been performed. In the present work, the two CFD methodologies which show the most promise for treating complex three-dimensional configurations as well as unsteady moving boundary problems are evaluated. These are namely the structured-overlapped and the unstructured grid schemes. Both methods use a cell centered, finite volume, upwind approach. The structured-overlapped algorithm uses an approximately factored, alternating direction implicit scheme to perform the time integration, whereas, the unstructured algorithm uses an explicit Runge-Kutta method. To examine the accuracy, efficiency, and limitations of each scheme, they are applied to the same steady complex multicomponent configurations and unsteady moving boundary problems. The steady complex cases consist of computing the subsonic flow about a two-dimensional high-lift multielement airfoil and the transonic flow about a three-dimensional wing/pylon/finned store assembly. The unsteady moving boundary problems are a forced pitching oscillation of an airfoil in a transonic freestream and a two-dimensional, subsonic airfoil/store separation sequence. Accuracy was accessed through the comparison of computed and experimentally measured pressure coefficient data on several of the wing/pylon/finned store assembly's components and at numerous angles-of-attack for the pitching airfoil. From this study, it was found that both the structured-overlapped and the unstructured grid schemes yielded flow solutions of comparable accuracy for these simulations. This study also indicated that, overall, the structured-overlapped scheme was slightly more CPU efficient than the unstructured approach.

Newman, James C., III↗