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 145 records · Page 8

Can we derive Tully's surface-hopping algorithm from the semiclassical quantum Liouville equation? Almost, but only with decoherence

In this article, we demonstrate that Tully's fewest-switches surface hopping (FSSH) algorithm approximately obeys the mixed quantum-classical Liouville equation (QCLE), provided that several conditions are satisfied – some major conditions, and some minor. The major conditions are: (1) nuclei must be moving quickly with large momenta; (2) there cannot be explicit recoherences or interference effects between nuclear wave packets; (3) force-based decoherence must be added to the FSSH algorithm, and the trajectories can no longer rigorously be independent (though approximations for independent trajectories are possible). We furthermore expect that FSSH (with decoherence) will be most robust when nonadiabatic transitions in an adiabatic basis are dictated primarily by derivative couplings that are presumably localized to crossing regions, rather than by small but pervasive off-diagonal force matrix elements. In the end, our results emphasize the strengths of and possibilities for the FSSH algorithm when decoherence is included, while also demonstrating the limitations of the FSSH algorithm and its inherent inability to follow the QCLE exactly.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Area Coverage Planning with 3-axis Steerable, 2D Framing Sensors

Existing algorithms for Agile Earth Observing Satellites((Lemaitre et al. 2002)) were largely created for 1D line sensors that acquire images in linear swaths. However, imaging satellites increasingly use 2D framing sensors (cameras) that capture discrete rectangular images. We describe tiling step-stare approaches that are more suited to rectangular image footprints than are 1D swath-based algorithms. Optimal area planning for these 2D framing instruments is an NPcomplete problem and intractable for large areas, so we present four approximation algorithms. Strategies are compared against a prior 2D framing instrument algorithm (Knight 2014) in three computational experiments. The impact of observer agility on schedule makespan is examined. Makespans vary more as observer agility decreases toward a critical point, then vary less after the critical point, suggesting a possible problem phase transition.

Chien, Steve↗

HBMax: Optimizing Memory Efficiency for Parallel Influence Maximization on Multicore Architectures

The goal of influence maximization is to select k most-influential vertices or seeds in a network, where influence is defined by a given diffusion process. The problem has a number of important applications such as viral marketing, information spread, and epidemic control. Although computing optimal seed set is NP-Hard, due to the submodular nature of the problem efficient approximation algorithms exist. However, even state-of-the-art parallel implementations are limited by a sampling step that incurs large memory footprints. This in turn limits the problem size reach and approximation quality. In this work, we study the memory footprint of the sampling process collecting reverse reachability information in the IMM algorithm over large real-world social networks. We present an adaptive and memory-efficient optimization approach for a state-of-the-art multi-threaded parallel influence maximization algorithm. Our approach,HuffMax, uses a portion of the reverse reachable (RR) sets collected by the algorithm to learn the characteristics of the graph. Then, it compresses the intermediate reverse reachability information with Huffman coding, and queries directly on the compressed data to preserve the memory savings obtained through compression. We also propose an efficient sampling strategy based on the distribution of RR sets, which can further reduce the computation time for typical social networks with long-tail distributions. Considering a NUMA architecture, we scale up our solution on 128-core CPUs and reduce the memory footprint by up to 45.7% with negligible time overhead (or even faster) and without perceivable loss of accuracy.

Chen, Xinyu↗

Two-Stage Estimation and Variance Modeling for Latency-Constrained Variational Quantum Algorithms

The quantum approximate optimization algorithm (QAOA) has enjoyed increasing attention in noisy, intermediate-scale quantum computing with its application to combinatorial optimization problems. QAOA has the potential to demonstrate a quantum advantage for NP-hard combinatorial optimization problems. As a hybrid quantum-classical algorithm, the classical component of QAOA resembles a simulation optimization problem in which the simulation outcomes are attainable only through a quantum computer. The simulation that derives from QAOA exhibits two unique features that can have a substantial impact on the optimization process: (i) the variance of the stochastic objective values typically decreases in proportion to the optimality gap, and (ii) querying samples from a quantum computer introduces an additional latency overhead. In this paper, we introduce a novel stochastic trust-region method derived from a derivative-free, adaptive sampling trust-region optimization method intended to efficiently solve the classical optimization problem in QAOA by explicitly taking into account the two mentioned characteristics. The key idea behind the proposed algorithm involves constructing two separate local models in each iteration: a model of the objective function and a model of the variance of the objective function. Exploiting the variance model allows us to restrict the number of communications with the quantum computer and also helps navigate the nonconvex objective landscapes typical in QAOA optimization problems. In conclusion, we numerically demonstrate the superiority of our proposed algorithm using the SimOpt library and Qiskit when we consider a metric of computational burden that explicitly accounts for communication costs.

