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 307 records · Page 17

An efficient and robust grid optimization algorithm

The development of an efficient and robust grid optimization is presented. This algorithm is developed by combining the best characteristics of algebraic, elliptic, and hyperbolic grid generation techniques. This development is based on the following observations and evaluations: (1) algebraic systems are fast and economical; (2) precise spacing control is always achieved; (3) grid generation by elliptic systems is always smooth; and (4) the hyperbolic system preserves the orthogonality at the solid boundary and the point distribution in the field. Computational examples representing practical internal flow configurations are presented to demonstrate the algorithm.

Soni, Bharat K.↗

Adapting iterative algorithms for solving large sparse linear systems for efficient use on the CDC CYBER 205

Adapting and designing mathematical software to achieve optimum performance on the CYBER 205 is discussed. Comments and observations are made in light of recent work done on modifying the ITPACK software package and on writing new software for vector supercomputers. The goal was to develop very efficient vector algorithms and software for solving large sparse linear systems using iterative methods.

Kincaid, D. R.↗

Constraint Embedding Technique for Multibody System Dynamics

Multibody dynamics play a critical role in simulation testbeds for space missions. There has been a considerable interest in the development of efficient computational algorithms for solving the dynamics of multibody systems. Mass matrix factorization and inversion techniques and the O(N) class of forward dynamics algorithms developed using a spatial operator algebra stand out as important breakthrough on this front. Techniques such as these provide the efficient algorithms and methods for the application and implementation of such multibody dynamics models. However, these methods are limited only to tree-topology multibody systems. Closed-chain topology systems require different techniques that are not as efficient or as broad as those for tree-topology systems. The closed-chain forward dynamics approach consists of treating the closed-chain topology as a tree-topology system subject to additional closure constraints. The resulting forward dynamics solution consists of: (a) ignoring the closure constraints and using the O(N) algorithm to solve for the free unconstrained accelerations for the system; (b) using the tree-topology solution to compute a correction force to enforce the closure constraints; and (c) correcting the unconstrained accelerations with correction accelerations resulting from the correction forces. This constraint-embedding technique shows how to use direct embedding to eliminate local closure-loops in the system and effectively convert the system back to a tree-topology system. At this point, standard tree-topology techniques can be brought to bear on the problem. The approach uses a spatial operator algebra approach to formulating the equations of motion. The operators are block-partitioned around the local body subgroups to convert them into aggregate bodies. Mass matrix operator factorization and inversion techniques are applied to the reformulated tree-topology system. Thus in essence, the new technique allows conversion of a system with closure-constraints into an equivalent tree-topology system, and thus allows one to take advantage of the host of techniques available to the latter class of systems. This technology is highly suitable for the class of multibody systems where the closure-constraints are local, i.e., where they are confined to small groupings of bodies within the system. Important examples of such local closure-constraints are constraints associated with four-bar linkages, geared motors, differential suspensions, etc. One can eliminate these closure-constraints and convert the system into a tree-topology system by embedding the constraints directly into the system dynamics and effectively replacing the body groupings with virtual aggregate bodies. Once eliminated, one can apply the well-known results and algorithms for tree-topology systems to solve the dynamics of such closed-chain system.

Woo, Simon S.↗

A fast, space-efficient average-case algorithm for the 'Greedy' Triangulation of a point set, and a proof that the Greedy Triangulation is not approximately optimal

The paper addresses the problem of how to find the Greedy Triangulation (GT) efficiently in the average case. It is noted that the problem is open whether there exists an efficient approximation algorithm to the Optimum Triangulation. It is first shown how in the worst case, the GT may be obtained in time O(n to the 3) and space O(n). Attention is then given to how the algorithm may be slightly modified to produce a time O(n to the 2), space O(n) solution in the average case. Finally, it is mentioned that Gilbert has found a worst case solution using totally different techniques that require space O(n to the 2) and time O(n to the 2 log n).

Manacher, G. K.↗

Reduction of the effects of the communication delays in scientific algorithms on message passing MIMD architectures

