SEARCH · Engineering Papers

Results for “fast 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 559 records · Page 31

All sources NASA NTRS DOE OSTI

NASA NTRS2002

Optimizing Performance of Far-Infrared Photoconductors: New Approach for Interpretation and Calibration of Transient Response

The goals of the proposed work were to determine if final steady state current values for Ge:Ga photoconductors could be predicted from the initial fast component of the transient response and to develop algorithms to operationalize this approach. This required transient measurements as a function of photon background and signal sizes, for both single shot and modulated signals. In addition, we proposed to address the nature of the hook response and the effects of non-equilibrium background fluctuations.

Haegel, Nancy M.↗

NASA NTRS1992

Towards a fast implementation of spectral nested dissection

We describe the spectral nested dissection (SND) algorithm, a new algorithm for computing orderings appropriate for parallel factorization of sparse, symmetric matrices. The algorithm makes use of spectral properties of the Laplacian matrix associated with the given matrix to compute separators. We evaluate the quality of the spectral orderings with respect to several measures: fill, elimination tree height, height and weight balances of elimination trees, and clique tree heights. We use some very large structural analysis problems as test cases and demonstrate on these real applications (such as the Space Shuttle Solid Rocket Booster) that spectral orderings compare quite favorably with commonly used orderings, outperforming them by a wide margin for some of these measures. The only disadvantage of SND is its relatively long execution time. We will present some recent efforts to improve the execution time using both a multilevel and a hybrid approach. We use SND in computing a multifrontal numerical factorization with the different orderings on an eight processor Cray Y-MP and show its effectiveness. We believe that spectral nested dissection is a major breakthrough in terms of generating efficient sparse orderings for parallel machines.

Pothen, Alex↗

NASA NTRS1999

Fast Integer Ambiguity Resolution for GPS Attitude Determination

In this paper, a new algorithm for GPS (Global Positioning System) integer ambiguity resolution is shown. The algorithm first incorporates an instantaneous (static) integer search to significantly reduce the search space using a geometric inequality. Then a batch-type loss function is used to check the remaining integers in order to determine the optimal integer. This batch function represents the GPS sightline vectors in the body frame as the sum of two vectors, one depending on the phase measurements and the other on the unknown integers. The new algorithm has several advantages: it does not require an a-priori estimate of the vehicle's attitude; it provides an inherent integrity check using a covariance-type expression; and it can resolve the integers even when coplanar baselines exist. The performance of the new algorithm is tested on a dynamic hardware simulator.

Lightsey, E. Glenn↗

NASA NTRS1995

Mapping minerals, amorphous materials, environmental materials, vegetation, water, ice and snow, and other materials: The USGS tricorder algorithm

One of the challenges of Imaging Spectroscopy is the identification, mapping and abundance determination of materials, whether mineral, vegetable, or liquid, given enough spectral range, spectral resolution, signal to noise, and spatial resolution. Many materials show diagnostic absorption features in the visual and near infrared region (0.4 to 2.5 micrometers) of the spectrum. This region is covered by the modern imaging spectrometers such as AVIRIS. The challenge is to identify the materials from absorption bands in their spectra, and determine what specific analyses must be done to derive particular parameters of interest, ranging from simply identifying its presence to deriving its abundance, or determining specific chemistry of the material. Recently, a new analysis algorithm was developed that uses a digital spectral library of known materials and a fast, modified-least-squares method of determining if a single spectral feature for a given material is present. Clark et al. made another advance in the mapping algorithm: simultaneously mapping multiple minerals using multiple spectral features. This was done by a modified-least-squares fit of spectral features, from data in a digital spectral library, to corresponding spectral features in the image data. This version has now been superseded by a more comprehensive spectral analysis system called Tricorder.

Clark, Roger N.↗

NASA NTRS1991

Parallel algorithms for placement and routing in VLSI design