Derivative-free Optimization↗

Fully quantum algorithm for mesoscale fluid simulations with application to partial differential equations

Fluid flow simulations marshal our most powerful computational resources. In many cases, even this is not enough. Quantum computers provide an opportunity to speed up traditional algorithms for flow simulations. We show that lattice-based mesoscale numerical methods can be executed as efficient quantum algorithms due to their statistical features. This approach revises a quantum algorithm for lattice gas automata to reduce classical computations and state preparation at every time step. For this, the algorithm approximates the qubit relative phases and subtracts them at the end of each time step. Phases are evaluated using the iterative phase estimation algorithm and subtracted using single-qubit rotation phase gates. Further, this method optimizes the quantum resource required and makes it more appropriate for near-term quantum hardware. We also demonstrate how the checkerboard deficiency that the D1Q2 scheme presents can be resolved using the D1Q3 scheme. The algorithm is validated by simulating two canonical partial differential equations: the diffusion and Burgers' equations on different quantum simulators. We find good agreement between quantum simulations and classical solutions for the presented algorithm.

97 MATHEMATICS AND COMPUTING↗

A Comprehensive Study of Three Delay Compensation Algorithms for Flight Simulators

This paper summarizes a comprehensive study of three predictors used for compensating the transport delay in a flight simulator; The McFarland, Adaptive and State Space Predictors. The paper presents proof that the stochastic approximation algorithm can achieve the best compensation among all four adaptive predictors, and intensively investigates the relationship between the state space predictor s compensation quality and its reference model. Piloted simulation tests show that the adaptive predictor and state space predictor can achieve better compensation of transport delay than the McFarland predictor.

Guo, Liwen↗

Graphical models for optimal power flow

Optimal power flow (OPF) is the central optimization problem in electric power grids. Although solved routinely in the course of power grid operations, it is known to be strongly NP-hard in general, and weakly NP-hard over tree networks. In this paper, we formulate the optimal power flow problem over tree networks as an inference problem over a tree-structured graphical model where the nodal variables are low-dimensional vectors. We adapt the standard dynamic programming algorithm for inference over a tree-structured graphical model to the OPF problem. Combining this with an interval discretization of the nodal variables, we develop an approximation algorithm for the OPF problem. Further, we use techniques from constraint programming (CP) to perform interval computations and adaptive bound propagation to obtain practically efficient algorithms. Compared to previous algorithms that solve OPF with optimality guarantees using convex relaxations, our approach is able to work for arbitrary tree-structured distribution networks and handle mixed-integer optimization problems. Further, it can be implemented in a distributed message-passing fashion that is scalable and is suitable for “smart grid” applications like control of distributed energy resources. In conclusion, numerical evaluations on several benchmark networks show that practical OPF problems can be solved effectively using this approach.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Optimal mapping of neural-network learning on message-passing multicomputers

A minimization of learning-algorithm completion time is sought in the present optimal-mapping study of the learning process in multilayer feed-forward artificial neural networks (ANNs) for message-passing multicomputers. A novel approximation algorithm for mappings of this kind is derived from observations of the dominance of a parallel ANN algorithm over its communication time. Attention is given to both static and dynamic mapping schemes for systems with static and dynamic background workloads, as well as to experimental results obtained for simulated mappings on multicomputers with dynamic background workloads.

Chu, Lon-Chan↗

Graph decomposition techniques for solving combinatorial optimization problems with variational quantum algorithms

The quantum approximate optimization algorithm (QAOA) has the potential to approximately solve complex combinatorial optimization problems in polynomial time. However, current noisy quantum devices cannot solve large problems due to hardware constraints. In this work, we develop an algorithm that decomposes the QAOA input problem graph into a smaller problem and solves MaxCut using QAOA on the reduced graph. The algorithm requires a subroutine that can be classical or quantum—in this work, we implement the algorithm twice on each graph. One implementation uses the classical solver Gurobi in the subroutine and the other uses QAOA. We solve these reduced problems with QAOA. On average, the reduced problems require only approximately 1/10 of the number of vertices than the original MaxCut instances. Furthermore, the average approximation ratio of the original MaxCut problems is 0.75, while the approximation ratios of the decomposed graphs are on average of 0.96 for both Gurobi and QAOA. With this decomposition, we are able to measure optimal solutions for ten 100-vertex graphs by running single-layer QAOA circuits on the Quantinuum trapped-ion quantum computer H1-1, sampling each circuit only 500 times. This approach is best suited for sparse, particularly k-regular graphs, as k-regular graphs on n vertices can be decomposed into a graph with at most $\frac{nk}{k+1}$ vertices in polynomial time. Further reductions can be obtained with a potential trade-off in computational time. In conclusion, while this paper applies the decomposition method to the MaxCut problem, it can be applied to more general classes of combinatorial optimization problems.

