Engineering Papers⌕ Search

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.

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

At least 559 records · Page 31
All sourcesNASA NTRSDOE OSTI
NASA NTRS2000

Reconstruction algorithm for polychromatic CT imaging: application to beam hardening correction

This paper presents a new reconstruction algorithm for both single- and dual-energy computed tomography (CT) imaging. By incorporating the polychromatic characteristics of the X-ray beam into the reconstruction process, the algorithm is capable of eliminating beam hardening artifacts. The single energy version of the algorithm assumes that each voxel in the scan field can be expressed as a mixture of two known substances, for example, a mixture of trabecular bone and marrow, or a mixture of fat and flesh. These assumptions are easily satisfied in a quantitative computed tomography (QCT) setting. We have compared our algorithm to three commonly used single-energy correction techniques. Experimental results show that our algorithm is much more robust and accurate. We have also shown that QCT measurements obtained using our algorithm are five times more accurate than that from current QCT systems (using calibration). The dual-energy mode does not require any prior knowledge of the object in the scan field, and can be used to estimate the attenuation coefficient function of unknown materials. We have tested the dual-energy setup to obtain an accurate estimate for the attenuation coefficient function of K2 HPO4 solution.

NASA Center ARC↗
NASA NTRS2004

cWINNOWER algorithm for finding fuzzy dna motifs

The cWINNOWER algorithm detects fuzzy motifs in DNA sequences rich in protein-binding signals. A signal is defined as any short nucleotide pattern having up to d mutations differing from a motif of length l. The algorithm finds such motifs if a clique consisting of a sufficiently large number of mutated copies of the motif (i.e., the signals) is present in the DNA sequence. The cWINNOWER algorithm substantially improves the sensitivity of the winnower method of Pevzner and Sze by imposing a consensus constraint, enabling it to detect much weaker signals. We studied the minimum detectable clique size qc as a function of sequence length N for random sequences. We found that qc increases linearly with N for a fast version of the algorithm based on counting three-member sub-cliques. Imposing consensus constraints reduces qc by a factor of three in this case, which makes the algorithm dramatically more sensitive. Our most sensitive algorithm, which counts four-member sub-cliques, needs a minimum of only 13 signals to detect motifs in a sequence of length N = 12,000 for (l, d) = (15, 4). Copyright Imperial College Press.

Evaluation Studies↗
NASA NTRS2014

NASA Team 2 Sea Ice Concentration Algorithm Retrieval Uncertainty

Satellite microwave radiometers are widely used to estimate sea ice cover properties (concentration, extent, and area) through the use of sea ice concentration (IC) algorithms. Rare are the algorithms providing associated IC uncertainty estimates. Algorithm uncertainty estimates are needed to assess accurately global and regional trends in IC (and thus extent and area), and to improve sea ice predictions on seasonal to interannual timescales using data assimilation approaches. This paper presents a method to provide relative IC uncertainty estimates using the enhanced NASA Team (NT2) IC algorithm. The proposed approach takes advantage of the NT2 calculations and solely relies on the brightness temperatures (TBs) used as input. NT2 IC and its associated relative uncertainty are obtained for both the Northern and Southern Hemispheres using the Advanced Microwave Scanning Radiometer for the Earth Observing System (AMSR-E) TB. NT2 IC relative uncertainties estimated on a footprint-by-footprint swath-by-swath basis were averaged daily over each 12.5-km grid cell of the polar stereographic grid. For both hemispheres and throughout the year, the NT2 relative uncertainty is less than 5%. In the Southern Hemisphere, it is low in the interior ice pack, and it increases in the marginal ice zone up to 5%. In the Northern Hemisphere, areas with high uncertainties are also found in the high IC area of the Central Arctic. Retrieval uncertainties are greater in areas corresponding to NT2 ice types associated with deep snow and new ice. Seasonal variations in uncertainty show larger values in summer as a result of melt conditions and greater atmospheric contributions. Our analysis also includes an evaluation of the NT2 algorithm sensitivity to AMSR-E sensor noise. There is a 60% probability that the IC does not change (to within the computed retrieval precision of 1%) due to sensor noise, and the cumulated probability shows that there is a 90% chance that the IC varies by less than +/-3%. We also examined the daily IC variability, which is dominated by sea ice drift and ice formation/melt. Daily IC variability is the highest, year round, in the MIZ (often up to 20%, locally 30%). The temporal and spatial distributions of the retrieval uncertainties and the daily IC variability is expected to be useful for algorithm intercomparisons, climate trend assessments, and possibly IC assimilation in models.

