SEARCH · Engineering Papers

Results for “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.

SourceResearch connectionFrom yearThrough year

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 271 records · Page 15

All sources NASA NTRS DOE OSTI

NASA NTRS2001

The Langley Parameterized Shortwave Algorithm (LPSA) for Surface Radiation Budget Studies

An efficient algorithm was developed during the late 1980's and early 1990's by W. F. Staylor at NASA/LaRC for the purpose of deriving shortwave surface radiation budget parameters on a global scale. While the algorithm produced results in good agreement with observations, the lack of proper documentation resulted in a weak acceptance by the science community. The primary purpose of this report is to develop detailed documentation of the algorithm. In the process, the algorithm was modified whenever discrepancies were found between the algorithm and its referenced literature sources. In some instances, assumptions made in the algorithm could not be justified and were replaced with those that were justifiable. The algorithm uses satellite and operational meteorological data for inputs. Most of the original data sources have been replaced by more recent, higher quality data sources, and fluxes are now computed on a higher spatial resolution. Many more changes to the basic radiation scheme and meteorological inputs have been proposed to improve the algorithm and make the product more useful for new research projects. Because of the many changes already in place and more planned for the future, the algorithm has been renamed the Langley Parameterized Shortwave Algorithm (LPSA).

Gupta, Shashi K.↗

NASA NTRS2003

A Fast Implementation of the ISOCLUS Algorithm

Unsupervised clustering is a fundamental building block in numerous image processing applications. One of the most popular and widely used clustering schemes for remote sensing applications is the ISOCLUS algorithm, which is based on the ISODATA method. The algorithm is given a set of n data points in d-dimensional space, an integer k indicating the initial number of clusters, and a number of additional parameters. The general goal is to compute the coordinates of a set of cluster centers in d-space, such that those centers minimize the mean squared distance from each data point to its nearest center. This clustering algorithm is similar to another well-known clustering method, called k-means. One significant feature of ISOCLUS over k-means is that the actual number of clusters reported might be fewer or more than the number supplied as part of the input. The algorithm uses different heuristics to determine whether to merge lor split clusters. As ISOCLUS can run very slowly, particularly on large data sets, there has been a growing .interest in the remote sensing community in computing it efficiently. We have developed a faster implementation of the ISOCLUS algorithm. Our improvement is based on a recent acceleration to the k-means algorithm of Kanungo, et al. They showed that, by using a kd-tree data structure for storing the data, it is possible to reduce the running time of k-means. We have adapted this method for the ISOCLUS algorithm, and we show that it is possible to achieve essentially the same results as ISOCLUS on large data sets, but with significantly lower running times. This adaptation involves computing a number of cluster statistics that are needed for ISOCLUS but not for k-means. Both the k-means and ISOCLUS algorithms are based on iterative schemes, in which nearest neighbors are calculated until some convergence criterion is satisfied. Each iteration requires that the nearest center for each data point be computed. Naively, this requires O(kn) time, where k denotes the current number of centers. Traditional techniques for accelerating nearest neighbor searching involve storing the k centers in a data structure. However, because of the iterative nature of the algorithm, this data structure would need to be rebuilt with each new iteration. Our approach is to store the data points in a kd-tree data structure. The assignment of points to nearest neighbors is carried out by a filtering process, which successively eliminates centers that can not possibly be the nearest neighbor for a given region of space. This algorithm is significantly faster, because large groups of data points can be assigned to their nearest center in a single operation. Preliminary results on a number of real Landsat datasets show that our revised ISOCLUS-like scheme runs about twice as fast.

Memarsadeghi, Nargess↗

NASA NTRS2005

Motion Cueing Algorithm Development: New Motion Cueing Program Implementation and Tuning

A computer program has been developed for the purpose of driving the NASA Langley Research Center Visual Motion Simulator (VMS). This program includes two new motion cueing algorithms, the optimal algorithm and the nonlinear algorithm. A general description of the program is given along with a description and flowcharts for each cueing algorithm, and also descriptions and flowcharts for subroutines used with the algorithms. Common block variable listings and a program listing are also provided. The new cueing algorithms have a nonlinear gain algorithm implemented that scales each aircraft degree-of-freedom input with a third-order polynomial. A description of the nonlinear gain algorithm is given along with past tuning experience and procedures for tuning the gain coefficient sets for each degree-of-freedom to produce the desired piloted performance. This algorithm tuning will be needed when the nonlinear motion cueing algorithm is implemented on a new motion system in the Cockpit Motion Facility (CMF) at the NASA Langley Research Center.