97 MATHEMATICS AND COMPUTING↗

Numerical analysis of discrete fractional integrodifferential structural dampers

This paper develops solution algorithms enabling the handling of the dynamic response of nonlinear structures contained discretely attached dampers modeled by fractional integrodifferential operators of the Grunwald-Liouville-Riemann type. The development consists of two levels of formulation, namely: (1) numerical approximations of fractional operators and, (2) the establishment of global level implicit schemes enabling the solution to nonlinear structural formulations. To generalize the overall results, error estimates are derived for the fractional operator approximation algorithm. These enable an ongoing optimization of solution efficiency for a given error tolerance. To benchmark the scheme, the results of several numerical experiments are presented. These illustrate the numerical characteristics of the overall formulation.

Padovan, Joseph↗

Advanced Control Algorithms for Compensating the Phase Distortion Due to Transport Delay in Human-Machine Systems

The desire to create more complex visual scenes in modern flight simulators outpaces recent increases in processor speed. As a result, simulation transport delay remains a problem. New approaches for compensating the transport delay in a flight simulator have been developed and are presented in this report. The lead/lag filter, the McFarland compensator and the Sobiski/Cardullo state space filter are three prominent compensators. The lead/lag filter provides some phase lead, while introducing significant gain distortion in the same frequency interval. The McFarland predictor can compensate for much longer delay and cause smaller gain error in low frequencies than the lead/lag filter, but the gain distortion beyond the design frequency interval is still significant, and it also causes large spikes in prediction. Though, theoretically, the Sobiski/Cardullo predictor, a state space filter, can compensate the longest delay with the least gain distortion among the three, it has remained in laboratory use due to several limitations. The first novel compensator is an adaptive predictor that makes use of the Kalman filter algorithm in a unique manner. In this manner the predictor can accurately provide the desired amount of prediction, while significantly reducing the large spikes caused by the McFarland predictor. Among several simplified online adaptive predictors, this report illustrates mathematically why the stochastic approximation algorithm achieves the best compensation results. A second novel approach employed a reference aircraft dynamics model to implement a state space predictor on a flight simulator. The practical implementation formed the filter state vector from the operator s control input and the aircraft states. The relationship between the reference model and the compensator performance was investigated in great detail, and the best performing reference model was selected for implementation in the final tests. Theoretical analyses of data from offline simulations with time delay compensation show that both novel predictors effectively suppress the large spikes caused by the McFarland compensator. The phase errors of the three predictors are not significant. The adaptive predictor yields greater gain errors than the McFarland predictor for short delays (96 and 138 ms), but shows smaller errors for long delays (186 and 282 ms). The advantage of the adaptive predictor becomes more obvious for a longer time delay. Conversely, the state space predictor results in substantially smaller gain error than the other two predictors for all four delay cases.

Guo, Liwen↗

DONKEY: A Flexible and Accurate Algorithm for Clustering

We propose an accurate clustering algorithm suitable for the varied and multidimensional data sets that correspond to temporal snapshots from on-the-fly nonadiabatic trajectory-based simulations of photoexcited dynamics. The algorithm approximates the underlying probability density function using variable kernel density estimation, with local maxima corresponding to cluster centers. Each data point is then assigned to one of the maxima by employing a maximization procedure. Finally, clusters artificially separated by minor fluctuations in the probability density are merged. The algorithm does not require parameter tuning, which ensures flexibility and reduces the risk of bias. It is tested on several synthetic data sets, where it consistently outperforms conventional clustering algorithms. As a final example, the algorithm is applied to the excited dynamics of the norbornadiene ⇌ quadricyclane (C 7 H 8 ) molecular photoswitch, demonstrating how distinct reaction pathways can be identified.

algorithms↗

Iterative spectral method for solving electrostatic or magnetostatic problems in complex and evolving heterostructures

Electrostatic or magnetostatic problems involving complex heterogeneity are nontrivial for modeling and simulation. Most existing numerical methods focus on sharp interface models and the computational cost increases with increasing complexity of the geometry. Here we develop an iterative spectral method, the bound charge successive approximation algorithm, to solve electrostatic or magnetostatic heterogeneity problems in the context of diffuse-interface modeling. As tests and verifications, this algorithm is applied to calculation of the depolarization factor of an ellipsoid, and simulation of random dielectric mixtures and the dielectophoretic motion of multiple particles. The algorithm shows excellent efficiency and the computational cost mainly depends on the permittivity or permeability contrast in the whole system, regardless of the complexity of the geometry. Specifically, for evolving heterostructures the solution of bound charge in one time step can be used as input for the next, which could further significantly shorten the iteration (approximation) process, making it practical to simulate the long-range electrostatic or magnetostatic interaction in complex and evolving heterostructures.