The computational requirements for high quality synthesis, analysis, and verification of very large scale integration (VLSI) designs have rapidly increased with the fast growing complexity of these designs. Research in the past has focused on the development of heuristic algorithms, special purpose hardware accelerators, or parallel algorithms for the numerous design tasks to decrease the time required for solution. Two new parallel algorithms are proposed for two VLSI synthesis tasks, standard cell placement and global routing. The first algorithm, a parallel algorithm for global routing, uses hierarchical techniques to decompose the routing problem into independent routing subproblems that are solved in parallel. Results are then presented which compare the routing quality to the results of other published global routers and which evaluate the speedups attained. The second algorithm, a parallel algorithm for cell placement and global routing, hierarchically integrates a quadrisection placement algorithm, a bisection placement algorithm, and the previous global routing algorithm. Unique partitioning techniques are used to decompose the various stages of the algorithm into independent tasks which can be evaluated in parallel. Finally, results are presented which evaluate the various algorithm alternatives and compare the algorithm performance to other placement programs. Measurements are presented on the parallel speedups available.

Brouwer, Randall Jay↗

NASA NTRS2011

Prioritized LT Codes

The original Luby Transform (LT) coding scheme is extended to account for data transmissions where some information symbols in a message block are more important than others. Prioritized LT codes provide unequal error protection (UEP) of data on an erasure channel by modifying the original LT encoder. The prioritized algorithm improves high-priority data protection without penalizing low-priority data recovery. Moreover, low-latency decoding is also obtained for high-priority data due to fast encoding. Prioritized LT codes only require a slight change in the original encoding algorithm, and no changes at all at the decoder. Hence, with a small complexity increase in the LT encoder, an improved UEP and low-decoding latency performance for high-priority data can be achieved. LT encoding partitions a data stream into fixed-sized message blocks each with a constant number of information symbols. To generate a code symbol from the information symbols in a message, the Robust-Soliton probability distribution is first applied in order to determine the number of information symbols to be used to compute the code symbol. Then, the specific information symbols are chosen uniform randomly from the message block. Finally, the selected information symbols are XORed to form the code symbol. The Prioritized LT code construction includes an additional restriction that code symbols formed by a relatively small number of XORed information symbols select some of these information symbols from the pool of high-priority data. Once high-priority data are fully covered, encoding continues with the conventional LT approach where code symbols are generated by selecting information symbols from the entire message block including all different priorities. Therefore, if code symbols derived from high-priority data experience an unusual high number of erasures, Prioritized LT codes can still reliably recover both high- and low-priority data. This hybrid approach decides not only "how to encode" but also "what to encode" to achieve UEP. Another advantage of the priority encoding process is that the majority of high-priority data can be decoded sooner since only a small number of code symbols are required to reconstruct high-priority data. This approach increases the likelihood that high-priority data is decoded first over low-priority data. The Prioritized LT code scheme achieves an improvement in high-priority data decoding performance as well as overall information recovery without penalizing the decoding of low-priority data, assuming high-priority data is no more than half of a message block. The cost is in the additional complexity required in the encoder. If extra computation resource is available at the transmitter, image, voice, and video transmission quality in terrestrial and space communications can benefit from accurate use of redundancy in protecting data with varying priorities.

Woo, Simon S.↗

NASA NTRS2000

Magnetometer-Only Attitude and Rate Estimates for Spinning Spacecraft

A deterministic algorithm and a Kalman filter for gyroless spacecraft are used independently to estimate the three-axis attitude and rates of rapidly spinning spacecraft using only magnetometer data. In-flight data from the Wide-Field Infrared Explorer (WIRE) during its tumble, and the Fast Auroral Snapshot Explorer (FAST) during its nominal mission mode are used to show that the algorithms can successfully estimate the above in spite of the high rates. Results using simulated data are used to illustrate the importance of accurate and frequent data.

Challa, M.↗

NASA NTRS2019

Machine Learning Based AFP Inspection: A Tool for Characterization and Integration

Automated Fiber Placement (AFP) has become a standard manufacturing technique in the creation of large scale composite structures due to its high production rates. However, the associated rapid layup that accompanies AFP manufacturing has a tendency to induce defects. We forward an inspection system that utilizes machine learning (ML) algorithms to locate and characterize defects from profilometry scans coupled with a data storage system and a user interface (UI) that allows for informed manufacturing. A Keyence LJ-7080 blue light profilometer is used for fast 2D height profiling. After scans are collected, they are process by ML algorithms, displayed to an operator through the UI, and stored in a database. The overall goal of the inspection system is to add an additional tool for AFP manufacturing. Traditional AFP inspection is done manually adding to manufacturing time and being subject to inspector errors or fatigue. For large parts, the inspection process can be cumbersome. The proposed inspection system has the capability of accelerating this process while still keeping a human inspector integrated and in control. This allows for the rapid capability of the automated inspection software and the robustness of a human checking for defects that the system either missed or misclassified.

