Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “algorithmic”

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 361 records · Page 20
All sourcesNASA NTRSDOE OSTI
DOE OSTI2021

An Adaptive Tracking Algorithm for Convection in Simulated and Remote Sensing Data

A robust and computationally efficient object tracking algorithm is developed by incorporating various tracking techniques. Physical properties of the objects, such as brightness temperature or reflectivity, are not considered. Therefore, the algorithm is adaptable for tracking convection-like features in simulated data and remotely sensed two-dimensional images. In this algorithm, a first guess of the motion, estimated using the Fourier phase shift, is used to predict the candidates for matching. A disparity score is computed for each target–candidate pair. The disparity also incorporates overlapping criteria in the case of large objects. Then the Hungarian method is applied to identify the best pairs by minimizing the global disparity. The high-disparity pairs are unmatched, and their target and candidate are declared expired and newly initiated objects, respectively. They are tested for merger and split on the basis of their size and overlap with the other objects. The sensitivity of track duration is shown for different disparity and size thresholds. The report highlights the algorithm’s ability to study convective life cycles using radar and simulated data over Darwin, Australia. The algorithm skillfully tracks individual convective cells (a few pixels in size) and large convective systems. The duration of tracks and cell size are found to be lognormally distributed over Darwin. The evolution of size and precipitation types of isolated convective cells is presented in the Lagrangian perspective. This algorithm is part of a vision for a modular platform [viz., TINT is not TITAN (TINT) and Tracking and Object-Based Analysis of Clouds (tobac)] that will evolve into a sustainable choice to analyze atmospheric features.

54 ENVIRONMENTAL SCIENCES↗
DOE OSTI2020

A parallel hierarchical blocked adaptive cross approximation algorithm

This article presents a low-rank decomposition algorithm based on subsampling of matrix entries. The proposed algorithm first computes rank-revealing decompositions of submatrices with a blocked adaptive cross approximation (BACA) algorithm, and then applies a hierarchical merge operation via truncated singular value decompositions (H-BACA). The proposed algorithm significantly improves the convergence of the baseline ACA algorithm and achieves reduced computational complexity compared to the traditional decompositions such as rank-revealing QR. Numerical results demonstrate the efficiency, accuracy, and parallel scalability of the proposed algorithm.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2016

Application of Hybrid Genetic Algorithm Routine in Optimizing Food and Bioengineering Processes

Optimization is a crucial step in the analysis of experimental results. Deterministic methods only converge on local optimums and require exponentially more time as dimensionality increases. Stochastic algorithms are capable of efficiently searching the domain space, however convergence is not guaranteed. This article demonstrates the novelty of hybrid genetic algorithm which combines both stochastic and deterministic routine for improved optimization results. A new hybrid genetic algorithm developed is applied to the Ackley benchmark function as well as case studies in foods, biofuels, and biotechnology processes. For each case study the hybrid genetic algorithm found a better optimum candidate than reported by the sources. In the case of food processing the hybrid genetic predicted 5% higher anthocyanin yield. Optimization of bio-oil production using HGA resulted in a 4.73 % higher yield. In enzyme production process HGA predicted 2.18 IU/gds of higher xylanase yield. In conclusion, hybridization of genetic algorithm with a deterministic algorithm resulted in maximum optimum compared to the statistical methods.

09 BIOMASS FUELS↗
DOE OSTI2022

A Comparative Study of Machine Learning Algorithms for Industry-Specific Freight Generation Model

According to Bureau of Transportation Statistics, the U.S. transportation system handled 14,329 million ton-miles of freight per day in 2020. Understanding the generation of these freight shipments is crucial for transportation researchers, planners, and policymakers to design and plan for a more efficient and connected freight transportation system. Traditionally, the freight generation modeling has been based on Ordinary Least Square (OLS) regression, although more advanced Machine Learning (ML) algorithms have been evaluated and proven to have excellent performance in various transportation applications in recent years. Furthermore, one modeling approach applied for one industry might not always be applicable for another as their freight generation logics can be quite different. The objective of this study is to apply and evaluate alternative ML algorithms in the estimation of freight generation for each of 45 industry types. Seven alternative ML algorithms, along with the base OLS regression, were evaluated and compared. In addition, the study considered different combinations of variables in both the original and logarithmic form as well as hyperparameters of those ML algorithms in the model selection for each industry type. The results showed statistically significant improvements in the root mean square error reduction by the alternative ML algorithms over the OLS for over 80% of cases. The study suggests utilizing the alternative ML algorithms can reduce the root mean square error by about 30%, depending on industry types.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2015

