Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “generalized 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 55 records · Page 3

Reliable algorithm for modal decomposition

This paper describes a reliable, general algorithm for modal decomposition in real arithmetic and its use in analyzing and synthesizing control logic for linear dynamic systems. The numerical difficulties are described associated with computing the Jordan canonical form when the system has repeated, or nearly repeated, eigenvalues. A new algorithm is described that satisfactorily solves these numerical difficulties. The relation and extension to related numerical analysis research are discussed to clarify the reliability of the techniques. Finally, its implementation as a practical modal decomposition method for efficiently computing the matrix exponential, transfer functions, and frequency response is also described.

Walker, Robert A.↗

Mixture densities, maximum likelihood, and the EM algorithm

The problem of estimating the parameters which determine a mixture density is reviewed as well as maximum likelihood estimation for it. A particular iterative procedure for numerically approximating maximum likelihood estimates for mixture density problems is considered. This EM algorithm, is a specialization to the mixture density context of a general algorithm of the same name used to approximate maximum likelihood estimates for incomplete data problems. The formulation and theoretical and practical properties of the EM algorithm for mixture densities are discussed focussing in particular on mixtures of densities from exponential families.

Redner, R. A.↗

Improved algorithms for mapping pipelined and parallel computations

Recent work on the problem of mapping pipelined or parallel computations onto linear array, shared memory, and host-satellite systems is extended. It is shown how these problems can be solved even more efficiently when computation module execution times are bounded from below, intermodule communication times are bounded from above, and the processors satisfy certain homogeneity constraints. The improved algorithms have significantly lower time and space complexities than the more general algorithms: in one case, an O(nm3) time algorithm for mapping m modules onto n processors is replaced with an O(nm log m) time algorithm, and the space requirements are reduced from O(nm2) to O(m). Run-time complexity is reduced further with parallel mapping algorithms based on these improvements, which run on the architectures for which they create mappings.

Nicol, David M.↗

A parameter-estimation subroutine package

Estimation subroutine package comprises fast, efficient, and simple least-squares data-processing algorithms for use in orbit determination and related analyses. Very reliable and general algorithms have been documented. Package contains collection of streamlined subroutines that can be used to solve large variety of parameter-estimation and filtering problems. Special routines are included for problems with colored process noise and covariance (factor) mapping.

Bierman, G.↗

Improvement of Aerosol Optical Depth Retrieval from MODIS Spectral Reflectance over the Global Ocean Using New Aerosol Models Archived from AERONET Inversion Data and Tri-axial Ellipsoidal Dust Database

New over-ocean aerosol models are developed by integrating the inversion data from the Aerosol Robotic Network (AERONET) sun/sky radiometers with a database for the optical properties of tri-axial ellipsoid particles. The new aerosol models allow more accurate retrieval of aerosol optical depth (AOD) from the Moderate Resolution Imaging Spectroradiometer (MODIS) in the case of high AOD (AOD greater than 0.3). The aerosol models are categorized by using the fine-mode fraction (FMF) at 550 nm and the singlescattering albedo (SSA) at 440 nm from the AERONET inversion data to include a variety of aerosol types found around the globe. For each aerosol model, the changes in the aerosol optical properties (AOPs) as functions of AOD are considered to better represent aerosol characteristics. Comparisons of AODs between AERONET and MODIS for the period from 2003 to 2010 show that the use of the new aerosol models enhances the AOD accuracy with a Pearson coefficient of 0.93 and a regression slope of 0.99 compared to 0.92 and 0.85 calculated using the MODIS Collection 5 data. Moreover, the percentage of data within an expected error of +/-(0.03 + 0.05xAOD) is increased from 62 percent to 64 percent for overall data and from 39 percent to 51 percent for AOD greater than 0.3. Errors in the retrieved AOD are further characterized with respect to the Angstrom exponent (AE), scattering angle, SSA, and air mass factor (AMF). Due to more realistic AOPs assumptions, the new algorithm generally reduces systematic errors in the retrieved AODs compared with the current operational algorithm. In particular, the underestimation of fine-dominated AOD and the scattering angle dependence of dust-dominated AOD are significantly mitigated as results of the new algorithm's improved treatment of aerosol size distribution and dust particle nonsphericity.

aerosol optical depth↗

A General Event Location Algorithm with Applications to Eclispe and Station Line-of-Sight

A general-purpose algorithm for the detection and location of orbital events is developed. The proposed algorithm reduces the problem to a global root-finding problem by mapping events of interest (such as eclipses, station access events, etc.) to continuous, differentiable event functions. A stepping algorithm and a bracketing algorithm are used to detect and locate the roots. Examples of event functions and the stepping/bracketing algorithms are discussed, along with results indicating performance and accuracy in comparison to commercial tools across a variety of trajectories.

