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 199 records · Page 11

The computation of generalized cross-validation functions through householder tridiagonalization with applications to the fitting of interaction spline models

An efficient algorithm for computing the generalized cross-validation function for the general cross-validated regularization/smoothing problem is provided. This algorithm is appropriate for problems where no natural structure is available, and the regularization/smoothing problem is solved (exactly) in a reproducing kernel Hilbert space. It is particularly appropriate for certain multivariate smoothing problems with irregularly spaced data, and certain remote sensing problems, such as those that occur in meteorology, where the sensors are arranged irregularly. The algorithm is applied to the fitting of interaction spline models with irregularly spaced data and two smoothing parameters; favorable timing results are presented. The algorithm may be extended to the computation of certain generalized maximum likelihood (GML) functions. Application of the GML algorithm to a problem in numerical weather forecasting, and to a broad class of hypothesis testing problems, is noted.

Gu, Chong↗

Bandwidth efficient coding for fading channels - Code construction and performance analysis

The authors apply a general method of bounding the event error probability of trellis-coded modulation schemes to fading channels and use the effective length and the minimum-squared-product distance to replace the minimum-free-squared-Euclidean distance as code design parameters for Rayleigh and Rician fading channels with a substantial multipath component. They present 8-PSK trellis codes specifically constructed for fading channels that outperform equivalent codes designed for the additive white Gaussian noise channel when v is greater than or equal to 5. For quasiregular trellis codes there exists an efficient algorithm for evaluating event error probability, and numerical results on Pe which demonstrate the importance of the effective length as a code design parameter for fading channels with or without side information have been obtained. This is consistent with the case for binary signaling, where the Hamming distance remains the best code design parameter for fading channels. The authors show that the use of Reed-Solomon block codes with expanded signal sets becomes interesting only for large values of E(s)/N(0), where they begin to outperform trellis codes.

Schlegel, Christian↗

Distributed parameter estimation for large beam-like structures for general inputs

In this paper, maximum likelihood estimation for distributed parameter models of large flexible structures has been formulated. Distributed parameter models involve far fewer unknown parameters than independent modal characteristics of finite element models. The closed-form solutions for the partial differential equations with general forced inputs have been derived. The closed-form expressions of the sensitivity functions lead to highly efficient algorithms for analyzing ground or on-orbit test results. Numerical simulations with impulse and step inputs to the NASA Mini-MAST trust have been demonstrated. The estimations of modal properties involve its longitudinal elongation modes, lateral bending modes and torsional modes. The results show that distributed parameter models are promising in the parameter estimation of large flexible structures.

Shen, Ji-Yao↗

Computing Gravitational Bumps From Repeating-Orbit Data

Iterative, least-squares algorithm efficiently computes estimates of both position errors indicative of irregularities in gravitational field of Earth and trajectory of satellite in orbit repeating along same ground track. Exploits sparse-matrix techniques. Useful in surveying, navigation, and geophysical research. Particularly useful for processing data on trajectory of satellite in low orbit tracked via Global Positioning System (GPS).

Wu, Jiun-Tsong↗

Multiprocessors and runtime compilation

Runtime preprocessing plays a major role in many efficient algorithms in computer science, as well as playing an important role in exploiting multiprocessor architectures. Examples are given that elucidate the importance of runtime preprocessing and show how these optimizations can be integrated into compilers. To support the arguments, transformations implemented in prototype multiprocessor compilers are described and benchmarks from the iPSC2/860, the CM-2, and the Encore Multimax/320 are presented.

Saltz, Joel↗

The simultaneous integration of many trajectories using nilpotent normal forms

Taylor's formula shows how to approximate a certain class of functions by polynomials. The approximations are arbitrarily good in some neighborhood whenever the function is analytic and they are easy to compute. The main goal is to give an efficient algorithm to approximate a neighborhood of the configuration space of a dynamical system by a nilpotent, explicitly integrable dynamical system. The major areas covered include: an approximating map; the generalized Baker-Campbell-Hausdorff formula; the Picard-Taylor method; the main theorem; simultaneous integration of trajectories; and examples.

Grayson, Matthew A.↗

A fully Sinc-Galerkin method for Euler-Bernoulli beam models