Houck, Jacob A.↗

NASA NTRS2005

Motion Cueing Algorithm Development: Human-Centered Linear and Nonlinear Approaches

While the performance of flight simulator motion system hardware has advanced substantially, the development of the motion cueing algorithm, the software that transforms simulated aircraft dynamics into realizable motion commands, has not kept pace. Prior research identified viable features from two algorithms: the nonlinear "adaptive algorithm", and the "optimal algorithm" that incorporates human vestibular models. A novel approach to motion cueing, the "nonlinear algorithm" is introduced that combines features from both approaches. This algorithm is formulated by optimal control, and incorporates a new integrated perception model that includes both visual and vestibular sensation and the interaction between the stimuli. Using a time-varying control law, the matrix Riccati equation is updated in real time by a neurocomputing approach. Preliminary pilot testing resulted in the optimal algorithm incorporating a new otolith model, producing improved motion cues. The nonlinear algorithm vertical mode produced a motion cue with a time-varying washout, sustaining small cues for longer durations and washing out large cues more quickly compared to the optimal algorithm. The inclusion of the integrated perception model improved the responses to longitudinal and lateral cues. False cues observed with the NASA adaptive algorithm were absent. The neurocomputing approach was crucial in that the number of presentations of an input vector could be reduced to meet the real time requirement without degrading the quality of the motion cues.

Houck, Jacob A.↗

NASA NTRS2010

Design and Implementation of the Automated Rendezvous Targeting Algorithms for Orion

The Orion vehicle will be designed to perform several rendezvous missions: rendezvous with the ISS in Low Earth Orbit (LEO), rendezvous with the EDS/Altair in LEO, a contingency rendezvous with the ascent stage of the Altair in Low Lunar Orbit (LLO) and a contingency rendezvous in LLO with the ascent and descent stage in the case of an aborted lunar landing. Therefore, it is not difficult to realize that each of these scenarios imposes different operational, timing, and performance constraints on the GNC system. To this end, a suite of on-board guidance and targeting algorithms have been designed to meet the requirement to perform the rendezvous independent of communications with the ground. This capability is particularly relevant for the lunar missions, some of which may occur on the far side of the moon. This paper will describe these algorithms which are designed to be structured and arranged in such a way so as to be flexible and able to safely perform a wide variety of rendezvous trajectories. The goal of the algorithms is not to merely fly one specific type of canned rendezvous profile. Conversely, it was designed from the start to be general enough such that any type of trajectory profile can be flown.(i.e. a coelliptic profile, a stable orbit rendezvous profile, and a expedited LLO rendezvous profile, etc) all using the same rendezvous suite of algorithms. Each of these profiles makes use of maneuver types which have been designed with dual goals of robustness and performance. They are designed to converge quickly under dispersed conditions and they are designed to perform many of the functions performed on the ground today. The targeting algorithms consist of a phasing maneuver (NC), an altitude adjust maneuver (NH), and plane change maneuver (NPC), a coelliptic maneuver (NSR), a Lambert targeted maneuver, and several multiple-burn targeted maneuvers which combine one of more of these algorithms. The derivation and implementation of each of these algorithms will be discussed in detail, as well and the Rendezvous Targeting "wrapper" which will sequentially tie them all together into a single onboard targeting tool which can produce a final integrated rendezvous trajectory. In a similar fashion, the various guidance modes available for flying out each of these maneuvers will be discussed as well. This paradigm of having the onboard guidance & targeting capability described above is different than the way the Space Shuttle has operated thus far. As a result, a discussion of these differences in terms of operations and ground and crew intervention will also be discussed. However, the general framework of how the mission designers on the ground first perform all mission design and planning functions, and then uplink that burn plan to the vehicle ensures that the ground will be involved to ensure safety and reliability. The only real difference is which of these functions will be done onboard vs. on the ground as done currently. Finally, this paper will describe the performance of each of these algorithms individually as well as the entire suite of algorithms as applied to the Orion ISS and EDS/Altair rendezvous missions in LEO. These algorithms have been incorporated in both a Linear Covariance environment and a Monte Carlo environment and the results of these dispersion analyses will be presented in the paper as well.