Sacco, Christopher↗

NASA NTRS2010

Automated Conflict Resolution, Arrival Management and Weather Avoidance for ATM

The paper describes a unified solution to three types of separation assurance problems that occur in en-route airspace: separation conflicts, arrival sequencing, and weather-cell avoidance. Algorithms for solving these problems play a key role in the design of future air traffic management systems such as NextGen. Because these problems can arise simultaneously in any combination, it is necessary to develop integrated algorithms for solving them. A unified and comprehensive solution to these problems provides the foundation for a future air traffic management system that requires a high level of automation in separation assurance. The paper describes the three algorithms developed for solving each problem and then shows how they are used sequentially to solve any combination of these problems. The first algorithm resolves loss-of-separation conflicts and is an evolution of an algorithm described in an earlier paper. The new version generates multiple resolutions for each conflict and then selects the one giving the least delay. Two new algorithms, one for sequencing and merging of arrival traffic, referred to as the Arrival Manager, and the other for weather-cell avoidance are the major focus of the paper. Because these three problems constitute a substantial fraction of the workload of en-route controllers, integrated algorithms to solve them is a basic requirement for automated separation assurance. The paper also reviews the Advanced Airspace Concept, a proposed design for a ground-based system that postulates redundant systems for separation assurance in order to achieve both high levels of safety and airspace capacity. It is proposed that automated separation assurance be introduced operationally in several steps, each step reducing controller workload further while increasing airspace capacity. A fast time simulation was used to determine performance statistics of the algorithm at up to 3 times current traffic levels.

Erzberger, H.↗

NASA NTRS2020

A New Method to Correct the Electrochemical Concentration Cell (ECC) Ozonesonde Time Response and its Implications for "Background Current" and Pump Efficiency

The electrochemical concentration cell (ECC) ozonesonde has been the main instrument for in situ profiling of ozone worldwide; yet, some details of its operation, which contribute to the ozone uncertainty budget, are not well understood. Here, we investigate the time response of the chemical reactions inside the ECC and how corrections can be used to remove some systematic biases. The analysis is based on the understanding that two reaction pathways involving ozone occur inside the ECC that generate electrical currents on two very different timescales. The main fast-reaction pathway with a time constant of about 20 s is due the conversion of iodide to molecular iodine and the generation of two free electrons per ozone molecule. A secondary slow-reaction pathway involving the buffer generates an excess current of about 2 %–10 % with a time constant of about 25 min. This excess current can be interpreted as what has conventionally been considered the “background current”. This contribution can be calculated and removed from the measured current instead of the background current. Here we provide an algorithm to calculate and remove the contribution of the slow-reaction pathway and to correct for the time lag of the fast-reaction pathway. This processing algorithm has been applied to ozonesonde profiles at Costa Rica and during the Central Equatorial Pacific Experiment (CEPEX) as well as to laboratory experiments evaluating the performance of ECC ozonesondes. At Costa Rica, where a 1 % KI, 1/10th buffer solution is used, there is no change in the derived total ozone column; however, in the upper troposphere and lower stratosphere, average reported ozone concentrations increase by up to 7 % and above 30 km decrease by up to 7 %. During CEPEX, where a 1 % KI, full-buffer solution was used, ozone concentrations are increased mostly in the upper troposphere, with no change near the top of the profile. In the laboratory measurements, the processing algorithms have been applied to measurements using the majority of current sensing solutions and using only the stronger pump efficiency correction reported by Johnson et al. (2002). This improves the accuracy of the ECC sonde ozone profiles, especially for low ozone concentrations or large ozone gradients and removes systematic biases relative to the reference instruments. In the surface layer, operational procedures prior to launch, in particular the use of filters, influence how typical gradients above the surface are detected. The correction algorithm may report gradients that are steeper than originally reported, but their uncertainty is strongly influenced by the prelaunch procedures.

electrochemical concentration cell (ECC) ozonesond↗

NASA NTRS1986

