Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “approximation algorithms”

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 1,477 records · Page 82

Enhancing Monte Carlo proxy applications on GPUs

In Monte Carlo neutron transport simulations, a computational routine commonly known as the ”cross-section lookup” has been identified as being the most computationally expensive part of these applications. A tool which is commonly used as a proxy application for these routines, named ”XSBench”, was created to simulate popular algorithms used in these routines on CPUs. Currently, however, as GPU-based HPC resources have become more widely available, there has been significant interest and efforts invested in moving these traditionally CPU-based simulations to GPUs. Unfortunately, the algorithms commonly used in the cross-section lookup routine were originally devised and developed for CPU-based platforms, and have seen limited study on GPUs to date. Additionally, platforms such as XSBench implement approximations which may have a negligible effect on CPUs, but may be quite impactful to performance on GPUs given the more resource-limited nature of the latter. As a result, we have created VEXS, a new tool for modeling the cross-section lookup routine which removes or at least reduces the approximations made by XSBench in order to provide a more realistic prediction of algorithm performance on GPUs. In this paper, we detail our efforts to remove and reduce these approximations, show the resulting improvement in performance prediction in comparison to a reference production code, Shift, and provide some basic profiling analysis of the resulting application.

Shriver, Forrest↗

Spatial Modulation Improves Performance in CTIS

Suitably formulated spatial modulation of a scene imaged by a computed-tomography imaging spectrometer (CTIS) has been found to be useful as a means of improving the imaging performance of the CTIS. As used here, "spatial modulation" signifies the imposition of additional, artificial structure on a scene from within the CTIS optics. The basic principles of a CTIS were described in "Improvements in Computed- Tomography Imaging Spectrometry" (NPO-20561) NASA Tech Briefs, Vol. 24, No. 12 (December 2000), page 38 and "All-Reflective Computed-Tomography Imaging Spectrometers" (NPO-20836), NASA Tech Briefs, Vol. 26, No. 11 (November 2002), page 7a. To recapitulate: A CTIS offers capabilities for imaging a scene with spatial, spectral, and temporal resolution. The spectral disperser in a CTIS is a two-dimensional diffraction grating. It is positioned between two relay lenses (or on one of two relay mirrors) in a video imaging system. If the disperser were removed, the system would produce ordinary images of the scene in its field of view. In the presence of the grating, the image on the focal plane of the system contains both spectral and spatial information because the multiple diffraction orders of the grating give rise to multiple, spectrally dispersed images of the scene. By use of algorithms adapted from computed tomography, the image on the focal plane can be processed into an image cube a three-dimensional collection of data on the image intensity as a function of the two spatial dimensions (x and y) in the scene and of wavelength (lambda). Thus, both spectrally and spatially resolved information on the scene at a given instant of time can be obtained, without scanning, from a single snapshot; this is what makes the CTIS such a potentially powerful tool for spatially, spectrally, and temporally resolved imaging. A CTIS performs poorly in imaging some types of scenes in particular, scenes that contain little spatial or spectral variation. The computed spectra of such scenes tend to approximate correct values to within acceptably small errors near the edges of the field of view but to be poor approximations away from the edges. The additional structure imposed on a scene according to the present method enables the CTIS algorithms to reconstruct acceptable approximations of the spectral data throughout the scene.

Bearman, Gregory H.↗

Adaptive Metropolis Sampling with Product Distributions

The Metropolis-Hastings (MH) algorithm is a way to sample a provided target distribution pi(z). It works by repeatedly sampling a separate proposal distribution T(x,x') to generate a random walk {x(t)}. We consider a modification of the MH algorithm in which T is dynamically updated during the walk. The update at time t uses the {x(t' less than t)} to estimate the product distribution that has the least Kullback-Leibler distance to pi. That estimate is the information-theoretically optimal mean-field approximation to pi. We demonstrate through computer experiments that our algorithm produces samples that are superior to those of the conventional MH algorithm.

Wolpert, David H.↗

Design Considerations of an Ascent Abort Monitor Algorithm for Use During Service Module Aborts

In support of human rating the Artemis missions, NASA's Orion program requires continuous abort coverage from liftoff through mission destination. During a portion of the ascent trajectory, the currently achievable abort mode is determined by an Orion algorithm using the onboard navigated vehicle state. This ascent abort monitor determines achievability for Orion's Mode 2 abort, Untargeted Abort Splashdown (UAS), by propagating the current vehicle state through ascent abort events to determine sufficient timing to perform the abort and to a ballistic touchdown point to approximate landing location relative to prescribed keep out boundaries. The algorithm was updated for Artemis 2 to allow the capability to limit loads for the majority of ascent. Performance of the algorithm has been demonstrated and verified through dispersed trajectory analysis with emulated flight software, unit testing, and hardware in the loop testing.