DSouza, Christopher↗

NASA NTRS2010

Synthesis of Greedy Algorithms Using Dominance Relations

Greedy algorithms exploit problem structure and constraints to achieve linear-time performance. Yet there is still no completely satisfactory way of constructing greedy algorithms. For example, the Greedy Algorithm of Edmonds depends upon translating a problem into an algebraic structure called a matroid, but the existence of such a translation can be as hard to determine as the existence of a greedy algorithm itself. An alternative characterization of greedy algorithms is in terms of dominance relations, a well-known algorithmic technique used to prune search spaces. We demonstrate a process by which dominance relations can be methodically derived for a number of greedy algorithms, including activity selection, and prefix-free codes. By incorporating our approach into an existing framework for algorithm synthesis, we demonstrate that it could be the basis for an effective engineering method for greedy algorithms. We also compare our approach with other characterizations of greedy algorithms.

Nedunuri, Srinivas↗

NASA NTRS2010

Recent Advancements in Lightning Jump Algorithm Work

In the past year, the primary objectives were to show the usefulness of total lightning as compared to traditional cloud-to-ground (CG) networks, test the lightning jump algorithm configurations in other regions of the country, increase the number of thunderstorms within our thunderstorm database, and to pinpoint environments that could prove difficult for any lightning jump configuration. A total of 561 thunderstorms have been examined in the past year (409 non-severe, 152 severe) from four regions of the country (North Alabama, Washington D.C., High Plains of CO/KS, and Oklahoma). Results continue to indicate that the 2 lightning jump algorithm configuration holds the most promise in terms of prospective operational lightning jump algorithms, with a probability of detection (POD) at 81%, a false alarm rate (FAR) of 45%, a critical success index (CSI) of 49% and a Heidke Skill Score (HSS) of 0.66. The second best performing algorithm configuration was the Threshold 4 algorithm, which had a POD of 72%, FAR of 51%, a CSI of 41% and an HSS of 0.58. Because a more complex algorithm configuration shows the most promise in terms of prospective operational lightning jump algorithms, accurate thunderstorm cell tracking work must be undertaken to track lightning trends on an individual thunderstorm basis over time. While these numbers for the 2 configuration are impressive, the algorithm does have its weaknesses. Specifically, low-topped and tropical cyclone thunderstorm environments are present issues for the 2 lightning jump algorithm, because of the suppressed vertical depth impact on overall flash counts (i.e., a relative dearth in lightning). For example, in a sample of 120 thunderstorms from northern Alabama that contained 72 missed events by the 2 algorithm 36% of the misses were associated with these two environments (17 storms).

Schultz, Christopher J.↗

NASA NTRS2005

Conservative Patch Algorithm and Mesh Sequencing for PAB3D

A mesh-sequencing algorithm and a conservative patched-grid-interface algorithm (hereafter Patch Algorithm ) have been incorporated into the PAB3D code, which is a computer program that solves the Navier-Stokes equations for the simulation of subsonic, transonic, or supersonic flows surrounding an aircraft or other complex aerodynamic shapes. These algorithms are efficient, flexible, and have added tremendously to the capabilities of PAB3D. The mesh-sequencing algorithm makes it possible to perform preliminary computations using only a fraction of the grid cells (provided the original cell count is divisible by an integer) along any grid coordinate axis, independently of the other axes. The patch algorithm addresses another critical need in multi-block grid situation where the cell faces of adjacent grid blocks may not coincide, leading to errors in calculating fluxes of conserved physical quantities across interfaces between the blocks. The patch algorithm, based on the Stokes integral formulation of the applicable conservation laws, effectively matches each of the interfacial cells on one side of the block interface to the corresponding fractional cell area pieces on the other side. This approach is comprehensive and unified such that all interface topology is automatically processed without user intervention. This algorithm is implemented in a preprocessing code that creates a cell-by-cell database that will maintain flux conservation at any level of full or reduced grid density as the user may choose by way of the mesh-sequencing algorithm. These two algorithms have enhanced the numerical accuracy of the code, reduced the time and effort for grid preprocessing, and provided users with the flexibility of performing computations at any desired full or reduced grid resolution to suit their specific computational requirements.