The efficient implementation of algorithms on multiprocessor machines requires that the effects of communication delays be minimized. The effects of these delays on the performance of a model problem on a hypercube multiprocessor architecture is investigated and methods are developed for increasing algorithm efficiency. The model problem under investigation is the solution by red-black Successive Over Relaxation YOUN71 of the heat equation; most of the techniques described here also apply equally well to the solution of elliptic partial differential equations by red-black or multicolor SOR methods. Methods for reducing communication traffic and overhead on a multiprocessor are identified and results of testing these methods on the Intel iPSC Hypercube reported. Methods for partitioning a problem's domain across processors, for reducing communication traffic during a global convergence check, for reducing the number of global convergence checks employed during an iteration, and for concurrently iterating on multiple time-steps in a time-dependent problem. Empirical results show that use of these models can markedly reduce a numewrical problem's execution time.

Saltz, J. H.↗

Filtering and error analysis via the UDU super T covariance factorization

Kalman filter algorithms based on the UDU super T covariance factorization are discussed, with special attention given to algorithm implementation efficiency. A U-D-factored covariance error-analysis algorithm is formulated, and its efficiency and numerical stability are demonstrated in a representative orbit determination problem. The numerical results are compared with those obtained using covariance error-analysis formulas, and the comparison highlights the numerical superiority of the present algorithm. A byproduct of the U-D analysis is a highly efficient algorithm mechanization of the arbitrary gain covariance update formula.

Thornton, C. L.↗

Probabilistic structural analysis algorithm development for computational efficiency

The PSAM (Probabilistic Structural Analysis Methods) program is developing a probabilistic structural risk assessment capability for the SSME components. An advanced probabilistic structural analysis software system, NESSUS (Numerical Evaluation of Stochastic Structures Under Stress), is being developed as part of the PSAM effort to accurately simulate stochastic structures operating under severe random loading conditions. One of the challenges in developing the NESSUS system is the development of the probabilistic algorithms that provide both efficiency and accuracy. The main probability algorithms developed and implemented in the NESSUS system are efficient, but approximate in nature. In the last six years, the algorithms have improved very significantly.

Wu, Y.-T.↗

Communication-Aware Orbit Design for Small Spacecraft Swarms around Small Bodies

Exploration of small Solar System bodies has traditionally been performed by single monolithic spacecraft carrying a number of science instruments. However, science instruments typically cannot be operated simultaneously due to the instrument requirements including optimal viewing angle, surface illumination, altitude and ground resolution, power, and data constraints. This observation has motivated interest in multi-spacecraft architectures where a swarm of small spacecraft, each carrying a single science instrument, studies a small body after being deployed by a carrier spacecraft, which then collects data from the vehicles and relays it to Earth. Such architectures hold promise to yield significant improvements in mission efficiency, increases in data quality, and shorter mission duration. A key difficulty in the design of such missions is the selection of orbits for the small spacecraft, which must satisfy not only instrument requirements, but also strict inter-spacecraft communication and on-board storage constraints. To address this, in this paper, we present a novel computationally-efficient optimization algorithm for \emph{communication-aware design} of the orbits of a small spacecraft swarm orbiting a small body. The proposed approach captures constraints including instrument requirements, inter-spacecraft communication bandwidths, and on-board memory usage, and it can accommodate highly irregular gravity field models and surface geometries. We propose an efficient algorithm for optimization of instrument observations and inter-spacecraft communications; we then leverage the differentiable nature of the proposed algorithm to accelerate a gradient-based global search algorithm. Numerical simulations of a six-spacecraft swarm studying 433 Eros show that the proposed approach successfully identifies high-quality orbits, and significantly outperform communication-agnostic optimization techniques, resulting in a 10% increase in scientific returns and a 30% increase in the quality of the collected data.

Rahmani, Amir↗

Fast Parallel Computation Of Multibody Dynamics

Constraint-force algorithm fast, efficient, parallel-computation algorithm for solving forward dynamics problem of multibody system like robot arm or vehicle. Solves problem in minimum time proportional to log(N) by use of optimal number of processors proportional to N, where N is number of dynamical degrees of freedom: in this sense, constraint-force algorithm both time-optimal and processor-optimal parallel-processing algorithm.

Fijany, Amir↗

Algorithm Sorts Groups Of Data

For efficient sorting, algorithm finds set containing minimum or maximum most significant data. Sets of data sorted as desired. Sorting process simplified by reduction of each multielement set of data to single representative number. First, each set of data expressed as polynomial with suitably chosen base, using elements of set as coefficients. Most significant element placed in term containing largest exponent. Base selected by examining range in value of data elements. Resulting series summed to yield single representative number. Numbers easily sorted, and each such number converted back to original set of data by successive division. Program written in BASIC.

