Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “algorithmic efficiency”

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 55 records · Page 3

Numerically efficient algorithm for model development of high-order systems

A technique for estimating transfer functions in partial fraction expansion form from frequency response data for a high-order system is presented. The problem formulation avoids many of the numerical difficulties associated with high-order polynomials and has the advantage of having the option to fix the camping and frequency of a mode, if known, during the estimation process. The resulting transfer function(s) may be converted to Jordan-Form time domain equations directly. During the implementation of this technique, a frequency and amplitude normalizing window was developed that maximized the efficiency of the optimization algorithm. The combination of estimating the transfer function in factored form, the ability to fix preciously determined parameters and the effectiveness of the normalizing window led to a progressive approach to synthesizing transfer functions from frequency response data for high-order systems.

Parada, L. O.↗

Efficient algorithms for robust feature matching

One of the basic building blocks in any point-based registration scheme involves matching feature points that are extracted from the sensed image to their counterparts in the reference image. This leads to the fundamental problem of point matching: given two sets of points, find the affine transformation that transforms one point set so that its distance from the other point set is minimized. Because of measurement errors and the presence of outlying data points, it is important that the distance measure between two point sets be robust to these effects. We measure distances using the generalized Hausdorff distance. Point matching can be a computationally intensive task, and there have been a number of algorithms and approaches proposed for solving this problem both theoretical and applied. We present two approaches to the point matching problem, in an attempt to reduce the computational complexity of the problem, while still providing guarantees on the quality of the final match. Our first method is an approximation algorithm, which is loosely based on a branch-and-bound approach due to Huttenlocher and Rucklidge. We show that by varying the approximation error bounds, it is possible to achieve a tradeoff between the quality of the match and the running time of the algorithm. Our second method involves a Monte Carlo method for accelerating the search process used in the first algorithm. With high probability this method succeeds in finding an approximately optimal match. We establish the efficiency of our approaches empirically.

Mount, David M.↗

Lax-Oleinik-Type Formulas and Efficient Algorithms for Certain High-Dimensional Optimal Control Problems

Two of the main challenges in optimal control are solving problems with state-dependent running costs and developing efficient numerical solvers that are computationally tractable in high dimension. In this paper, we provide analytical solutions to certain optimal control problems whose running cost depends on the state variable and with constraints on the control. We also provide Lax-Oleinik-type representation formulas for the corresponding Hamilton-Jacobi partial differential equations with state-dependent Hamiltonians. Additionally, we present an efficient, grid-free numerical solver based on our representation formulas, which is shown to scale linearly with the state dimension, and thus, to overcome the curse of dimensionality. Using existing optimization methods and the min-plus technique, we extend our numerical solvers to address more general classes of convex and nonconvex initial costs. We demonstrate the capabilities of our numerical solvers using implementations on a central processing unit (CPU) and a field-programmable gate array (FPGA). In several cases, our FPGA implementation obtains over a 10 times speedup compared to the CPU, which demonstrates the promising performance boosts FPGAs can achieve. Furthermore, our numerical results show that our solvers have the potential to serve as a building block for solving broader classes of high-dimensional optimal control problems in real-time.

97 MATHEMATICS AND COMPUTING↗

An Efficient Algorithm for Automatic Structure Optimization in X-ray Standing-Wave Experiments

We present that x-ray standing-wave photoemission experiments involving multilayered samples are emerging as unique probes of the buried interfaces that are ubiquitous in current device and materials research. Such data require for their analysis a structure optimization process comparing experiment to theory that is not straightforward. In this work, we present a new computer program for optimizing the analysis of standing-wave data, called SWOPT, that automates this trial-and-error optimization process. The program includes an algorithm that has been developed for computationally expensive problems: so-called black-box simulation optimizations. It also includes a more efficient version of the Yang X-ray Optics Program (YXRO) [Yang, S.-H., Gray, A.X., Kaiser, A.M., Mun, B.S., Sell, B.C., Kortright, J.B., Fadley, C.S., J. Appl. Phys. 113, 1 (2013)] which is about an order of magnitude faster than the original version. Human interaction is not required during optimization. We tested our optimization algorithm on real and hypothetical problems and show that it finds better solutions significantly faster than a random search approach. The total optimization time ranges, depending on the sample structure, from minutes to a few hours on a modern laptop computer, and can be up to 100x faster than a corresponding manual optimization. Finally, these speeds make the SWOPT program a valuable tool for realtime analyses of data during synchrotron experiments.

36 MATERIALS SCIENCE↗

Efficient algorithms for mixed aleatory-epistemic uncertainty quantification with application to radiation-hardened electronics. Part I, algorithms and benchmark results.