A fully Sinc-Galerkin method in both space and time is presented for fourth-order time-dependent partial differential equations with fixed and cantilever boundary conditions. The Sinc discretizations for the second-order temporal problem and the fourth-order spatial problems are presented. Alternate formulations for variable parameter fourth-order problems are given which prove to be especially useful when applying the forward techniques to parameter recovery problems. The discrete system which corresponds to the time-dependent partial differential equations of interest are then formulated. Computational issues are discussed and a robust and efficient algorithm for solving the resulting matrix system is outlined. Numerical results which highlight the method are given for problems with both analytic and singular solutions as well as fixed and cantilever boundary conditions.

Smith, R. C.↗

Likelihood estimation for distributed parameter models for NASA Mini-MAST truss

A maximum likelihood estimation for distributed parameter models of large flexible structures was formulated. Distributed parameter models involve far fewer unknown parameters than independent modal characteristics or finite element models. The closed form solutions for the partial differential equations with corresponding boundary conditions were derived. The closed-form expressions of sensitivity functions led to highly efficient algorithms for analyzing ground or on-orbit test results. For an illustration of this approach, experimental data of the NASA Mini-MAST truss was used. The estimations of modal properties involve lateral bending modes and torsional modes. The results show that distributed parameter models are promising in the parameter estimation of large flexible structures.

Shen, Ji-Yao↗

Masking failures of multidimensional sensors (extended abstract)

When a computer monitors a physical process, the computer uses sensors to determine the values of the physical variables that represent the state of the process. A sensor can sometimes fail, however, and in the worst case report a value completely unrelated to the true physical value. The work described is motivated by a methodology for transforming a process control program that can not tolerate sensor failure into one that can. In this methodology, a reliable abstract sensor is created by combining information from several real sensors that measure the same physical value. To be useful, an abstract sensor must deliver reasonably accurate information at reasonable computational cost. Sensors are considered that deliver multidimensional values (e.g., location or velocity in three dimensions, or both temperature and pressure). Geometric techniques are used to derive upper bounds on abstract sensor accuracy and to develop efficient algorithms for implementing abstract sensors.

Chew, Paul↗

Optimal expression evaluation for data parallel architectures

A data parallel machine represents an array or other composite data structure by allocating one processor per data item. A pointwise operation can be performed between two such arrays in unit time, provided their corresponding elements are allocated in the same processors. If the arrays are not aligned in this fashion, the cost of moving one or both of them is part of the cost of operation. The choice of where to perform the operation then affects this cost. If an expression with several operands is to be evaluated, there may be many choices of where to perform the intermediate operations. An efficient algorithm is given to find the minimum cost way to evaluate an expression, for several different data parallel architectures. The algorithm applies to any architecture in which the metric describing the cost of moving an array has a property called robustness. This encompasses most of the common data parallel communication architectures, including meshes of arbitrary dimension and hypercubes.

Gilbert, J. R.↗

Unified formulation of dynamics for serial rigid multibody systems

There has been a growing interest in the development of new and efficient algorithms for multibody dynamics in recent years. Serial rigid multibody systems form the basic subcomponents of general multibody systems, and a variety of algorithms to solve the serial chain forward dynamics problem have been proposed. In this paper, the economy of representation and analysis tools provided by the spatial operator algebra are used to clarify the inherent structure of these algorithms, to identify those that are similar, and to study the relationships among the ones that are distinct. For the purposes of this study, the algorithms are categorized into three classes: algorithms that require the explicit computation of the mass matrix, algorithms that are completely recursive in nature, and algorithms of intermediate complexity. In addition, alternative factorizations for the mass matrix and closed form expressions for its inverse are derived. These results provide a unifying perspective, within which these diverse dynamics algorithms arise naturally as a consequence of a progressive exploitation of the structure of the mass matrix.

Jain, Abhinandan↗

Robust control systems design by H-infinity optimization theory

In this paper, step-by-step procedures of applying the H-infinity theory to robust control systems design are given. The objective of the paper is to eliminate the possible difficulties a control engineer may encounter in applying H-infinity control theory and to clear up some misconceptions about H-infinity theory like high-gain controller and numerical obstacles, etc. An efficient algorithm is used to compute the optimal H-infinity norm. The Glover and Doyle (1988) controller formulas are slightly modified and used to construct an optimal controller without any numerical difficulties.