Evans, J. D.↗

Serial and parallel computation of Kane's equations for multibody dynamics

The analysis of the efficiency of algorithms resulting from Kane's Equation for serial and parallel computation of mass matrix is examined. The algorithms resulting from Kane's equation and Modified Kane's equations are detailed. An analysis was made of two classes of algorithms for computation of mass matrix: the Newton-Euler based algorithms and the Composite rigid body algorithms. An analysis was also made of the efficiency of different algorithms for serial and parallel computations. Conclusions are drawn and presented.

Fijany, Amir↗

Computationally efficient multibody simulations

Computationally efficient approaches to the solution of the dynamics of multibody systems are presented in this work. The computational efficiency is derived from both the algorithmic and implementational standpoint. Order(n) approaches provide a new formulation of the equations of motion eliminating the assembly and numerical inversion of a system mass matrix as required by conventional algorithms. Computational efficiency is also gained in the implementation phase by the symbolic processing and parallel implementation of these equations. Comparison of this algorithm with existing multibody simulation programs illustrates the increased computational efficiency.

Ramakrishnan, Jayant↗

Empirical study of parallel LRU simulation algorithms

This paper reports on the performance of five parallel algorithms for simulating a fully associative cache operating under the LRU (Least-Recently-Used) replacement policy. Three of the algorithms are SIMD, and are implemented on the MasPar MP-2 architecture. Two other algorithms are parallelizations of an efficient serial algorithm on the Intel Paragon. One SIMD algorithm is quite simple, but its cost is linear in the cache size. The two other SIMD algorithm are more complex, but have costs that are independent on the cache size. Both the second and third SIMD algorithms compute all stack distances; the second SIMD algorithm is completely general, whereas the third SIMD algorithm presumes and takes advantage of bounds on the range of reference tags. Both MIMD algorithm implemented on the Paragon are general and compute all stack distances; they differ in one step that may affect their respective scalability. We assess the strengths and weaknesses of these algorithms as a function of problem size and characteristics, and compare their performance on traces derived from execution of three SPEC benchmark programs.

Carr, Eric↗

Bayesian Estimation of Precipitation from Satellite Passive Microwave Observations Using Combined Radar-Radiometer Retrievals

Precipitation estimation from satellite passive microwave radiometer observations is a problem that does not have a unique solution that is insensitive to errors in the input data. Traditionally, to make this problem well posed, a priori information derived from physical models or independent, high-quality observations is incorporated into the solution. In the present study, a database of precipitation profiles and associated brightness temperatures is constructed to serve as a priori information in a passive microwave radiometer algorithm. The precipitation profiles are derived from a Tropical Rainfall Measuring Mission (TRMM) combined radar radiometer algorithm, and the brightness temperatures are TRMM Microwave Imager (TMI) observed. Because the observed brightness temperatures are consistent with those derived from a radiative transfer model embedded in the combined algorithm, the precipitation brightness temperature database is considered to be physically consistent. The database examined here is derived from the analysis of a month-long record of TRMM data that yields more than a million profiles of precipitation and associated brightness temperatures. These profiles are clustered into a tractable number of classes based on the local sea surface temperature, a radiometer-based estimate of the echo-top height (the height beyond which the reflectivity drops below 17 dBZ), and brightness temperature principal components. For each class, the mean precipitation profile, brightness temperature principal components, and probability of occurrence are determined. The precipitation brightness temperature database supports a radiometer-only algorithm that incorporates a Bayesian estimation methodology. In the Bayesian framework, precipitation estimates are weighted averages of the mean precipitation values corresponding to the classes in the database, with the weights being determined according to the similarity between the observed brightness temperature principal components and the brightness temperature principal components of the classes. Because the classes are stratified by the sea surface temperature and the echo-top-height estimator, the number of classes that are considered for retrieval is significantly smaller than the total number of classes, making the algorithm computationally efficient. The radiometer-only algorithm is applied to TMI observations, and precipitation estimates are compared with combined TRMM precipitation radar (PR) TMI reference estimates. The TMI-only algorithm, supported by the empirically derived database, produces estimates that are more consistent with the reference values than the precipitation estimates from the version-6 TRMM facility TMI algorithm. Cloud-resolving model simulations are used to assign a latent heating profile to each precipitation profile in the empirically derived database, making it possible to estimate latent heating using the radiometer-only algorithm. Although the evaluation of latent heating estimates in this study is preliminary, because realistic conditional probability distribution functions are attached to latent heating structures in the algorithm s database, a generally positive impact on latent heating estimation from passive microwave observations is expected.