Pao, S. P.↗

NASA NTRS2020

Comparison of Cloud Detection Algorithms for Sentinel-2 Imagery

Accurate, automated cloud and cloud shadow detection is a key component of the processing needed to prepare optical satellite imagery for scientific analysis. Many existing cloud detection algorithms rely on temperature information to identify clouds, making detection difficult for imagers that lack a thermal band, like Sentinel-2. To get maximum benefit from Sentinel-2 products it is critical to understand which algorithms best identify clouds and their shadows in images. We examined the relative performance of five different cloud-masking algorithms (Sen2Cor, MAJA, LaSRC, Fmask and Tmask) in 6 Sentinel-2 scenes (28 total images) distributed across the Eastern Hemisphere. Expanding on these comparisons, we tested ensemble approaches to improve results. We tested three ensemble approaches to cloud and shadow classification based on the outputs of the five initial algorithms using the cloud masks in: (1) a majority prediction model; (2) a random forests model; and (3) a conditional logic model. Accuracy assessments show a trade-off between omission and commission errors in cloud detection for individual algorithms across all sites, and some algorithms are better at detecting either clouds or cloud shadows. No single algorithm outperforms the others for both clouds and shadows. Aggregating the results from multiple algorithms produces fewer undetected clouds and higher overall accuracy than any single algorithm, with as high as 2.7% improvement over the top-performing algorithm, suggesting an ensemble approach may be the most useful for processing of Sentinel-2 data.

Sentinel-2↗

NASA NTRS2024

Comparison of Multisine Peak Factor Minimization Algorithms for Aircraft System Identification

Two phase-optimized multisine peak factor minimization algorithms are presented and evaluated. The first algorithm minimizes peak factor by iteratively clipping the peaks of generated multisine signals. The second algorithm optimizes peak factor indirectly through minimization of an approximation of the infinity norm of the multisine. Algorithm performance was evaluated as a function of different signal properties, including the number of harmonics, harmonic spacing, and number of snow harmonics (extra harmonics included for further reduction of the peak factor). The two algorithms are compared against results obtained by minimizing peak factor directly using a simplex algorithm, which has been a common approach when designing phase-optimized multisines for system identification flight tests. Sample results show that the clipping and infinity norm algorithms produced multisine signals with comparable peak factors that were lower than that of the simplex algorithm. However, the clipping algorithm runs an order of magnitude faster than the other two algorithms, which also makes it practical to repeat the algorithm multiple times to achieve even lower peak factors.

system identification↗

NASA NTRSDate not supplied

Comparison of Multisine Peak Factor Minimization Algorithms for Aircraft System Identification(Presentation)

flight test↗

DOE OSTI2016

A robust return-map algorithm for general multisurface plasticity

Three new contributions to the field of multisurface plasticity are presented for general situations with an arbitrary number of nonlinear yield surfaces with hardening or softening. A method for handling linearly dependent flow directions is described. A residual that can be used in a line search is defined. An algorithm that has been implemented and comprehensively tested is discussed in detail. Examples are presented to illustrate the computational cost of various components of the algorithm. The overall result is that a single Newton-Raphson iteration of the algorithm costs between 1.5 and 2 times that of an elastic calculation. Examples also illustrate the successful convergence of the algorithm in complicated situations. For example, without using the new contributions presented here, the algorithm fails to converge for approximately 50% of the trial stresses for a common geomechanical model of sedementary rocks, while the current algorithm results in complete success. Since it involves no approximations, the algorithm is used to quantify the accuracy of an efficient, pragmatic, but approximate, algorithm used for sedimentary-rock plasticity in a commercial software package. Furthermore, the main weakness of the algorithm is identified as the difficulty of correctly choosing the set of initially active constraints in the general setting.