This report documents the results of an FY09 ASC V&V Methods level 2 milestone demonstrating new algorithmic capabilities for mixed aleatory-epistemic uncertainty quantification. Through the combination of stochastic expansions for computing aleatory statistics and interval optimization for computing epistemic bounds, mixed uncertainty analysis studies are shown to be more accurate and efficient than previously achievable. Part I of the report describes the algorithms and presents benchmark performance results. Part II applies these new algorithms to UQ analysis of radiation effects in electronic devices and circuits for the QASPR program.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

Computer architecture for efficient algorithmic executions in real-time systems: New technology for avionics systems and advanced space vehicles

Improvements and advances in the development of computer architecture now provide innovative technology for the recasting of traditional sequential solutions into high-performance, low-cost, parallel system to increase system performance. Research conducted in development of specialized computer architecture for the algorithmic execution of an avionics system, guidance and control problem in real time is described. A comprehensive treatment of both the hardware and software structures of a customized computer which performs real-time computation of guidance commands with updated estimates of target motion and time-to-go is presented. An optimal, real-time allocation algorithm was developed which maps the algorithmic tasks onto the processing elements. This allocation is based on the critical path analysis. The final stage is the design and development of the hardware structures suitable for the efficient execution of the allocated task graph. The processing element is designed for rapid execution of the allocated tasks. Fault tolerance is a key feature of the overall architecture. Parallel numerical integration techniques, tasks definitions, and allocation algorithms are discussed. The parallel implementation is analytically verified and the experimental results are presented. The design of the data-driven computer architecture, customized for the execution of the particular algorithm, is discussed.

Carroll, Chester C.↗

An efficient algorithm for numerical airfoil optimization

A new optimization algorithm is presented. The method is based on sequential application of a second-order Taylor's series approximation to the airfoil characteristics. Compared to previous methods, design efficiency improvements of more than a factor of 2 are demonstrated. If multiple optimizations are performed, the efficiency improvements are more dramatic due to the ability of the technique to utilize existing data. The method is demonstrated by application to subsonic and transonic airfoil design but is a general optimization technique and is not limited to a particular application or aerodynamic analysis.

Vanderplaats, G. N.↗

BattPhase—A Convergent, Non-Oscillatory, Efficient Algorithm and Code for Predicting Shape Changes in Lithium Metal Batteries Using Phase-Field Models: Part I. Secondary Current Distribution

Electrochemical models at different scales and varying levels of complexity have been used in the literature to study the evolution of the anode surface in lithium metal batteries. This includes continuum, mesoscale (phase-field approaches), and multiscale models. Thermodynamics-based equations have been used to study phase changes in lithium batteries using phase-field approaches. However, grid convergence studies and the effect of additional parameters needed to simulate these models are not well-documented in the literature. In this paper, using a motivating example of a moving boundary model in one- and two-dimensions, we show how one can formulate phase-field models, implement algorithms for the same and analyze the results. An open-access code with no restrictions is provided as well. This article concludes with some thoughts on the computational efficiency of phase-field models for simulating dendritic growth.

25 ENERGY STORAGE↗

Efficient algorithm for locating and sizing series compensation devices in large power transmission grids: II. Solutions and applications

In a companion manuscript, we developed a novel optimization method for placement, sizing, and operation of Flexible Alternating Current Transmission System (FACTS) devices to relieve transmission network congestion. Specifically, we addressed FACTS that provide Series Compensation (SC) via modification of line inductance. In this manuscript, this heuristic algorithm and its solutions are explored on a number of test cases: a 30-bus test network and a realistically-sized model of the Polish grid (~ 2700 nodes and ~ 3300 lines). The results on the 30-bus network are used to study the general properties of the solutions including non-locality and sparsity. The Polish grid is used as a demonstration of the computational efficiency of the heuristics that leverages sequential linearization of power flow constraints and cutting plane methods that take advantage of the sparse nature of the SC placement solutions. Using these approaches, the algorithm is able to solve an instance of Polish grid in tens of seconds. We explore the utility of the algorithm by analyzing transmission networks congested by (a) uniform load growth, (b) multiple overloaded configurations, and (c) sequential generator retirements.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Efficient Algorithm for Locating and Sizing Series Compensation Devices in Large Transmission Grids: Solutions and Applications (PART II)

In a companion manuscript, we developed a novel optimization method for placement, sizing, and operation of Flexible Alternating Current Transmission System (FACTS) devices to relieve transmission network congestion. Specifically, we addressed FACTS that provide Series Compensation (SC) via modification of line inductance. In this manuscript, this heuristic algorithm and its solutions are explored on a number of test cases: a 30-bus test network and a realistically-sized model of the Polish grid (~2700 nodes and ~3300 lines). The results on the 30-bus network are used to study the general properties of the solutions including non-locality and sparsity. The Polish grid is used as a demonstration of the computational efficiency of the heuristics that leverages sequential linearization of power flow constraints and cutting plane methods that take advantage of the sparse nature of the SC placement solutions. Using these approaches, the algorithm is able to solve an instance of Polish grid in tens of seconds. We explore the utility of the algorithm by analyzing transmission networks congested by (a) uniform load growth, (b) multiple overloaded configurations, and (c) sequential generator retirements