Esteban Guzman↗

A new algorithm for microwave delay estimation from water vapor radiometer data

A new algorithm has been developed for the estimation of tropospheric microwave path delays from water vapor radiometer (WVR) data, which does not require site and weather dependent empirical parameters to produce high accuracy. Instead of taking the conventional linear approach, the new algorithm first uses the observables with an emission model to determine an approximate form of the vertical water vapor distribution which is then explicitly integrated to estimate wet path delays, in a second step. The intrinsic accuracy of this algorithm has been examined for two channel WVR data using path delays and stimulated observables computed from archived radiosonde data. It is found that annual RMS errors for a wide range of sites are in the range from 1.3 mm to 2.3 mm, in the absence of clouds. This is comparable to the best overall accuracy obtainable from conventional linear algorithms, which must be tailored to site and weather conditions using large radiosonde data bases. The new algorithm's accuracy and flexibility are indications that it may be a good candidate for almost all WVR data interpretation.

Robinson, S. E.↗

The profile algorithm for microwave delay estimation from water vapor radiometer data

A new algorithm has been developed for the estimation of tropospheric microwave path delays from water vapor radiometer (WVR) data, which does not require site and weather dependent empirical parameters to produce accuracy better than 0.3 cm of delay. Instead of taking the conventional linear approach, the new algorithm first uses the observables with an emission model to determine an approximate form of the vertical water vapor distribution, which is then explicitly integrated to estimate wet path delays in a second step. The intrinsic accuracy of this algorithm, excluding uncertainties caused by the radiometers and the emission model, has been examined for two channel WVR data using path delays and corresponding simulated observables computed from archived radiosonde data. It is found that annual rms errors for a wide range of sites average 0.18 cm in the absence of clouds, 0.22 cm in cloudy weather, and 0.19 cm overall. In clear weather, the new algorithm's accuracy is comparable to the best that can be obtained from conventional linear algorithms, while in cloudy weather it offers a 35 percent improvement.

Robinson, Steven E.↗

Use of Probability Distribution Functions for Discriminating Between Cloud and Aerosol in Lidar Backscatter Data

In this paper we describe the algorithm hat will be used during the upcoming Cloud-Aerosol Lidar and Infrared Pathfinder Satellite Observations (CALIPSO) mission for discriminating between clouds and aerosols detected in two wavelength backscatter lidar profiles. We first analyze single-test and multiple-test classification approaches based on one-dimensional and multiple-dimensional probability density functions (PDFs) in the context of a two-class feature identification scheme. From these studies we derive an operational algorithm based on a set of 3-dimensional probability distribution functions characteristic of clouds and aerosols. A dataset acquired by the Cloud Physics Lidar (CPL) is used to test the algorithm. Comparisons are conducted between the CALIPSO algorithm results and the CPL data product. The results obtained show generally good agreement between the two methods. However, of a total of 228,264 layers analyzed, approximately 5.7% are classified as different types by the CALIPSO and CPL algorithm. This disparity is shown to be due largely to the misclassification of clouds as aerosols by the CPL algorithm. The use of 3-dimensional PDFs in the CALIPSO algorithm is found to significantly reduce this type of error. Dust presents a special case. Because the intrinsic scattering properties of dust layers can be very similar to those of clouds, additional algorithm testing was performed using an optically dense layer of Saharan dust measured during the Lidar In-space Technology Experiment (LITE). In general, the method is shown to distinguish reliably between dust layers and clouds. The relatively few erroneous classifications occurred most often in the LITE data, in those regions of the Saharan dust layer where the optical thickness was the highest.

Liu, Zhaoyan↗

An Efficient, Multi-Layered Crown Delineation Algorithm for Mapping Individual Tree Structure Across Multiple Ecosystems

Deriving individual tree information from discrete return, small footprint LiDAR data may improve forest above ground biomass estimates, and provide tree-level information that is important in many ecological studies. Several crown delineation algorithms have been developed to extract individual tree information from LiDAR point clouds or rasterized canopy height models (CHM), but many of these algorithms have difficulty discriminating between overlapping crowns, and also may fail to detect understory trees. Our approach uses a watershed based delineation of a CHM, which is subsequently refined using the LiDAR point cloud. Individual tree detection was validated with stem mapped field data from the Smithsonian Environmental Research Center (SERC), Maryland, and on a plot and stand level through comparisons of stem density and basal area to delineated metrics at both SERC and a study area in the Sierra Nevada, California. For individual tree detection, the algorithm correctly identified 70% of dominant trees, 58% of co-dominant trees, 35% of intermediate trees and 21% of suppressed trees at SERC. The algorithm had difficulty distinguishing between crowns of small, dense understory trees of approximately the same height. Delineated crown volume alone explained 53% and 84% of the variability in basal area at the SERC and Sierra Nevada sites, respectively. The algorithm produced crown area distributions comparable to diameter at breast height (DBH) size class distributions observed in the field in both study sites. The algorithm detected understory crowns better in the conifer-dominated Sierra Nevada site than in the closed-canopy deciduous site in Maryland. The ability for the algorithm to reproduce both accurate tree size distributions and individual crown geometries in two dissimilar and complex forests suggests great promise for applicability to a wide range of forest systems.