Sea Ice↗
NASA NTRS2018

A Cloud Algorithm Based on the O2-O2 477 nm Absorption Band Featuring an Advanced Spectral Fitting Method and the Use of Surface Geometry-Dependent Lambertian-Equivalent Reflectivity

We discuss a new cloud algorithm that retrieves an effective cloud pressure, also known as cloud optical centroid pressure (OCP), from oxygen dimer (O2-O2) absorption at 477nm after determining an effective cloud fraction (ECF) at 466nm, a wavelength not significantly affected by trace-gas absorption and rotational Raman scattering. The retrieved cloud products are intended for use as inputs to the operational nitrogen dioxide (NO2) retrieval algorithm for the Ozone Monitoring Instrument (OMI) flying on the Aura satellite. The cloud algorithm uses temperature-dependent O2-O2 cross sections and incorporates flexible spectral fitting techniques that account for specifics of the surface reflectivity. The fitting procedure derives O2-O2 slant column densities (SCDs) from radiances after O3, NO2, and H2O absorption features have been removed based on estimates of the amounts of these species from independent OMI algorithms. The cloud algorithm is based on the frequently used mixed Lambertian-equivalent reflectivity (MLER) concept. A geometry-dependent Lambertian-equivalent reflectivity (GLER), which is a proxy of surface bidirectional reflectance, is used for the ground reflectivity in our implementation of the MLER approach. The OCP is derived from a match of the measured O2-O2 SCD to that calculated with the MLER method. Temperature profiles needed for computation of vertical column densities are taken from the Global Modeling Initiative (GMI) model. We investigate the effect of using GLER instead of climatological LER on the retrieved ECF and OCP. For evaluation purposes, the retrieved ECFs and OCPs are compared with those from the operational OMI cloud product, which is also based on the same O2-O2 absorption band. Impacts of the application of the newly developed cloud algorithm to the OMI NO2 retrieval are discussed.

cloud fraction and pressure↗
NASA NTRS2013

Algorithm Development for Predicting Biodiversity Based on Phytoplankton Absorption