25 ENERGY STORAGE↗

Efficient algorithm for locating and sizing series compensation devices in large power transmission grids: I. Model implementation

We explore optimization methods for planning the placement, sizing and operations of Flexible Alternating Current Transmission System (FACTS) devices installed to relieve transmission grid congestion. We limit our selection of FACTS devices to Series Compensation (SC) devices that can be represented by modification of the inductance of transmission lines. Our master optimization problem minimizes the l 1 norm of the inductance modification subject to the usual line thermal-limit constraints. We develop heuristics that reduce this non-convex optimization to a succession of Linear Programs (LP) which are accelerated further using cutting plane methods. The algorithm solves an instance of the MatPower Polish Grid model (3299 lines and 2746 nodes) in 40 seconds per iteration on a standard laptop—a speed up that allows the sizing and placement of a family of SC devices to correct a large set of anticipated congestions. We observe that our algorithm finds feasible solutions that are always sparse, i.e., SC devices are placed on only a few lines. In a companion manuscript, we demonstrate our approach on realistically-sized networks that suffer congestion from a range of causes including generator retirement. In this manuscript, we focus on the development of our approach, investigate its structure on a small test system subject to congestion from uniform load growth, and demonstrate computational efficiency on a realistically-sized network.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Efficient Algorithm for Locating and Sizing Series Compensation Devices in Large Transmission Grids: Model Implementation (PART 1)

We explore optimization methods for planning the placement, sizing and operations of Flexible Alternating Current Transmission System (FACTS) devices installed to relieve transmission grid congestion. We limit our selection of FACTS devices to Series Compensation (SC) devices that can be represented by modification of the inductance of transmission lines. Our master optimization problem minimizes the l 1 norm of the inductance modification subject to the usual line thermal-limit constraints. We develop heuristics that reduce this non-convex optimization to a succession of Linear Programs (LP) which are accelerated further using cutting plane methods. The algorithm solves an instance of the MatPower Polish Grid model (3299 lines and 2746 nodes) in 40 seconds per iteration on a standard laptop—a speed up that allows the sizing and placement of a family of SC devices to correct a large set of anticipated congestions. We observe that our algorithm finds feasible solutions that are always sparse, i.e., SC devices are placed on only a few lines. In a companion manuscript, we demonstrate our approach on realistically-sized networks that suffer congestion from a range of causes including generator retirement. In this manuscript, we focus on the development of our approach, investigate its structure on a small test system subject to congestion from uniform load growth, and demonstrate computational efficiency on a realistically-sized network.

25 ENERGY STORAGE↗

Improvements to GlennICE Collection Efficiency Algorithm

GlennICE (Glenn Icing Computational Environment) is a computational tool designed to calculate ice growth on complex three-dimensional geometries using the input from a user-supplied computational fluid dynamics (CFD) solution for the geometry of interest. The NASA John H. Glenn Research Center at Lewis Field is developing this tool to aid those evaluating, designing and certifying aircraft, engines, and aircraft components for flight in icing conditions. This domestically available software is being developed to enable the introduction of new icing physics into a computational environment in a manner that is open for evaluation and eventual use by industry, academia, and other government organizations. This paper will document recent improvements that reduce the number of trajectories needed to converge on collection efficiency. These improvements are documented using example cases with complex geometries.

Aircraft Icing↗

Improvements to GlennICE Collection Efficiency Algorithm

GlennICE (Glenn Icing Computational Environment) is a computational tool designed to calculate ice growth on complex three-dimensional geometries using the input from a user-supplied computational fluid dynamics (CFD) solution for the geometry of interest. The NASA John H. Glenn Research Center at Lewis Field is developing this tool to aid those evaluating, designing and certifying aircraft, engines, and aircraft components for flight in icing conditions. This domestically available software is being developed to enable the introduction of new icing physics into a computational environment in a manner that is open for evaluation and eventual use by industry, academia, and other government organizations. This paper will document recent improvements that reduce the number of trajectories needed to converge on collection efficiency. These improvements are documented using example cases with complex geometries.

Aircraft Icing↗

An efficient algorithm for solving the generalized trust region subproblem

In this paper, we consider the interval bounded generalized trust region subproblem (GTRS) which is the problem of minimizing a general quadratic function subject to an upper and lower bounded general quadratic constraint. Under the assumption that two matrices from the objective and the constraint functions can be simultaneously diagonalizable via congruence, a diagonalization-based algorithm is introduced to solve it by showing that GTRS is indeed equivalent to a linearly constrained convex univariate problem. Some numerical experiments are given to show the effectiveness of the proposed method and to compare it with the extended Rendl–Wolkowicz algorithm due to Pong and Wolkowicz.

97 MATHEMATICS AND COMPUTING↗