LiDAR↗

A Framework for Error-Bounded Approximate Computing, with an Application to Dot Products

Approximate computing techniques, which trade off the computation accuracy of an algorithm for better performance and energy efficiency, have been successful in reducing computation and power costs in several domains. However, error sensitive applications in high-performance computing are unable to benefit from existing approximate computing strategies that are not developed with guaranteed error bounds. While approximate computing techniques can be developed for individual high-performance computing applications by domain specialists, this often requires additional theoretical analysis and potentially extensive software modification. Hence, the development of low-level error-bounded approximate computing strategies that can be introduced into any high-performance computing application without requiring additional analysis or significant software alterations is desirable. In this paper, we provide a contribution in this direction by proposing a general framework for designing error-bounded approximate computing strategies and apply it to the dot product kernel to develop \bf qdot---an error-bounded approximate dot product kernel. Following the introduction of qdot, here we perform a theoretical analysis that yields a deterministic bound on the relative approximation error introduced by qdot. Empirical tests are performed to illustrate the tightness of the derived error bound and to demonstrate the effectiveness of qdot on a synthetic dataset, as well as two scientific benchmarks---the conjugate gradient (CG) and power methods. In some instances, using qdot for the dot products in CG can result in many components being quantized to half precision without increasing the iteration count required for convergence to the same solution as CG using a double precision dot product.

97 MATHEMATICS AND COMPUTING↗

Assessing barriers and research challenges for automated fault detection and diagnosis technology for small commercial buildings in the United States

Commercial buildings often experience faults that waste energy, decrease occupant comfort, and increase operating costs. For medium and larger commercial buildings (buildings with more than approximately 1000 m 2 [approximately 10,000 ft 2 ] of floor area), studies have shown that automated fault detection and diagnosis (AFDD) tools can help building owners and operators identify and correct faults, improving building performance and producing up to 10% energy savings. However, the existing state of the art in AFDD tools and algorithms poorly serves the needs of commercial buildings less than approximately 1000 m2 (approximately 10,000 ft 2 ). Using the United States market and building stock as a case study, this article characterizes AFDD needs for small commercial buildings, surveys the types of AFDD tools presently available in the market, identifies gaps and barriers to widespread adoption of AFDD technology in small commercial buildings, and makes recommendations for the future research and development of small buildings AFDD technology.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗

Effective matrix model for nuclear physics on a quantum computer

In this project we studied a simplified potential from [1] describing nuclear physics from quark and gluon fields, where spatial degrees of freedom have been integrated over. This potential deals with the phase structure of the strong interaction. We created a matrix representation of the Hamiltonian for this theory using discrete quantum mechanics [2]. We then feed this Hamiltonian to IBM's Qiskit package [3]. We run on IBM's 32-qubit quantum simulator, which approximates the ground state energy using the variational quantum eigensolver (VQE) algorithm [4]. This result is then compared with the exact ground state energy, which we can calculate classically since the matrices we use are still small enough. The bosonic Hamiltonian for a 6-qubit representation took over 1000 Pauli factors to represent fully. To improve our performance, we can look for a more efficient representation of this model's Hamiltonian. We will develop a better variational trial wave function and initial state, as well as include the effect of fermions and heavy quarks on the potential.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Three-dimensional imaging using coherent x rays at grazing incidence geometry

We have developed a three-dimensional coherent diffraction imaging algorithm to retrieve phases of diffraction patterns of samples in grazing incidence small angle x-ray scattering experiments. The algorithm interprets the diffraction patterns using the distorted-wave Born approximation instead of the Born approximation, as in this case, the existence of a reflected beam from the substrate causes the diffraction pattern to deviate significantly from the simple Fourier transform of the object. Detailed computer simulations show that the algorithm works. Verification with real experiments is planned.

Yang, Yi↗

Applying the Dark Target Aerosol Algorithm with Advanced Himawari Imager Observations During the KORUS-AQ Field Campaign

