Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “algorithm complexity analysis”

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 235 records · Page 13
All sourcesNASA NTRSDOE OSTI
NASA NTRS2000

Wavelet-Based Interpolation and Representation of Non-Uniformly Sampled Spacecraft Mission Data

A well-documented problem in the analysis of data collected by spacecraft instruments is the need for an accurate, efficient representation of the data set. The data may suffer from several problems, including additive noise, data dropouts, an irregularly-spaced sampling grid, and time-delayed sampling. These data irregularities render most traditional signal processing techniques unusable, and thus the data must be interpolated onto an even grid before scientific analysis techniques can be applied. In addition, the extremely large volume of data collected by scientific instrumentation presents many challenging problems in the area of compression, visualization, and analysis. Therefore, a representation of the data is needed which provides a structure which is conducive to these applications. Wavelet representations of data have already been shown to possess excellent characteristics for compression, data analysis, and imaging. The main goal of this project is to develop a new adaptive filtering algorithm for image restoration and compression. The algorithm should have low computational complexity and a fast convergence rate. This will make the algorithm suitable for real-time applications. The algorithm should be able to remove additive noise and reconstruct lost data samples from images.

Bose, Tamal↗
NASA NTRS2005

High Resolution Aerospace Applications using the NASA Columbia Supercomputer

This paper focuses on the parallel performance of two high-performance aerodynamic simulation packages on the newly installed NASA Columbia supercomputer. These packages include both a high-fidelity, unstructured, Reynolds-averaged Navier-Stokes solver, and a fully-automated inviscid flow package for cut-cell Cartesian grids. The complementary combination of these two simulation codes enables high-fidelity characterization of aerospace vehicle design performance over the entire flight envelope through extensive parametric analysis and detailed simulation of critical regions of the flight envelope. Both packages. are industrial-level codes designed for complex geometry and incorpor.ats. CuStomized multigrid solution algorithms. The performance of these codes on Columbia is examined using both MPI and OpenMP and using both the NUMAlink and InfiniBand interconnect fabrics. Numerical results demonstrate good scalability on up to 2016 CPUs using the NUMAIink4 interconnect, with measured computational rates in the vicinity of 3 TFLOP/s, while InfiniBand showed some performance degradation at high CPU counts, particularly with multigrid. Nonetheless, the results are encouraging enough to indicate that larger test cases using combined MPI/OpenMP communication should scale well on even more processors.

Mavriplis, Dimitri J.↗
NASA NTRS2009

Computing Bounds on Resource Levels for Flexible Plans