15 GEOTHERMAL ENERGY↗

DOE OSTI2018

Generalized radial-return mapping algorithm for anisotropic von Mises plasticity framed in material eigenspace

A computationally efficient integration algorithm for anisotropic plasticity is proposed, which is identified as a generalization of the radial-return mapping algorithm to anisotropy. The algorithm is based upon formulation within the eigenspace of a material anisotropy tensor associated with anisotropic quadratic von Mises (J 2 ) plasticity (also called Hill plasticity), for which it is shown to ensure that the flow rule remains associative, ie, the normality condition is satisfied. Extension of the algorithm to include anisotropic elasticity (anisotropic elastoplasticity) is further provided, made possible by the identification of a certain fourth-order material tensor dependent on both the elastic and plastic anisotropy. The derivation of the fully elastoplastically anisotropic algorithm involves further complexity, but the resulting algorithm is shown to closely resemble the purely plastically anisotropic one once the appropriate eigenspace is identified. The proposed generalized radial-return algorithm is compared to a classical closest-point projection algorithm, for which it is shown to provide considerable advantage in computational cost. In conclusion, the efficiency, accuracy, and robustness of the algorithm are demonstrated through various illustrative test cases and in the finite element simulation of Taylor impact tests on tantalum.

36 MATERIALS SCIENCE↗

DOE OSTI2017

Families of Graph Algorithms: SSSP Case Study

Single-Source Shortest Paths (SSSP) is a well-studied graph problem. Examples of SSSP algorithms include the original Dijkstra’s algorithm and the parallel Δ-stepping and KLA-SSSP algorithms. In this paper, we use a novel Abstract Graph Machine (AGM) model to show that all these algorithms share a common logic and differ from one another by the order in which they perform work. We use the AGM model to thoroughly analyze the family of algorithms that arises from the common logic. We start with the basic algorithm without any ordering (Chaotic), and then we derive the existing and new algorithms by methodically exploring semantic and spatial ordering of work. Our experimental results show that new derived algorithms show better performance than the existing distributed memory parallel algorithms, especially at higher scales.

distributed-memory graph algorithms↗

DOE OSTI2018

Optimization of stepwise clustering algorithm in backward trajectory analysis

In recent years, the backward trajectory model has been widely used in the research of meteorological and atmospheric environmental quality. This paper presents a comprehensive study on a stepwise clustering analysis algorithm in the clustering process of backward trajectory model and an application of the clustering analysis of single-particle backward trajectory in 2016 in Changchun City. This study starts with an analysis of the original stepwise clustering algorithm and its application to a clustering process of 8784 backward trajectories during 48 h in Changchun City as a benchmark test case. Then, two improvements are made in the algorithm: First, in the process of finding the optimal classification, the algorithm complexity is improved from original O(n 3 ) to O(log(n)*n 2 ) through algorithm improvement. The algorithm performance is enhanced by log(n) times. Next, in the process of re-establishing the classification, the algorithm complexity is improved from the original O(m*n 2 ) to O(m*log(n)*n), that is another algorithm performance improvement by a factor of log(n). Therefore, the accumulative execution efficiency improvement through the algorithm optimization is 2*log(n) times, which has been further verified in the practical application in Changchun City.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2022

Integrating a ponderomotive guiding center algorithm into a quasi-static particle-in-cell code based on azimuthal mode decomposition