97 MATHEMATICS AND COMPUTING↗

Scaling Out a Combinatorial Algorithm for Discovering Carcinogenic Gene Combinations to Thousands of GPUs

Cancer is a leading cause of death in the US, second only to heart disease. It is primarily a result of a combination of an estimated two-nine genetic mutations (multi-hit combinations). Although a body of research has identified hundreds of cancer-causing genetic mutations, we don’t know the specific combination of mutations responsible for specific instances of cancer for most cancer types. An approximate algorithm for solving the weighted set cover problem was previously adapted to identify combinations of genes with mutations that may be responsible for individual instances of cancer. However, the algorithm’s computational requirement scales exponentially with the number of genes, making it impractical for identifying more than three-hit combinations, even after the algorithm was parallelized and scaled up to a V100 GPU. Since most cancers have been estimated to require more than three hits, we scaled out the algorithm to identify combinations of four or more hits using 1000 nodes (6000 V100 GPUs with ≈48×106 processing cores) on the Summit supercomputer at Oak Ridge National Laboratory. Efficiently scaling out the algorithm required a series of algorithmic innovations and optimizations for balancing an exponentially divergent workload across processors and for minimizing memory latency and inter-node communication. We achieved an average strong scaling efficiency of 90.14% (80.96%–97.96% for 200 to 1000 nodes), compared to a 100 node run, with 84.18% scaling efficiency for 1000 nodes. With experimental validation, the multi-hit combinations identified here could provide further insight into the etiology of different cancer subtypes and provide a rational basis for targeted combination therapy.

Dash, Sajal↗

Fronts propagating with curvature dependent speed: Algorithms based on Hamilton-Jacobi formulations

New numerical algorithms are devised (PSC algorithms) for following fronts propagating with curvature-dependent speed. The speed may be an arbitrary function of curvature, and the front can also be passively advected by an underlying flow. These algorithms approximate the equations of motion, which resemble Hamilton-Jacobi equations with parabolic right-hand-sides, by using techniques from the hyperbolic conservation laws. Non-oscillatory schemes of various orders of accuracy are used to solve the equations, providing methods that accurately capture the formation of sharp gradients and cusps in the moving fronts. The algorithms handle topological merging and breaking naturally, work in any number of space dimensions, and do not require that the moving surface be written as a function. The methods can be used also for more general Hamilton-Jacobi-type problems. The algorithms are demonstrated by computing the solution to a variety of surface motion problems.

Osher, Stanley↗

Iterative packing for demand matching and sparse packing.

The main result we will present is a 2k-approximation algorithm for the following 'k-hypergraph demand matching' problem: given a set system with sets of size <=k, where sets have profits & demands and vertices have capacities, find a max-profit subsystem whose demands do not exceed the capacities. The main tool is an iterative way to explicitly build a decomposition of the fractional optimum as 2k times a convex combination of integral solutions. If time permits we'll also show how the approach can be extended to a 3-approximation for 2-column sparse packing. The second result is tight w.r.t the integrality gap, and the first is near-tight as a gap lower bound of 2(k-1+1/k) is known.

99 GENERAL AND MISCELLANEOUS↗

Enhancing scattering images for orientation recovery with diffusion map

We explore the possibility for orientation recovery in single-molecule coherent diffractive imaging with diffusion map. This algorithm approximates the Laplace-Beltrami operator, which we diagonalize with a metric that corresponds to the mapping of Euler angles onto scattering images. While suitable for images of objects with specific properties we show why this approach fails for realistic molecules. Here, we introduce a modification of the form factor in the scattering images which facilitates the orientation recovery and should be suitable for all recovery algorithms based on the distance of individual images. (C) 2016 Optical Society of America

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

Fractional boundary layer flow and radiation heat transfer of MHD viscoelastic fluid over an unsteady stretching surface

This paper presents an investigation for magnetohydrodynamic (MHD) viscoelastic fluid boundary layer flow and radiation heat transfer over an unsteady stretching sheet in presence of heat source. Time dependent fractional derivative is first introduced in formulating the boundary layer equations. Numerical solutions are obtained by using the finite difference scheme and L1-algorithm approximation. Results indicate that the proposed model describes a basic delaying times framework for viscoelastic flow and radiation heat transfer. The effects of involved parameters on velocity and temperature fields are shown graphically and analyzed in detail.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