A new algorithm efficiently computes the tightest exact bound on the levels of resources induced by a flexible activity plan (see figure). Tightness of bounds is extremely important for computations involved in planning because tight bounds can save potentially exponential amounts of search (through early backtracking and detection of solutions), relative to looser bounds. The bound computed by the new algorithm, denoted the resource-level envelope, constitutes the measure of maximum and minimum consumption of resources at any time for all fixed-time schedules in the flexible plan. At each time, the envelope guarantees that there are two fixed-time instantiations one that produces the minimum level and one that produces the maximum level. Therefore, the resource-level envelope is the tightest possible resource-level bound for a flexible plan because any tighter bound would exclude the contribution of at least one fixed-time schedule. If the resource- level envelope can be computed efficiently, one could substitute looser bounds that are currently used in the inner cores of constraint-posting scheduling algorithms, with the potential for great improvements in performance. What is needed to reduce the cost of computation is an algorithm, the measure of complexity of which is no greater than a low-degree polynomial in N (where N is the number of activities). The new algorithm satisfies this need. In this algorithm, the computation of resource-level envelopes is based on a novel combination of (1) the theory of shortest paths in the temporal-constraint network for the flexible plan and (2) the theory of maximum flows for a flow network derived from the temporal and resource constraints. The measure of asymptotic complexity of the algorithm is O(N O(maxflow(N)), where O(x) denotes an amount of computing time or a number of arithmetic operations proportional to a number of the order of x and O(maxflow(N)) is the measure of complexity (and thus of cost) of a maximumflow algorithm applied to an auxiliary flow network of 2N nodes. The algorithm is believed to be efficient in practice; experimental analysis shows the practical cost of maxflow to be as low as O(N1.5). The algorithm could be enhanced following at least two approaches. In the first approach, incremental subalgorithms for the computation of the envelope could be developed. By use of temporal scanning of the events in the temporal network, it may be possible to significantly reduce the size of the networks on which it is necessary to run the maximum-flow subalgorithm, thereby significantly reducing the time required for envelope calculation. In the second approach, the practical effectiveness of resource envelopes in the inner loops of search algorithms could be tested for multi-capacity resource scheduling. This testing would include inner-loop backtracking and termination tests and variable and value-ordering heuristics that exploit the properties of resource envelopes more directly.

Muscvettola, Nicola↗
NASA NTRSDate not supplied

Toward Adjoint-Based Aeroacoustic Optimization for Propeller and Rotorcraft Applications

The goal of the present project is to build a multidisciplinary, rapid, robust, and accurate computational tool to optimize wing-mounted propeller designs. The full Farassat’s formulation F1Afor aeroacoustic analysis is implemented in the open-source software SU2.This extension enables the prediction of far-field noise generated by moving sources. The formulation is verified, for a stationary and rotating sphere in a wind tunnel and for a tiltrotor in forward flight, by comparing the acoustic predictions ofSU2 with the predictions computed by NASA’s aeroacoustics code ANOPP2. The algorithmic differentiation capability of SU2 provides discretely consistent, adjoint-based sensitivity analysis for this formulation. The adjoint-based sensitivities are verified through comparison with complex-step sensitivities

R Omur Icke↗
NASA NTRS1996

Development of Collaborative Research Initiatives to Advance the Aerospace Sciences-via the Communications, Electronics, Information Systems Focus Group

The primary goal of the Adaptive Vision Laboratory Research project was to develop advanced computer vision systems for automatic target recognition. The approach used in this effort combined several machine learning paradigms including evolutionary learning algorithms, neural networks, and adaptive clustering techniques to develop the E-MOR.PH system. This system is capable of generating pattern recognition systems to solve a wide variety of complex recognition tasks. A series of simulation experiments were conducted using E-MORPH to solve problems in OCR, military target recognition, industrial inspection, and medical image analysis. The bulk of the funds provided through this grant were used to purchase computer hardware and software to support these computationally intensive simulations. The payoff from this effort is the reduced need for human involvement in the design and implementation of recognition systems. We have shown that the techniques used in E-MORPH are generic and readily transition to other problem domains. Specifically, E-MORPH is multi-phase evolutionary leaming system that evolves cooperative sets of features detectors and combines their response using an adaptive classifier to form a complete pattern recognition system. The system can operate on binary or grayscale images. In our most recent experiments, we used multi-resolution images that are formed by applying a Gabor wavelet transform to a set of grayscale input images. To begin the leaming process, candidate chips are extracted from the multi-resolution images to form a training set and a test set. A population of detector sets is randomly initialized to start the evolutionary process. Using a combination of evolutionary programming and genetic algorithms, the feature detectors are enhanced to solve a recognition problem. The design of E-MORPH and recognition results for a complex problem in medical image analysis are described at the end of this report. The specific task involves the identification of vertebrae in x-ray images of human spinal columns. This problem is extremely challenging because the individual vertebra exhibit variation in shape, scale, orientation, and contrast. E-MORPH generated several accurate recognition systems to solve this task. This dual use of this ATR technology clearly demonstrates the flexibility and power of our approach.

Knasel, T. Michael↗
DOE OSTI2019

Computing the small-scale galaxy power spectrum and bispectrum in configuration space

ABSTRACT We present a new class of estimators for computing small-scale power spectra and bispectra in configuration space via weighted pair and triple counts, with no explicit use of Fourier transforms. Particle counts are truncated at $R_0\sim 100\, h^{-1}\, \mathrm{Mpc}$ via a continuous window function, which has negligible effect on the measured power spectrum multipoles at small scales. This gives a power spectrum algorithm with complexity $\mathcal {O}(NnR_0^3)$ (or $\mathcal {O}(Nn^2R_0^6)$ for the bispectrum), measuring N galaxies with number density n. Our estimators are corrected for the survey geometry and have neither self-count contributions nor discretization artefacts, making them ideal for high-k analysis. Unlike conventional Fourier-transform-based approaches, our algorithm becomes more efficient on small scales (since a smaller R0 may be used), thus we may efficiently estimate spectra across k-space by coupling this method with standard techniques. We demonstrate the utility of the publicly available power spectrum algorithm by applying it to BOSS DR12 simulations to compute the high-k power spectrum and its covariance. In addition, we derive a theoretical rescaled-Gaussian covariance matrix, which incorporates the survey geometry and is found to be in good agreement with that from mocks. Computing configuration- and Fourier-space statistics in the same manner allows us to consider joint analyses, which can place stronger bounds on cosmological parameters; to this end we also discuss the cross-covariance between the two-point correlation function and the small-scale power spectrum.

79 ASTRONOMY AND ASTROPHYSICS↗
NASA NTRSDate not supplied

System-Theoretic Analysis of Unsafe Collaborative Control in Teaming Systems

The interactions that occur in human-teaming are inspiring novel aerospace designs aimed at improving how humans and machines, or multiple machines, work together. Unfortunately, current Systems Engineering processes are ill-equipped to handle these complex relationships and are unable to design and assure the safety for these systems. To close part of this gap, this paper introduces a novel system-theoretic analytical process to identify unsafe collaborative control actions. It is part of a broader set of techniques that extend the state-of-the-art in hazard analysis, System Theoretic Process Analysis (STPA), to systematically address collaboration. The method rigorously expresses the different ways multiple commands may be unsafe together. Using Systems Theory, it employs abstraction to manage the combinatorial complexity in enumerating control contributions from multiple collaborating components. An algorithm integrates these concepts into an end-to-end process and is supported by automation to enumerate, refine, prune, and prioritize unsafe combinations of control actions. The output of the method feeds the specification of system requirements to implement safety-guided design starting early in concept development. The process is demonstrated on a manned-unmanned aircraft teaming case study and finds new causal factors that were not previously found in a past hazard analysis of the same system.

System Safety↗
DOE OSTI2020

Large Scale Tensor Factorization via Parallel Sketches

Tensor factorization methods have recently gained increased popularity. A key feature that renders tensors attractive is the ability to directly model multi-relational data. In this work, we propose ParaSketch, a parallel tensor factorization algorithm that enables massive parallelism, to deal with large tensors. The idea is to compress the large tensor into multiple small tensors, decompose each small tensor in parallel, and combine the results to reconstruct the desired latent factors. Prior art in this direction entails potentially very high complexity in the (Gaussian) compression and final combining stages. Adopting sketching matrices for compression, the proposed method enjoys a dramatic reduction in compression complexity, and features a much lighter combining step. Moreover, theoretical analysis shows that the compressed tensors inherit latent identifiability under mild conditions, hence establishing correctness of the overall approach. Numerical experiments corroborate the theory and demonstrate the effectiveness of the proposed algorithm.

block term decomposition↗
NASA NTRS1986

Free vibration and dynamic response analysis of spinning structures

The proposed effort involved development of numerical procedures for efficient solution of free vibration problems of spinning structures. An eigenproblem solution procedure, based on a Lanczos method employing complex arithmetic, was successfully developed. This task involved formulation of the numerical procedure, FORTRAN coding of the algorithm, checking and debugging of software, and implementation of the routine in the STARS program. A graphics package for the E/S PS 300 as well as for the Tektronix terminals was successfully generated and consists of the following special capabilities: (1) a dynamic response plot for the stresses and displacements as functions of time; and (2) a menu driven command module enabling input of data on an interactive basis. Finally, the STARS analysis capability was further improved by implementing the dynamic response analysis package that provides information on nodal deformations and element stresses as a function of time. A number of test cases were run utilizing the currently developed algorithm implemented in the STARS program and such results indicate that the newly generated solution technique is significantly more efficient than other existing similar procedures.

Source record↗
DOE OSTI2021

Reaction paths of methane activation and oxidation of surface intermediates over NiO on Ceria-Zirconia catalysts studied by In-situ FTIR spectroscopy

Methane activation over NiO/Ce 0.82 Zr 0.18 O 2 catalysts synthesized by combustion synthesis is studied by in-situ IR spectroscopy and correlated to the properties and oxygen speciation of the catalyst. Through XRD, H 2 -TPR, and pyridine adsorption followed by FTIR spectroscopy, the reducibility and Lewis acidity of the catalysts are assessed. In-situ FTIR spectroscopy is used to monitor the methane activation on catalyst surfaces. Complex IR features of methane-derived surface species are observed and are attributed to the formation of surface alkyl/alkoxy, aldehyde, formate/carbonate, and aromatic species. A data analysis algorithm is developed to evaluate the evolution of different surface species over time. The formation of formate and carbonate species is driven by adsorbed surface oxygen, while less reactive oxygen species associated with NiO allow for the production of aromatics and alkoxy intermediates. Finally, by tuning the reducibility and Lewis acidity of the catalyst, the selectivity to alkoxy intermediates can be improved.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2019

Theoretical simulation of a signal for a scheme of an atomic spin gyroscope with optical detection

An operation scheme of an atomic spin gyroscope with optical detection is described, in which two noble gas isotopes, {sup 129} Xe and {sup 131} Xe, are used as carriers of the spin of an atomic nucleus. Based on this scheme, we construct a theoretical model of the dynamics of the spin polarisation of an alkali metal and the magnetisation of a noble gas under conditions of spin-exchange interaction and optical pumping. This model allows one to simulate the pumping and signal readout in the gyroscope scheme. The time dependences of this signal are plotted, the analysis of which shows that the signal has a sophisticated complex structure. Thus, the problem arises of demodulating this signal based on the improvement of demodulation methods and algorithms. (paper)

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
NASA NTRS1991

An X-ray image of the violent interstellar medium in 30 Doradus

A detailed analysis of the X-ray emission from the largest H II region complex in the Local Group, 30 Dor, is presented. Applying a new maximum entropy deconvolution algorithm to the Einstein Observatory data, reveals striking correlations among the X-ray, radio, and optical morphologies of the region, with X-ray-emitting bubbles filling cavities surrounded by H-alpha shells and coextensive diffuse X-ray and radio continuum emission from throughout the region. The total X-ray luminosity in the 0.16-3.5 keV band from an area within 160 pc of the central cluster R136 is about 2 x 10 to the 37th ergs/sec.

Wang, Q.↗
NASA NTRS1993

Analysis of hyper-spectral AVIRIS image data over a mixed-conifer forest in Maine

An introduction to some of the potential uses of hyperspectral data for ecosystem analysis is presented. The examples given are derived from a digital dataset acquired over a sub-boreal forest in central Maine in 1990 by the NASA-JPL Airborne Visible and Infrared Imaging Spectrometer (AVIRIS) instrument gathers data from 400 to 2500 nm in 224 channels at bandwidths of approximately 10 nm. As a preview to the uses of the hyperspectral data, several products from this dataset were extracted. They range from the traditional false color composite made from simulated Thematic Mapper bands and the well known normalized difference vegetation index to much more exotic products such as fractions of vegetation, soil and shade based on linear spectral mixing models and estimates of the leaf water content at the landscape level derived using spectrum-matching techniques. Our research and that of many others indicates that the hyperspectral datasets carry much important information which is only beginning to be understood. This analysis gives an initial indication of the utility of hyperspectral data. Much work still remains to be done in algorithm development and in understanding the physics behind the complex information signal carried in the hyperspectral datasets. This work must be carried out to provide the fullest science support for high spectral resolution data to be acquired by many of the instruments to be launched as part of the Earth Observing System program in the mid-1990's.

Lawrence, William T.↗
NASA NTRS2009

Sequential Principal Component Analysis -An Optimal and Hardware-Implementable Transform for Image Compression

This paper presents the JPL-developed Sequential Principal Component Analysis (SPCA) algorithm for feature extraction / image compression, based on "dominant-term selection" unsupervised learning technique that requires an order-of-magnitude lesser computation and has simpler architecture compared to the state of the art gradient-descent techniques. This algorithm is inherently amenable to a compact, low power and high speed VLSI hardware embodiment. The paper compares the lossless image compression performance of the JPL's SPCA algorithm with the state of the art JPEG2000, widely used due to its simplified hardware implementability. JPEG2000 is not an optimal data compression technique because of its fixed transform characteristics, regardless of its data structure. On the other hand, conventional Principal Component Analysis based transform (PCA-transform) is a data-dependent-structure transform. However, it is not easy to implement the PCA in compact VLSI hardware, due to its highly computational and architectural complexity. In contrast, the JPL's "dominant-term selection" SPCA algorithm allows, for the first time, a compact, low-power hardware implementation of the powerful PCA algorithm. This paper presents a direct comparison of the JPL's SPCA versus JPEG2000, incorporating the Huffman and arithmetic coding for completeness of the data compression operation. The simulation results show that JPL's SPCA algorithm is superior as an optimal data-dependent-transform over the state of the art JPEG2000. When implemented in hardware, this technique is projected to be ideally suited to future NASA missions for autonomous on-board image data processing to improve the bandwidth of communication.

Duong, Tuan A.↗
DOE OSTI2022

Three-dimensional imaging of grain boundaries via quantitative fluorescence X-ray tomography analysis

Abstract Three-dimensional visualization of material composition within multiple grains and across complex networks of grain boundaries at nanoscales can provide new insight into the structure evolution and emerging functional properties of the material for diverse applications. Here, using nanoscale scanning X-ray fluorescence tomography, coupled with an advanced self-absorption correction algorithm developed in this work, we analyze the three-dimensional gain distributions and compositions in a Ce 0.8 Gd 0.2 O 2-δ -CoFe 2 O 4 mixed ionic-electronic conductor system with high accuracy and statistical significance. Our systematic investigation reveals an additional emergent phase and uncovers highly intriguing composition stability ranges for the multiple material phases within this system. The presented visualization of composition variations across complex interfaces, supported by our quantitative composition analysis, discloses mechanistic pathways of the diverse phase transformations occurring in the material synthesis, providing insights for the optimization of transport properties in the mixed ionic-electronic conductor system.

36 MATERIALS SCIENCE↗
DOE OSTI2019

DiaMonD: An Integrated Multifaceted Approach to Mathematics at the Interfaces of Data, Models, and Decisions

DiaMonD is a multi-institutional DOE MMICC effort that aims to address the challenges of end-to-end, data-to-decisions modeling and simulation for complex computational science and engineering problems in a unified, systematic, and integrated fashion. Institutions involved are Colorado State, Florida State, Los Alamos, MIT, Oak Ridge, Stanford, and UT-Austin. The goals of DiaMonD are (1) to develop advanced mathematical methods and analysis for multimodel, multiphysics, multiscale model problems driven by frontier DOE applications, including those in subsurface energy and environmental flows, materials for energy storage and conversion, and ice sheet dynamics; (2) to create theory and algorithms for integrated inversion, optimization, and uncertainty quantification for these complex problems; and (3) to disseminate the philosophy of an integrated end-to-end, data-to-decisions approach to modeling and simulation of complex problems to the broader applied math and computational science communities through workshops and other outreach.

42 ENGINEERING↗
NASA NTRS1978

Sorting on STAR

Timing comparisons are given for three sorting algorithms written for the CDC STAR computer. One algorithm is Hoare's (1962) Quicksort, which is the fastest or nearly the fastest sorting algorithm for most computers. A second algorithm is a vector version of Quicksort that takes advantage of the STAR's vector operations. The third algorithm is an adaptation of Batcher's (1968) sorting algorithm, which makes especially good use of vector operations but has a complexity of N(log N)-squared as compared with a complexity of N log N for the Quicksort algorithms. In spite of its worse complexity, Batcher's sorting algorithm is competitive with the serial version of Quicksort for vectors up to the largest that can be treated by STAR. Vector Quicksort outperforms the other two algorithms and is generally preferred. These results indicate that unusual instruction sets can introduce biases in program execution time that counter results predicted by worst-case asymptotic complexity analysis.

Stone, H. S.↗