For nearly 2 decades we have been quantitatively observing the Earth's aerosol system from space at one or two times of the day by applying the Dark Target family of algorithms to polar-orbiting satellite sensors, particularly MODIS and VIIRS. With the launch of the Advanced Himawari Imager (AHI) and the Advanced Baseline Imagers (ABIs) into geosynchronous orbits, we have the new ability to expand temporal coverage of the traditional aerosol optical depth (AOD) to resolve the diurnal signature of aerosol loading during daylight hours. The Korean–United States Air Quality (KORUS-AQ) campaign taking place in and around the Korean peninsula during May–June 2016 initiated a special processing of full-disk AHI observations that allowed us to make a preliminary adoption of Dark Target aerosol algorithms to the wavelengths and resolutions of AHI. Here,we describe the adaptation and show retrieval results from AHI for this 2-month period. The AHI-retrieved AOD is collocated in time and space with existing AErosol RObotic NETwork stations across Asia and with collocated Terra and Aqua MODIS retrievals. The new AHI AOD product matches AERONET, and the standard MODIS product does as well, and the agreement between AHI and MODIS retrieved AOD is excellent, as can be expected by maintaining consistency in algorithm architecture and most algorithm assumptions. Furthermore, we show that the new product approximates the AERONET-observed diurnal signature. Examining the diurnal patterns of the new AHI AOD product we find specific areas over land where the diurnal signal is spatially cohesive. For example, in Bangladesh the AOD in-creases by 0.50 from morning to evening, and in northeast China the AOD decreases by 0.25. However, over open ocean the observed diurnal cycle is driven by two artifacts, one associated with solar zenith angles greater than 70t hat may be caused by a radiative transfer model that does not properly represent the spherical Earth and the other artifact associated with the fringes of the 40 degree glint angle mask. This opportunity during KORUS-AQ provides encouragement to move towards an operational Dark Target algorithm for AHI. Future work will need to re-examine masking including snow mask, reevaluate assumed aerosol models for geosynchronous geometry, address the artifacts over the ocean, and investigate size parameter retrieval from the over-ocean algorithm.

Gupta, Pawan↗

Proceedings of the Third International Workshop on Neural Networks and Fuzzy Logic, volume 2

Papers presented at the Neural Networks and Fuzzy Logic Workshop sponsored by the National Aeronautics and Space Administration and cosponsored by the University of Houston, Clear Lake, held 1-3 Jun. 1992 at the Lyndon B. Johnson Space Center in Houston, Texas are included. During the three days approximately 50 papers were presented. Technical topics addressed included adaptive systems; learning algorithms; network architectures; vision; robotics; neurobiological connections; speech recognition and synthesis; fuzzy set theory and application, control and dynamics processing; space applications; fuzzy logic and neural network computers; approximate reasoning; and multiobject decision making.

Culbert, Christopher J.↗

Proceedings of the Third International Workshop on Neural Networks and Fuzzy Logic, volume 1

Documented here are papers presented at the Neural Networks and Fuzzy Logic Workshop sponsored by the National Aeronautics and Space Administration and cosponsored by the University of Houston, Clear Lake. The workshop was held June 1-3, 1992 at the Lyndon B. Johnson Space Center in Houston, Texas. During the three days approximately 50 papers were presented. Technical topics addressed included adaptive systems; learning algorithms; network architectures; vision; robotics; neurobiological connections; speech recognition and synthesis; fuzzy set theory and application, control, and dynamics processing; space applications; fuzzy logic and neural network computers; approximate reasoning; and multiobject decision making.

Culbert, Christopher J.↗

Simulation of three-dimensional compressible viscous flow on the Illiac IV computer

Complicated three-dimensional viscous transonic flows about bodies at high angles of attack are solved on the Illiac IV computer. It is shown that certain approximate forms of the compressible Reynolds-averaged Navier-Stokes equations can be computed about realistic three-dimensional geometries with relative ease on the Illiac IV. The ease and efficiency with which this can be done depend on the approximations made in the basic equations, the choice of the numerical algorithm used for the solution, and the data-base system that controls the data management and identifies and manipulates the vectors. A pencil data-base system is found to be particularly suitable for the approximations and numerical method chosen to produce the results presented. In addition, some comparisons are made of computer predictions with experimental results for various lows about hemisphere-cylinders in both subsonic and supersonic free streams. The same viscous model and numerical model are used, showing good qualitative agreement in the location of separation lines and pressure distributions.

Pulliam, T. H.↗

Advancing-Front Algorithm For Delaunay Triangulation

Efficient algorithm performs Delaunay triangulation to generate unstructured grids for use in computing two-dimensional flows. Once grid generated, one can optionally call upon additional subalgorithm that removes diagonal lines from quadrilateral cells nearly rectangular. Resulting approximately rectangular grid reduces cost per iteration of flow-computing algorithm.

Merriam, Marshal L.↗