Data inversion algorithm development for the hologen occultation experiment

The successful retrieval of atmospheric parameters from radiometric measurement requires not only the ability to do ideal radiometric calculations, but also a detailed understanding of instrument characteristics. Therefore a considerable amount of time was spent in instrument characterization in the form of test data analysis and mathematical formulation. Analyses of solar-to-reference interference (electrical cross-talk), detector nonuniformity, instrument balance error, electronic filter time-constants and noise character were conducted. A second area of effort was the development of techniques for the ideal radiometric calculations required for the Halogen Occultation Experiment (HALOE) data reduction. The computer code for these calculations must be extremely complex and fast. A scheme for meeting these requirements was defined and the algorithms needed form implementation are currently under development. A third area of work included consulting on the implementation of the Emissivity Growth Approximation (EGA) method of absorption calculation into a HALOE broadband radiometer channel retrieval algorithm.

Gordley, Larry L.↗

NASA NTRS2010

The Monotonic Lagrangian Grid for Fast Air-Traffic Evaluation

This paper describes the continued development of a dynamic air-traffic model, ATMLG, intended for rapid evaluation of rules and methods to control and optimize transport systems. The underlying data structure is based on the Monotonic Lagrangian Grid (MLG), which is used for sorting and ordering positions and other data needed to describe N moving bodies, and their interactions. In ATMLG, the MLG is combined with algorithms for collision avoidance and updating aircraft trajectories. Aircraft that are close to each other in physical space are always near neighbors in the MLG data arrays, resulting in a fast nearest-neighbor interaction algorithm that scales as N. In this paper, we use ATMLG to examine how the ability to maintain a required separation between aircraft decreases as the number of aircraft in the volume increases. This requires keeping track of the primary and subsequent collision avoidance maneuvers necessary to maintain a five mile separation distance between all aircraft. Simulation results show that the number of collision avoidance moves increases exponentially with the number of aircraft in the volume.

Alexandrov, Natalia↗

NASA NTRS1986

Solution of elliptic partial differential equations by fast Poisson solvers using a local relaxation factor. 1: One-step method