Chang, B. C.↗

Optimal expression evaluation for data parallel architectures

A data parallel machine represents an array or other composits data structure by allocating one processor per data item. A pointwise operation can be performed between two such arrays in unit time, provided their corresponding elements are allocated in the same processors. If the arrays are not aligned in this fashion, the cost of moving one or both of them is part of the cost of operation. The choice of where to perform the operation then affects this cost. If an expression with several operands is to be evaluated, there may be many choices of where to perform the intermediate operations. An efficient algorithm is given to find the minimum cost way to evaluate an expression, for several different data parallel architectures. The algorithm applies to any architecture in which the metric describing the cost of moving an array has a property called robustness. This encompasses most of the common data parallel communication architectures, including meshes of arbitrary dimension and hypercubes.

Gilbert, John R.↗

Approximate factorization with source terms

A comparative evaluation is made of three methodologies with a view to that which offers the best approximate factorization error. While two of these methods are found to lead to more efficient algorithms in cases where factors which do not contain source terms can be diagonalized, the third method used generates the lowest approximate factorization error. This method may be preferred when the norms of source terms are large, and transient solutions are of interest.

Shih, T. I.-P.↗

A kinematic analysis of the Space Station remote manipulator system (SSRMS)

An efficient reverse analysis of three 6-degree-of-freedom (dof) subchains of the 7-dof SSRMS is presented. The first subchain is formed by locking the seventh joint. The second subchain is formed by locking the second joint, while the third subchain is formed by locking the first joint (the grounded joint is counted as the first joint in the chain). There are a maximum of eight different arm configurations in each of the three subchains, and these were determined by employing a computer-efficient algorithm, which required the rooting of only at most quadratic polynomials. The algorithms were implemented, and the SSRMS was employed in an animated environment to perform and practice a number of useful tasks for Space Station servicing. The locking of the second joint has the advantage in that an operator can choose the orientation of the plane that contains the two longest links so as to avoid collisions with obstacles. However, it has the disadvantage that when the second joint angle equals 0 deg or 180 deg, the manipulator is in a singularity configuration. This plane can also be oriented by specifying the first joint angle, so that the plane can be oriented arbitrarily and, in this, the singularity is avoided.

Crane, Carl D., III↗

Efficient Computation Of Confidence Intervals Of Parameters

Study focuses on obtaining efficient algorithm for estimation of confidence intervals of ML estimates. Four algorithms selected to solve associated constrained optimization problem. Hybrid algorithms, following search and gradient approaches, prove best.

Murphy, Patrick C.↗

Optimal expression evaluation for data parallel architectures

A data parallel machine represents an array or other composite data structure by allocating one processor (at least conceptually) per data item. A pointwise operation can be performed between two such arrays in unit time, provided their corresponding elements are allocated in the same processors. If the arrays are not aligned in this fashion, the cost of moving one or both of them is part of the cost of the operation. The choice of where to perform the operation then affects this cost. If an expression with several operands is to be evaluated, there may be many choices of where to perform the intermediate operations. An efficient algorithm is given to find the minimum-cost way to evaluate an expression, for several different data parallel architectures. This algorithm applies to any architecture in which the metric describing the cost of moving an array is robust. This encompasses most of the common data parallel communication architectures, including meshes of arbitrary dimension and hypercubes. Remarks are made on several variations of the problem, some of which are solved and some of which remain open.

Gilbert, John R.↗

Multi-resolution analysis for ENO schemes

Given an function, u(x), which is represented by its cell-averages in cells which are formed by some unstructured grid, we show how to decompose the function into various scales of variation. This is done by considering a set of nested grids in which the given grid is the finest, and identifying in each locality the coarsest grid in the set from which u(x) can be recovered to a prescribed accuracy. This multi-resolution analysis was applied to essentially non-oscillatory (ENO) schemes in order to advance the solution by one time-step. This is accomplished by decomposing the numerical solution at the beginning of each time-step into levels of resolution, and performing the computation in each locality at the appropriate coarser grid. An efficient algorithm for implementing this program in the 1-D case is presented; this algorithm can be extended to the multi-dimensional case with Cartesian grids.

Harten, Ami↗