Ocean color remote sensing has provided the scientific community with unprecedented global coverage of chlorophyll a, an indicator of phytoplankton biomass. Together, satellite-derived chlorophyll a and knowledge of Phytoplankton Functional Types (PFTs) will improve our limited understanding of marine ecosystem responses to physiochemical climate drivers involved in carbon cycle dynamics and linkages. Using cruise data from the Gulf of Maine and the Middle Atlantic Bight (N 269 pairs of HPLC and phytoplankton absorption samples), two modeling approaches were utilized to predict phytoplankton absorption and pigments. Algorithm I predicts the chlorophyll-specific absorption coefficient (a*(sub ph) (m(exp 2) mg chl a(exp - 1)) using inputs of temperature, light, and chlorophyll a. Modeled r(exp 2) values (400700 nm) ranged from 0.79 to 0.99 when compared to in situ observations with approximately 25 percent lower r(exp 2) values in the UV region. Algorithm II-a utilizes matrix inversion analysis to predict a(sub ph)(m(exp -1), 400700 nm) and r(exp 2) values ranged from 0.89 to 0.99. The prediction of phytoplankton pigments with Algorithm II-b produced r(exp 2) values that ranged from 0.40 to 0.93. When used in combination, Algorithm I, and Algorithm II-a are able to use satellite products of SST, PAR, and chlorophyll a (Algorithm I) to predict pigment concentrations and ratios to describe the phytoplankton community. The results of this study demonstrate that the spatial variation in modeled pigment ratios differ significantly from the 10-year SeaWiFS average chlorophyll a data set. Contiguous observations of chlorophyll a and phytoplankton biodiversity will elucidate ecosystem responses with unprecedented complexity.

phytoplankton↗
NASA NTRS1994

Massively Parallel Algorithms for Real-Time Wavefront Control of a Dense Adaptive Optics System

In this paper massively parallel algorithms and architectures for real-time wavefront control of a dense adaptive optic system (SELENE) are presented. We have already shown that the computation of a near optimal control algorithm for SELENE can be reduced to the solution of a discrete Poisson equation on a regular domain. Although this represents an optimal computation, due the large size of the system and the high sampling rate requirement, the implementation of this control algorithm poses a computationally challenging problem since it demands a sustained computational throughput of the order of 10 GFlops. We develop a novel algorithm, designated as Fast Invariant Imbedding algorithm, which offers a massive degree of parallelism with simple communication and synchronization requirements. Due to these features, our algorithm is significantly more efficient than other Fast Poisson Solvers for implementation on massively parallel architectures.

massively↗
NASA NTRS2022

Analysis of the MODIS Above-Cloud Aerosol Retrieval Algorithm Using MCARS

The Multi-sensor Cloud and Aerosol Retrieval Simulator (MCARS) presently produces synthetic radiance data from Goddard Earth Observing System version 5 (GEOS-5) model output as if the Moderate Resolution Imaging Spectroradiometer (MODIS) was viewing a combination of atmospheric column inclusive of clouds, aerosols and a variety of gases and land/ocean surface at a specific location. In this paper we use MCARS to study the MODIS Above-Cloud AEROsol retrieval algorithm (MOD06ACAERO). MOD06ACAERO is presently a regional research algorithm able to retrieve aerosol optical thickness over clouds, in particular absorbing biomass burning aerosols overlying marine boundary layer clouds in the Southeastern Atlantic Ocean. The algorithm’s ability to provide aerosol information in cloudy conditions makes it a valuable source of information for modeling and climate studies n an area where current clear sky-only operational MODIS aerosol retrievals effectively have a data gap between the months of June and October. We use MCARS for a verification and closure study of the MOD06ACAERO algorithm. The purpose of this study is to develop a set of constraints a model developer might use during assimilation of MOD06ACAERO data. Our simulations indicate that the MOD06ACAERO algorithm performs well for marine boundary layer clouds in the SE Atlantic provided some specific screening rules are observed. For the present study, a combination of five simulated MODIS data granules was used for a dataset of 13.5 million samples with known input conditions. When pixel retrieval uncertainty was less than 30%, optical thickness of the underlying cloud layer was greater than 4 and scattering angle range within the cloud bow was excluded, MOD06ACAERO retrievals agreed with the underlying ground truth (GEOS-5 cloud and aerosol profiles used to generate the synthetic radiances) with a slope of 0.913, offset of 0.06, and RMSE=0.107. When only near-nadir pixels were considered (view zenith angle within +/-20 degrees) the agreement with source data further improved (0.977, 0.051 and 0.096 respectively). Algorithm closure was examined using a single case out of the five 38 used for verification. For closure, the MOD06ACAERO code was modified to use GEOS-5 temperature and moisture profiles as ancillary. Agreement of MOD06ACAERO retrievals with source data for the closure study had a slope of 0.996 with offset -0.007 and RMSE of 0.097 at pixel uncertainty level of less than 40%, illustrating the benefits of high-quality ancillary atmospheric data for such retrievals.

MODIS↗
DOE OSTI2016

Analysis of Community Detection Algorithms for Large Scale Cyber Networks

The aim of this project is to use existing community detection algorithms on an IP network dataset to create supernodes within the network. This study compares the performance of different algorithms on the network in terms of running time. The paper begins with an introduction to the concept of clustering and community detection followed by the research question that the team aimed to address. Further the paper describes the graph metrics that were considered in order to shortlist algorithms followed by a brief explanation of each algorithm with respect to the graph metric on which it is based. The next section in the paper describes the methodology used by the team in order to run the algorithms and determine which algorithm is most efficient with respect to running time. Finally, the last section of the paper includes the results obtained by the team and a conclusion based on those results as well as future work.

algorithms↗
DOE OSTI2021

Parallel Algorithms for Efficient Computation of High-Order Line Graphs of Hypergraphs

This paper considers structures of systems beyond dyadic (pairwise) interactions and investigates mathematical modeling of multi-way interactions and connections as hypergraphs, where captured relationships among system entities are set-valued. To date, in most situations, entities in a hypergraph are considered connected as long as there is at least one common ``neighbor''. However, minimal commonality sometimes discards the ``strength'' of connections and interactions among groups. To this end, considering the ``width'' of a connection, referred to as the \emph{$s$-overlap} of neighbors, provides more meaningful insights into how closely the communities or entities interact with each other. In addition, $s$-overlap computation is the fundamental kernel to construct the line graph of a hypergraph, a low-order approximation of the hypergraph which can carry significant information about the original hypergraph. Subsequent stages of a data analytics pipeline then can apply highly-tuned graph algorithms on the line graph to reveal important features. Given a hypergraph, computing the $s$-overlaps by exhaustively considering all pairwise entities can be computationally prohibitive. To tackle this challenge, we develop efficient algorithms to compute $s$-overlaps and the corresponding line graph of a hypergraph. We propose several heuristics to avoid execution of redundant work and improve performance of the $s$-overlap computation. Our parallel algorithm, combined with these heuristics, is orders of magnitude (more than $10\times$) faster than the naive algorithm in all cases and the SpGEMM algorithm with filtration in most cases (especially with large $s$ value).

hypergraph algorithms, graph algorithms, parallel ↗
DOE OSTI2014

New algorithms for iterative matrix‐free eigensolvers in quantum chemistry

New algorithms for iterative diagonalization procedures that solve for a small set of eigen‐states of a large matrix are described. The performance of the algorithms is illustrated by calculations of low and high‐lying ionized and electronically excited states using equation‐of‐motion coupled‐cluster methods with single and double substitutions (EOM‐IP‐CCSD and EOM‐EE‐CCSD). We present two algorithms suitable for calculating excited states that are close to a specified energy shift (interior eigenvalues). One solver is based on the Davidson algorithm, a diagonalization procedure commonly used in quantum‐chemical calculations. The second is a recently developed solver, called the “Generalized Preconditioned Locally Harmonic Residual (GPLHR) method.” We also present a modification of the Davidson procedure that allows one to solve for a specific transition. The details of the algorithms, their computational scaling, and memory requirements are described. The new algorithms are implemented within the EOM‐CC suite of methods in the Q‐Chem electronic structure program. © 2014 Wiley Periodicals, Inc.

Zuev, Dmitry↗
DOE OSTI2014

A nonlinearly preconditioned conjugate gradient algorithm for rank‐ R canonical tensor approximation

Summary Alternating least squares (ALS) is often considered the workhorse algorithm for computing the rank‐ R canonical tensor approximation, but for certain problems, its convergence can be very slow. The nonlinear conjugate gradient (NCG) method was recently proposed as an alternative to ALS, but the results indicated that NCG is usually not faster than ALS. To improve the convergence speed of NCG, we consider a nonlinearly preconditioned NCG (PNCG) algorithm for computing the rank‐ R canonical tensor decomposition. Our approach uses ALS as a nonlinear preconditioner in the NCG algorithm. Alternatively, NCG can be viewed as an acceleration process for ALS. We demonstrate numerically that the convergence acceleration mechanism in PNCG often leads to important pay‐offs for difficult tensor decomposition problems, with convergence that is significantly faster and more robust than for the stand‐alone NCG or ALS algorithms. We consider several approaches for incorporating the nonlinear preconditioner into the NCG algorithm that have been described in the literature previously and have met with success in certain application areas. However, it appears that the nonlinearly PNCG approach has received relatively little attention in the broader community and remains underexplored both theoretically and experimentally. Thus, this paper serves several additional functions, by providing in one place a concise overview of several PNCG variants and their properties that have only been described in a few places scattered throughout the literature, by systematically comparing the performance of these PNCG variants for the tensor decomposition problem, and by drawing further attention to the usefulness of nonlinearly PNCG as a general tool. In addition, we briefly discuss the convergence of the PNCG algorithm. In particular, we obtain a new convergence result for one of the PNCG variants under suitable conditions, building on known convergence results for non‐preconditioned NCG. Copyright © 2014 John Wiley & Sons, Ltd.

Sterck, Hans De↗
DOE OSTI2016

Incremental k-core decomposition: Algorithms and evaluation

A k-core of a graph is a maximal connected subgraph in which every vertex is connected to at least k vertices in the subgraph. k-core decomposition is often used in large-scale network analysis, such as community detection, protein function prediction, visualization, and solving NP-hard problems on real networks efficiently, like maximal clique finding. In many real-world applications, networks change over time. As a result, it is essential to develop efficient incremental algorithms for dynamic graph data. In this paper, we propose a suite of incremental k-core decomposition algorithms for dynamic graph data. These algorithms locate a small subgraph that is guaranteed to contain the list of vertices whose maximum k-core values have changed and efficiently process this subgraph to update the k-core decomposition. We present incremental algorithms for both insertion and deletion operations, and propose auxiliary vertex state maintenance techniques that can further accelerate these operations. Our results show a significant reduction in runtime compared to non-incremental alternatives. We illustrate the efficiency of our algorithms on different types of real and synthetic graphs, at varying scales. Furthermore, for a graph of 16 million vertices, we observe relative throughputs reaching a million times, relative to the non-incremental algorithms.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2019

An adaptive, multivariate partitioning algorithm for global optimization of nonconvex programs

We develop an adaptive, multivariate partitioning algorithm for solving nonconvex, Mixed-Integer Nonlinear Programs (MINLPs) with polynomial functions to global optimality. In particular, we present an iterative algorithm that exploits piecewise, convex relaxation approaches via disjunctive formulations to solve MINLPs that is different than conventional spatial branch-and-bound approaches. The algorithm partitions the domains of variables in an adaptive and non-uniform manner at every iteration to focus on productive areas of the search space. Furthermore, domain reduction techniques based on sequential, optimization-based bound-tightening and piecewise relaxation techniques, as a part of a presolve step, are integrated into the main algorithm. Finally, we demonstrate the effectiveness of the algorithm on well-known benchmark problems (including Pooling and Blending instances) from MINLPLib and compare our algorithm with state-of-the-art global optimization solvers. With our novel approach, we solve several large-scale instances, some of which are not solvable by state-of-the-art solvers. We also succeed in reducing the best known optimality gap for a hard, generalized pooling problem instance.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Multistart algorithm for identifying all optima of nonconvex stochastic functions

Here, we propose a multistart algorithm to identify all local minima of a constrained, nonconvex stochastic optimization problem. The algorithm uniformly samples points in the domain and then starts a local stochastic optimization run from any point that is the "probabilistically best" point in its neighborhood. Under certain conditions, our algorithm is shown to asymptotically identify all local optima with high probability; this holds even though our algorithm is shown to almost surely start only finitely many local stochastic optimization runs. We demonstrate the performance of an implementation of our algorithm on nonconvex stochastic optimization problems, including identifying optimal variational parameters for the quantum approximate optimization algorithm.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2016

A spectral, quasi-cylindrical and dispersion-free Particle-In-Cell algorithm

We propose a spectral Particle-In-Cell (PIC) algorithm that is based on the combination of a Hankel transform and a Fourier transform. For physical problems that have close-to-cylindrical symmetry, this algorithm can be much faster than full 3D PIC algorithms. In addition, unlike standard finite-difference PIC codes, the proposed algorithm is free of spurious numerical dispersion, in vacuum. This algorithm is benchmarked in several situations that are of interest for laser-plasma interactions. These benchmarks show that it avoids a number of numerical artifacts, that would otherwise affect the physics in a standard PIC algorithm - including the zero-order numerical Cherenkov effect.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
DOE OSTI2016

Comparison of Dose Distributions With TG-43 and Collapsed Cone Convolution Algorithms Applied to Accelerated Partial Breast Irradiation Patient Plans

Purpose: To compare the treatment plans for accelerated partial breast irradiation calculated by the new commercially available collapsed cone convolution (CCC) and current standard TG-43–based algorithms for 50 patients treated at our institution with either a Strut-Adjusted Volume Implant (SAVI) or Contura device. Methods and Materials: We recalculated target coverage, volume of highly dosed normal tissue, and dose to organs at risk (ribs, skin, and lung) with each algorithm. For 1 case an artificial air pocket was added to simulate 10% nonconformance. We performed a Wilcoxon signed rank test to determine the median differences in the clinical indices V90, V95, V100, V150, V200, and highest-dosed 0.1 cm{sup 3} and 1.0 cm{sup 3} of rib, skin, and lung between the two algorithms. Results: The CCC algorithm calculated lower values on average for all dose-volume histogram parameters. Across the entire patient cohort, the median difference in the clinical indices calculated by the 2 algorithms was <10% for dose to organs at risk, <5% for target volume coverage (V90, V95, and V100), and <4 cm{sup 3} for dose to normal breast tissue (V150 and V200). No discernable difference was seen in the nonconformance case. Conclusions: We found that on average over our patient population CCC calculated (<10%) lower doses than TG-43. These results should inform clinicians as they prepare for the transition to heterogeneous dose calculation algorithms and determine whether clinical tolerance limits warrant modification.

62 RADIOLOGY AND NUCLEAR MEDICINE↗
DOE OSTI2021

An unsupervised machine-learning checkpoint-restart algorithm using Gaussian mixtures for particle-in-cell simulations

We propose an unsupervised machine-learning checkpoint-restart (CR) algorithm for particle-in-cell (PIC) algorithms using Gaussian mixtures (GM). The algorithm compresses the particle population per spatial cell by constructing a velocity distribution function using GM. Particles are reconstructed at restart time by local resampling of the Gaussians. To guarantee fidelity of the CR process, we ensure the exact preservation of invariants such as charge, momentum, and energy for both compression and reconstruction stages, everywhere on the mesh. We also ensure the preservation of Gauss' law after particle reconstruction by exactly matching the density profile at restart time. As a result, the GM CR algorithm is shown to provide a clean, conservative restart capability while potentially affording orders of magnitude savings in input/output requirements. Here, we demonstrate the algorithm using a recently developed exactly energy- and charge-conserving PIC algorithm using both electrostatic and electromagnetic tests. The tests demonstrate not only a high-fidelity CR capability, but also its potential for enhancing the fidelity of the PIC solution for a given particle resolution.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2018

An automated isotope identification and quantification algorithm for isotope mixtures in low-resolution gamma-ray spectra

There is a need to develop an automated isotope identification and quantification algorithm that can perform well using low-resolution gamma-ray detectors. The algorithm should be able to perform well on spectra that contain a mixture of many isotopes as well as in cases where spectral features are difficult to analyze. Due to the low resolution of these detectors, spectra of isotope mixtures becomes complicated to identify when features overlap. Previous research applying machine learning algorithms to isotope identification has been promising. Further work is needed to demonstrate the limits of machine learning algorithms when applied to identifying mixtures of isotopes and spectra where features are not obvious. Because machine learning algorithms use abstract features of the spectrum, such as the shape of overlapping peaks and Compton continuum, they are a natural choice for analyzing isotope mixtures. In this work, an artificial neural network (ANN) has be trained to calculate the relative activities of 29 isotopes in a spectrum. The ANN is trained with simulated gamma-ray spectra, allowing custom datasets to be generated for specific identification tasks. The algorithms performance on simulated spectra without apparent features and on simulated isotope mixtures are both analyzed.

38 RADIATION CHEMISTRY, RADIOCHEMISTRY, AND NUCLEA↗