A cloud detection algorithm using the downwelling infrared radiance measured by an infrared pyrometer of the ground-based microwave radiometer

For better utilization of the ground-based microwave radiometer, it is important to detect the cloud presence in the measured data. Here, we introduce a simple and fast cloud detection algorithm by using the optical characteristics of the clouds in the infrared atmospheric window region. The new algorithm utilizes the brightness temperature (Tb) measured by an infrared radiometer installed on top of a microwave radiometer. The two-step algorithm consists of a spectral test followed by a temporal test. The measured Tb is first compared with a predicted clear-sky Tb obtained by an empirical formula as a function of surface air temperature and water vapor pressure. For the temporal test, the temporal variability of the measured Tb during one minute compares with a dynamic threshold value, representing the variability of clear-sky conditions. It is designated as cloud-free data only when both the spectral and temporal tests confirm cloud-free data. Overall, most of the thick and uniform clouds are successfully detected by the spectral test, while the broken and fast-varying clouds are detected by the temporal test. The algorithm is validated by comparison with the collocated ceilometer data for six months, from January to June 2013. The overall proportion of correctness is about 88.3% and the probability of detection is 90.8%, which are comparable with or better than those of previous similar approaches. Two thirds of discrepancies occur when the new algorithm detects clouds while the ceilometer does not, resulting in different values of the probability of detection with different cloud-base altitude, 93.8, 90.3, and 82.8% for low, mid, and high clouds, respectively. Finally, due to the characteristics of the spectral range, the new algorithm is found to be insensitive to the presence of inversion layers.

14 SOLAR ENERGY↗
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↗
DOE OSTI2023

BigNeuron: a resource to benchmark and predict performance of algorithms for automated tracing of neurons in light microscopy datasets

BigNeuron is an open community bench-testing platform with the goal of setting open standards for accurate and fast automatic neuron tracing. We gathered a diverse set of image volumes across several species that is representative of the data obtained in many neuroscience laboratories interested in neuron tracing. Here, we report generated gold standard manual annotations for a subset of the available imaging datasets and quantified tracing quality for 35 automatic tracing algorithms. The goal of generating such a hand-curated diverse dataset is to advance the development of tracing algorithms and enable generalizable benchmarking. Together with image quality features, we pooled the data in an interactive web application that enables users and developers to perform principal component analysis, t-distributed stochastic neighbor embedding, correlation and clustering, visualization of imaging and tracing data, and benchmarking of automatic tracing algorithms in user-defined data subsets. The image quality metrics explain most of the variance in the data, followed by neuromorphological features related to neuron size. Furthermore, we observed that diverse algorithms can provide complementary information to obtain accurate results and developed a method to iteratively combine methods and generate consensus reconstructions. The consensus trees obtained provide estimates of the neuron structure ground truth that typically outperform single algorithms in noisy datasets. However, specific algorithms may outperform the consensus tree strategy in specific imaging conditions. Finally, to aid users in predicting the most accurate automatic tracing results without manual annotations for comparison, we used support vector machine regression to predict reconstruction quality given an image volume and a set of automatic tracings.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

Semantic embedding for quantum algorithms

The study of classical algorithms is supported by an immense understructure, founded in logic, type, and category theory, that allows an algorithmist to reason about the sequential manipulation of data irrespective of a computation’s realizing dynamics. As quantum computing matures, a similar need has developed for an assurance of the correctness of high-level quantum algorithmic reasoning. Parallel to this need, many quantum algorithms have been unified and improved using quantum signal processing (QSP) and quantum singular value transformation (QSVT), which characterize the ability, by alternating circuit ansätze, to transform the singular values of sub-blocks of unitary matrices by polynomial functions. However, while the algebraic manipulation of polynomials is simple (e.g., compositions and products), the QSP/QSVT circuits realizing analogous manipulations of their embedded polynomials are non-obvious. This work constructs and characterizes the runtime and expressivity of QSP/QSVT protocols where circuit manipulation maps naturally to the algebraic manipulation of functional transforms (termed semantic embedding). In this way, QSP/QSVT can be treated and combined modularly, purely in terms of the functional transforms they embed, with key guarantees on the computability and modularity of the realizing circuits. We also identify existing quantum algorithms whose use of semantic embedding is implicit, spanning from distributed search to proofs of soundness in quantum cryptography. The methods used, based in category theory, establish a theory of semantically embeddable quantum algorithms, and provide a new role for QSP/QSVT in reducing sophisticated algorithmic problems to simpler algebraic ones.

Physics↗