An algorithm for solving a large class of two- and three-dimensional nonseparable elliptic partial differential equations (PDE's) is developed and tested. It uses a modified D'Yakanov-Gunn iterative procedure in which the relaxation factor is grid-point dependent. It is easy to implement and applicable to a variety of boundary conditions. It is also computationally efficient, as indicated by the results of numerical comparisons with other established methods. Furthermore, the current algorithm has the advantage of possessing two important properties which the traditional iterative methods lack; that is: (1) the convergence rate is relatively insensitive to grid-cell size and aspect ratio, and (2) the convergence rate can be easily estimated by using the coefficient of the PDE being solved.

Chang, S. C.↗

NASA NTRS1988

Fast computation of the multivariable stability margin for real interrelated uncertain parameters

A novel algorithm for computing the multivariable stability margin for checking the robust stability of feedback systems with real parametric uncertainty is proposed. This method eliminates the need for the frequency search involved in another given algorithm by reducing it to checking a finite number of conditions. These conditions have a special structure, which allows a significant improvement on the speed of computations.

Sideris, Athanasios↗

NASA NTRS1990

Attitude determination and calibration using a recursive maximum likelihood-based adaptive Kalman filter

An adaptive Kalman filter design that utilizes recursive maximum likelihood parameter identification is discussed. At the center of this design is the Kalman filter itself, which has the responsibility for attitude determination. At the same time, the identification algorithm is continually identifying the system parameters. The approach is applicable to nonlinear, as well as linear systems. This adaptive Kalman filter design has much potential for real time implementation, especially considering the fast clock speeds, cache memory and internal RAM available today. The recursive maximum likelihood algorithm is discussed in detail, with special attention directed towards its unique matrix formulation. The procedure for using the algorithm is described along with comments on how this algorithm interacts with the Kalman filter.

Kelly, D. A.↗

NASA NTRS1994

Accelerated panel methods using the fast multipole method

Panel methods are commonly used in computational fluid dynamics for the solution of potential flow problems. The methods are a numerical technique based on the surface distribution of singularity elements. The solution is the process of finding the strength of the singularity elements distributed over the body's surface. This process involves the solution of the matrix problem Pq = p' for a set of unknowns q. The Fast Multipole Method is used to directly compute q without using matrix solvers. The algorithm works in O(N) time for N points, a great improvement over standard matrix solvers. In panel methods, the surface of a body is divided into a series of quadrilateral panels. The methods involve the computation of the influence of all other panels on each individual panel. The influence is based on the surface distribution, though this can be approximated by the area for distant panels. An alternative approximation, though with arbitrary accuracy, is to develop a multipole expansion about the center of the panel to describe the effect of a given panel on distant points in space. The expansion is based on the moments of the panel, thus allow the use of various surface distributions without changing the basic algorithm, just the computation of the various moments. The expansions are then manipulated in a tree walk to develop Taylor series expansions about a point in space which describe the effect of all distant panels on any point within a volume of convergence. The effect of near panels then needs to be computed directly, but the effect of all distant panels can be computed by simply evaluating the resulting expansion. The Fast Multipole Method has been applied to panel methods for the solution of source and doublet distributions. A major feature of the algorithm is that the algorithm does not change to derive the potential and velocity for sources and doublets. The same expansions can be used for both sources and doublets. Since the velocity is related to the potential, and the doublet potential is related to the z-component of the source velocity, all values can be derived from the same expansion by taking a series of partial derivatives. This requires more expansion terms to be kept since terms are lost in the process of taking partial derivatives. Thus to maintain accuracy for the doublet computation, more terms are required than if just evaluating for sources. The resulting Fast Multipole code should then parallelize better than classical panel methods due to the locality of data dependencies found in the Fast Multipole Method. Theoretically the parallelized code should execute in O(log N) time with O(N) processors, though this is not practical. Ongoing work includes implementing the parallel accelerated panel method, including methods to improve the load balancing of the problem by taking advantage of the known geometry of panels, and to encorporate sensitivity analysis into the algorithm.

Leathrum, James F., Jr.↗

NASA NTRS2018

Validation of Model-Based Prognostics for Pneumatic Valves in a Cryogenic Fueling Demonstration Testbed

Because valves control many critical operations, they are prime candidates for deployment of prognostic algorithms. But, similar to the situation with most other components, examples of failures experienced in the field are hard to come by. This lack of data impacts the ability to test and validate prognostic algorithms. A solution sometimes employed to overcome this shortcoming is to perform run to failure experiments in a lab. However, the mean time to failure of valves is typically very high (possibly lasting decades), preventing evaluation within a reasonable time frame. Therefore, a mechanism to observe development of fault signatures considerably faster is sought. Described here is a testbed that addresses these issues by allowing the physical injection of leakage faults (which are the most common fault mode) into pneumatic valves. What makes this testbed stand out is the ability to modulate the magnitude of the fault almost arbitrarily fast. With that, the performance of end-of-life estimation algorithms can be tested. Further, the testbed is mobile and can be connected to valves in the field. This mobility helps to bring the overall process of prognostic algorithm development for this valve a step closer to validation. The paper illustrates the development of a model-based prognostic approach that uses data from the testbed for partial validation.

Kulkarni, Chetan S.↗

NASA NTRS2020

Experimental Validation of Model-Based Prognostics for Pneumatic Valves

Because valves control many critical operations, they are prime candidates for deployment of prognostic algorithms. But, similar to the situation with most other components, examples of failures experienced in the field are hard to come by. This lack of data impacts the ability to test and validate prognostic algorithms. A solution sometimes employed to overcome this shortcoming is to perform run-to-failure experiments in a lab. However, the mean time to failure of valves is typically very high (possibly lasting decades), preventing evaluation within a reasonable time frame. Therefore, a mechanism to observe development of fault signatures considerably faster is sought. Described here is a testbed that addresses these issues by allowing the physical injection of leakage faults (which are the most common fault mode) into pneumatic valves. What makes this testbed stand out is the ability to modulate the magnitude of the fault almost arbitrarily fast. With that, the performance of end-of-life estimation algorithms can be tested. Further, the testbed is mobile and can be connected to valves in the field. This mobility helps to bring the overall process of prognostic algorithm development for this valve a step closer to validation. The paper illustrates the development of a model-based prognostic approach that uses data from the testbed for partial validation.

Chetan S Kulkarni↗