High fidelity modeling of plasma based acceleration (PBA) requires the use of three dimensional, fully nonlinear, and kinetic descriptions based on the particle-in-cell (PIC) method. In PBA an intense particle beam or laser (driver) propagates through a tenuous plasma whereby it excites a plasma wave wake. Three-dimensional PIC algorithms based on the quasi-static approximation (QSA) have been successfully applied to efficiently model the interaction between relativistic charged particle beams and plasma. In a QSA PIC algorithm, the plasma response to a charged particle beam or laser driver is calculated based on forces from the driver and self-consistent forces from the QSA form of Maxwell's equations. These fields are then used to advance the charged particle beam or laser forward by a large time step. Since the time step is not limited by the regular Courant-Friedrichs-Lewy (CFL) condition that constrains a standard 3D fully electromagnetic PIC code, a 3D QSA PIC code can achieve orders of magnitude speedup in performance. Recently, a new hybrid QSA PIC algorithm that combines another speedup technique known as an azimuthal Fourier decomposition has been proposed and implemented. This hybrid algorithm decomposes the electromagnetic fields, charge and current density into azimuthal harmonics and only the Fourier coefficients need to be updated, which can reduce the algorithmic complexity of a 3D code to that of a 2D code. Modeling the laser-plasma interaction in a full 3D electromagnetic PIC algorithm is very computationally expensive due the enormous disparity of physical scales to be resolved. In the QSA the laser is modeled using the ponderomotive guiding center (PGC) approach. We describe how to implement a PGC algorithm compatible for the QSA PIC algorithms based on the azimuthal mode expansion. Here this algorithm permits time steps orders of magnitude larger than the cell size and it can be asynchronously parallelized. Details on how this is implemented into the QSA PIC code that utilizes an azimuthal mode expansion, QPAD, are also described. Benchmarks and comparisons between a fully 3D explicit PIC code (OSIRIS), as well as a few examples related to laser wakefield acceleration, are presented.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2015

Generalized and efficient algorithm for computing multipole energies and gradients based on Cartesian tensors

Accurate representation of intermolecular forces has been the central task of classical atomic simulations, known as molecular mechanics. Recent advancements in molecular mechanics models have put forward the explicit representation of permanent and/or induced electric multipole (EMP) moments. The formulas developed so far to calculate EMP interactions tend to have complicated expressions, especially in Cartesian coordinates, which can only be applied to a specific kernel potential function. For example, one needs to develop a new formula each time a new kernel function is encountered. The complication of these formalisms arises from an intriguing and yet obscured mathematical relation between the kernel functions and the gradient operators. Here, I uncover this relation via rigorous derivation and find that the formula to calculate EMP interactions is basically invariant to the potential kernel functions as long as they are of the form f(r), i.e., any Green’s function that depends on inter-particle distance. I provide an algorithm for efficient evaluation of EMP interaction energies, forces, and torques for any kernel f(r) up to any arbitrary rank of EMP moments in Cartesian coordinates. The working equations of this algorithm are essentially the same for any kernel f(r). Recently, a few recursive algorithms were proposed to calculate EMP interactions. Depending on the kernel functions, the algorithm here is about 4–16 times faster than these algorithms in terms of the required number of floating point operations and is much more memory efficient. I show that it is even faster than a theoretically ideal recursion scheme, i.e., one that requires 1 floating point multiplication and 1 addition per recursion step. This algorithm has a compact vector-based expression that is optimal for computer programming. The Cartesian nature of this algorithm makes it fit easily into modern molecular simulation packages as compared with spherical coordinate-based algorithms. A software library based on this algorithm has been implemented in C++11 and has been released.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

DOE OSTI2021

Grand Unification of Quantum Algorithms

Quantum algorithms offer significant speed-ups over their classical counterparts for a variety of problems. The strongest arguments for this advantage are borne by algorithms for quantum search, quantum phase estimation, and Hamiltonian simulation, which appear as subroutines for large families of composite quantum algorithms. A number of these quantum algorithms have recently been tied together by a novel technique known as the quantum singular value transformation (QSVT), which enables one to perform a polynomial transformation of the singular values of a linear operator embedded in a unitary matrix. In the seminal GSLW’19 paper on the QSVT [Gilyén et al., ACM STOC 2019], many algorithms are encompassed, including amplitude amplification, methods for the quantum linear systems problem, and quantum simulation. Here, we provide a pedagogical tutorial through these developments, first illustrating how quantum signal processing may be generalized to the quantum eigenvalue transform, from which the QSVT naturally emerges. Paralleling GSLW’19, we then employ the QSVT to construct intuitive quantum algorithms for search, phase estimation, and Hamiltonian simulation, and also showcase algorithms for the eigenvalue threshold problem and matrix inversion. This overview illustrates how the QSVT is a single framework comprising the three major quantum algorithms, suggesting a grand unification of quantum algorithms.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