Grecu, Mircea↗

An implicit factored scheme for the compressible Navier-Stokes equations

An implicit finite difference scheme is developed for the numerical solution of the compressible Navier-Stokes equations in conservation-law form. The algorithm is second-order-time accurate, noniterative, and spatially factored. In order to obtain an efficient factored algorithm, the spatial cross-derivatives are evaluated explicitly. However, the algorithm is unconditionally stable and, although a three-time-level scheme, requires only two-time-levels of data storage. The algorithm is constructed in a 'delta' form (i.e., increments of the conserved variables and fluxes) that provides a direct derivation of the scheme and leads to an efficient computational algorithm. In addition, the delta form has the advantageous property of a steady-state (if one exists) independent of the size of the time step. Numerical results are presented for a two-dimensional shock boundary-layer interaction problem.

Beam, R. M.↗

Efficient and Accurate Explicit Integration Algorithms with Application to Viscoplastic Models

Several explicit integration algorithms with self-adative time integration strategies are developed and investigated for efficiency and accuracy. These algorithms involve the Runge-Kutta second order, the lower Runge-Kutta method of orders one and two, and the exponential integration method. The algorithms are applied to viscoplastic models put forth by Freed and Verrilli and Bodner and Partom for thermal/mechanical loadings (including tensile, relaxation, and cyclic loadings). The large amount of computations performed showed that, for comparable accuracy, the efficiency of an integration algorithm depends significantly on the type of application (loading). However, in general, for the aforementioned loadings and viscoplastic models, the exponential integration algorithm with the proposed self-adaptive time integration strategy worked more (or comparably) efficiently and accurately than the other integration algorithms. Using this strategy for integrating viscoplastic models may lead to considerable savings in computer time (better efficiency) without adversely affecting the accuracy of the results. This conclusion should encourage the utilization of viscoplastic models in the stress analysis and design of structural components.

Arya, Vinod K.↗

Algorithm Optimally Allocates Actuation of a Spacecraft

A report presents an algorithm that solves the following problem: Allocate the force and/or torque to be exerted by each thruster and reaction-wheel assembly on a spacecraft for best performance, defined as minimizing the error between (1) the total force and torque commanded by the spacecraft control system and (2) the total of forces and torques actually exerted by all the thrusters and reaction wheels. The algorithm incorporates the matrix vector relationship between (1) the total applied force and torque and (2) the individual actuator force and torque values. It takes account of such constraints as lower and upper limits on the force or torque that can be applied by a given actuator. The algorithm divides the aforementioned problem into two optimization problems that it solves sequentially. These problems are of a type, known in the art as semi-definite programming problems, that involve linear matrix inequalities. The algorithm incorporates, as sub-algorithms, prior algorithms that solve such optimization problems very efficiently. The algorithm affords the additional advantage that the solution requires the minimum rate of consumption of fuel for the given best performance.

Motaghedi, Shi↗

Hardware-Efficient Quantum Optimization Layered Algorithms and Experiments

Quantum optimization algorithms, such as QAOA, that implement parametrized stochastic optimization solvers attempt to identify low-energy solutions of Ising systems by exploiting available quantum effects in noisy-intermediate scale machines. Engineering a well-performing parametrized quantum optimization circuit is indeed an exercise in balancing the trade-off between expressivity and implementation complexity. We show that, for MaxCut QAOA circuits defined on native hardware topology (Rigetti’s Aspen Quantum Processors), error-mitigation techniques recover simulated features of the noiseless theory. Moreover, we explore a design space for QAOA-like ansatze that perform well in theory as well as in hardware for fully-connected problems. We also discuss how efficient coherence and entanglement detection methods that could be coupled with quantum optimization experiments require only linear overhead in benchmarking time.

quantum computing↗