Parker, Joel J. K.↗

A General Event Location Algorithm with Applications to Eclipse and Station Line-of-Sight

A general-purpose algorithm for the detection and location of orbital events is developed. The proposed algorithm reduces the problem to a global root-finding problem by mapping events of interest (such as eclipses, station access events, etc.) to continuous, differentiable event functions. A stepping algorithm and a bracketing algorithm are used to detect and locate the roots. Examples of event functions and the stepping/bracketing algorithms are discussed, along with results indicating performance and accuracy in comparison to commercial tools across a variety of trajectories.

Parker, Joel J. K.↗

An Evaluation of a Flight Deck Interval Management Algorithm Including Delayed Target Trajectories

NASA's first Air Traffic Management (ATM) Technology Demonstration (ATD-1) was created to facilitate the transition of mature air traffic management technologies from the laboratory to operational use. The technologies selected for demonstration are the Traffic Management Advisor with Terminal Metering (TMA-TM), which provides precise timebased scheduling in the terminal airspace; Controller Managed Spacing (CMS), which provides controllers with decision support tools enabling precise schedule conformance; and Interval Management (IM), which consists of flight deck automation that enables aircraft to achieve or maintain precise in-trail spacing. During high demand operations, TMA-TM may produce a schedule and corresponding aircraft trajectories that include delay to ensure that a particular aircraft will be properly spaced from other aircraft at each schedule waypoint. These delayed trajectories are not communicated to the automation onboard the aircraft, forcing the IM aircraft to use the published speeds to estimate the target aircraft's estimated time of arrival. As a result, the aircraft performing IM operations may follow an aircraft whose TMA-TM generated trajectories have substantial speed deviations from the speeds expected by the spacing algorithm. Previous spacing algorithms were not designed to handle this magnitude of uncertainty. A simulation was conducted to examine a modified spacing algorithm with the ability to follow aircraft flying delayed trajectories. The simulation investigated the use of the new spacing algorithm with various delayed speed profiles and wind conditions, as well as several other variables designed to simulate real-life variability. The results and conclusions of this study indicate that the new spacing algorithm generally exhibits good performance; however, some types of target aircraft speed profiles can cause the spacing algorithm to command less than optimal speed control behavior.

Swieringa, Kurt A.↗

An intrinsically n-dimensional generalized flux vector splitting implicit finite element Euler algorithm

A generalized flux-vector splitting implicit Galerkin finite-element algorithm for the Euler equations in curvilinear coordinates for ideal and reacting gases is derived. For an arbitrary equation of state, the curvilinear-coordinate flux vector is split in kinematic and kinetic components, and the associated jacobian matrix eigenvalues explicitly depend on the metric data. After directional semidiscretization, the terminal ordinary differential-equation system is solved via a nonlinearly stable implicit Runge-Kutta scheme in concert with an accurate tensor matrix product factorization. The results for selected two-dimensional supersonic and axisymmetric hypersonic flows validate the algorithm and verify its robustness for curvilinear-coordinate computations. The evolution towards a steady state is achieved for large Courant numbers without indication of numerical instabilities.

Iannelli, G. S.↗

An extension of the QZ algorithm for solving the generalized matrix eigenvalue problem

This algorithm is an extension of Moler and Stewart's QZ algorithm with some added features for saving time and operations. Also, some additional properties of the QR algorithm which were not practical to implement in the QZ algorithm can be generalized with the combination shift QZ algorithm. Numerous test cases are presented to give practical application tests for algorithm. Based on results, this algorithm should be preferred over existing algorithms which attempt to solve the class of generalized eigenproblems where both matrices are singular or nearly singular.

Ward, R. C.↗

Deep Learning Method for Detecting Precursors to Adverse Events

With the recent advancements in Deep Learning methods, the ability to model large complex heterogeneous data sets are fundamentally changing industry and research. Coupled with hardware improvements, and ease of implementation, a wide variety of deep neural network architectures can quickly be developed to solve a sweeping range of problems such as: object detection in images, automatic healthcare diagnosis using heterogenous data sources, real time language translating and sentence prediction, upscaling low resolution images, and forecasting of multivariate timeseries. Generally, many of these architectures outperform classical machine learning approaches in their respective tasks, however, this typically comes at a cost of interpretability. These black box algorithms generally suffer from lack of transparency in both model complexity as well as the rationale behind the prediction. This lack of comprehension, is driving an emerging area of interest in “Explainable AI”. An algorithm called: “Deep Temporal Multiple Instance Learning”1 was a recently developed to identify precursors to adverse events and has been applied in the aviation domain. The deep learning architecture is designed to capture the evolution of the probability of the outcome over the time preceding the adverse event using a multiple instance learning approach as illustrated in Figure 1. Precursors are defined when the probability of the event has exceeded a threshold at some point in the timeseries, at which point, a sensitivity analysis is performed to determine contributing factors. The contributing factors are used to explain and define the precursor during the periods where the probability score is high. The identified contributing factors are then presented to subject matter experts to provide objective insights into the leading factors associated with the particular adverse event. The algorithm has been tested on flight data from a commercial airline and has the ability to discover precursors to known adverse events that take the form of safety critical operations, such as unstable approach events on final approach. Apart from detecting precursors to adverse events, the converse can also be leveraged to discover corrective actions. These positive actions manifest themselves as periods in the timeseries when the precursor score has been lowered from an elevated state; meaning that if the system had been left uncorrected, it would have eventually reached the adverse event state. Characterizing these state changes can help identify successful interventions that may not have been known before. Policy makers and procedure designers can use this additional knowledge to craft more safety and efficient resilient procedures for future operations and therefore improve the overall performance of the National Airspace.

Matthews, Bryan L.↗

Structural factoring approach for analyzing stochastic networks

The problem of finding the distribution of the shortest path length through a stochastic network is investigated. A general algorithm for determining the exact distribution of the shortest path length is developed based on the concept of conditional factoring, in which a directed, stochastic network is decomposed into an equivalent set of smaller, generally less complex subnetworks. Several network constructs are identified and exploited to reduce significantly the computational effort required to solve a network problem relative to complete enumeration. This algorithm can be applied to two important classes of stochastic path problems: determining the critical path distribution for acyclic networks and the exact two-terminal reliability for probabilistic networks. Computational experience with the algorithm was encouraging and allowed the exact solution of networks that have been previously analyzed only by approximation techniques.

Hayhurst, Kelly J.↗

Modified Recursive Hierarchical Segmentation of Data

An algorithm and a computer program that implements the algorithm that performs recursive hierarchical segmentation (RHSEG) of data have been developed. While the current implementation is for two-dimensional data having spatial characteristics (e.g., image, spectral, or spectral-image data), the generalized algorithm also applies to three-dimensional or higher dimensional data and also to data with no spatial characteristics. The algorithm and software are modified versions of a prior RHSEG algorithm and software, the outputs of which often contain processing-window artifacts including, for example, spurious segmentation-image regions along the boundaries of processing-window edges.

Tilton, James C.↗

An Arbitrary First Order Theory Can Be Represented by a Program: A Theorem

How can we represent knowledge inside a computer? For formalized knowledge, classical logic seems to be the most adequate tool. Classical logic is behind all formalisms of classical mathematics, and behind many formalisms used in Artificial Intelligence. There is only one serious problem with classical logic: due to the famous Godel's theorem, classical logic is algorithmically undecidable; as a result, when the knowledge is represented in the form of logical statements, it is very difficult to check whether, based on this statement, a given query is true or not. To make knowledge representations more algorithmic, a special field of logic programming was invented. An important portion of logic programming is algorithmically decidable. To cover knowledge that cannot be represented in this portion, several extensions of the decidable fragments have been proposed. In the spirit of logic programming, these extensions are usually introduced in such a way that even if a general algorithm is not available, good heuristic methods exist. It is important to check whether the already proposed extensions are sufficient, or further extensions is necessary. In the present paper, we show that one particular extension, namely, logic programming with classical negation, introduced by M. Gelfond and V. Lifschitz, can represent (in some reasonable sense) an arbitrary first order logical theory.

Hosheleva, Olga↗

An asymptotic analysis of a general class of signal detection algorithms

For applications to the problem of radio frequency interference identification, or in the search for extraterrestrial intelligence, it is important to have a basic understanding of signal detection algorithms. A general technique for assessing the asymptotic sensitivity of a broad class of signal detection algorithms is given. In these algorithms, the decision is based on the value of X sub 1 + X sub 2...+ X sub n where the X sub 1's are obtained by sampling and preliminary processing of a physical process.

Mceliece, R. J.↗

An algorithm for a generalization of the Richardson extrapolation process

The paper presents a recursive method, designated the W exp (m)-algorithm, for implementing a generalization of the Richardson extrapolation process. Compared to the direct solution of the linear sytems of equations defining the extrapolation procedure, this method requires a small number of arithmetic operations and very little storage. The technique is also applied to solve recursively the coefficient problem associated with the rational approximations obtained by applying a d-transformation to power series. In the course of development a new recursive algorithm for implementing a very general extrapolation procedure is introduced, for solving the same problem. A FORTRAN program for the W exp (m)-algorithm is also appended.

Ford, William F.↗