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 1,135 records · Page 63
All sourcesNASA NTRSDOE OSTI
DOE OSTI2017

A Histogram-Free Multicanonical Monte Carlo Algorithm for the Basis Expansion of Density of States

We report a new multicanonical Monte Carlo (MC) algorithm to obtain the density of states (DOS) for physical systems with continuous state variables in statistical mechanics. Our algorithm is able to obtain an analytical form for the DOS expressed in a chosen basis set, instead of a numerical array of finite resolution as in previous variants of this class of MC methods such as the multicanonical (MUCA) sampling and Wang-Landau (WL) sampling. This is enabled by storing the visited states directly in a data set and avoiding the explicit collection of a histogram. This practice also has the advantage of avoiding undesirable artificial errors caused by the discretization and binning of continuous state variables. Our results show that this scheme is capable of obtaining converged results with a much reduced number of Monte Carlo steps, leading to a significant speedup over existing algorithms.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

A Length Adaptive Algorithm-Hardware Co-design of Transformer on FPGA Through Sparse Attention and Dynamic Pipelining

Transformers are considered one of the most important deep learning models since 2018, in part because it establishes state-of-the-art (SOTA) records and could potentially replace existing Deep Neural Networks (DNNs). Despite the remarkable triumphs, the prolonged turnaround time of Transformer models is a widely recognized roadblock. The variety of sequence lengths imposes additional computing overhead where inputs need to be zero-padded to the maximum sentence length in the batch to accommodate the parallel computing platforms. This paper targets the field-programmable gate array (FPGA) and proposes a coherent sequence length adaptive algorithm–hardware co-design for Transformer acceleration. Particularly, we develop a hardware-friendly sparse attention operator and a length-aware hardware resource scheduling algorithm. The proposed sparse attention operator brings the complexity of attention-based models down to linear complexity and alleviates the off-chip memory traffic. The proposed length-aware resource hardware scheduling algorithm dynamically allocates the hardware resources to fill up the pipeline slots and eliminates bubbles for NLP tasks. Experiments show that our design has very small accuracy loss and has 80.2 × and 2.6 × speedup compared to CPU and GPU implementation, and 4 × higher energy efficiency than state-of-the-art GPU accelerator optimized via CUBLAS GEMM.

Peng, Hongwu↗
DOE OSTI2025

ScaWL: Scaling k-WL (Weisfeiler-Lehman) Algorithms in Memory and Performance on Shared and Distributed-Memory Systems

The k-dimensional Weisfeiler-Lehman (k-WL) algorithm—developed as an efficient heuristic for testing if two graphs are isomorphic—is a fundamental kernel for node embedding in the emerging field of graph neural networks. Unfortunately, the k-WL algorithm has exponential storage requirements, limiting the size of graphs that can be handled. This work presents a novel k-WL scheme with a storage requirement orders of magnitude lower while maintaining the same accuracy as the original k-WL algorithm. Due to the reduced storage requirement, our scheme allows for processing much bigger graphs than previously possible on a single compute node. For even bigger graphs, we provide the first distributed-memory implementation. Our k-WL scheme also has significantly reduced communication volume and offers high scalability. Our experimental results demonstrate that our approach is significantly faster and has superior scalability compared to five other implementations employing state-of-the-art techniques.

algorithims↗
DOE OSTI2020

Simulating pitch angle scattering using an explicitly solvable energy-conserving algorithm

Particle distribution functions evolving under the Lorentz operator can be simulated with the Langevin equation for pitch angle scattering. This approach is frequently used in particle based Monte-Carlo simulations of plasma collisions, among others. However, most numerical treatments do not guarantee energy conservation, which may lead to unphysical artifacts such as numerical heating and spectra distortions. We present a novel structure-preserving numerical algorithm for the Langevin equation for pitch angle scattering. Similar to the well-known Boris algorithm, the proposed numerical scheme takes advantage of the structure-preserving properties of the Cayley transform when calculating the velocity-space rotations. The resulting algorithm is explicitly solvable, while preserving the norm of velocities down to machine precision. We demonstrate that the method has the same order of numerical convergence as the traditional stochastic Euler-Maruyama method.

Zhang, Xin↗
DOE OSTI2019

Benchmark Algorithm for RadioNuclide Identification v1.0

Benchmark Algorithm for Radio-Nuclide Identification (BARNI) is an automatic radionuclide identification tool for use with gamma-ray spectra. BARNI is designed to serve as a comparative tool for commercial vendor algorithms, such as those found in RadioIsotope Identification Devices (RIID). The tool incorporates an automated training routine allowing BARNI's classifier to be trained for a variety of detectors. The identification algorithm uses a peak search, the results of which are used to build features that are subsequently used for training a classifier. The user provided spectral templates allow BARNI to be trained for any detector of the user's choice. Is

NELSON, KARLE.↗
DOE OSTI2018

A Time-Dependent Intermodal A* Algorithm: Methodology and Implementation on a Large-Scale Network

This paper proposes a time-dependent intermodal A* (TDIMA*) algorithm. The algorithm works on a multimodal network with transit, walking, and vehicular network links, and finds paths for the three major modes (transit, walking, driving) and any feasible combination thereof (e.g., park-and-ride). Turn penalties on the vehicular network and progressive transfer penalties on the transit network are considered for improved realism. Moreover, upper bounds to prevent excessive waiting and walking are introduced, as well as an upper bound on driving for the park-and-ride (PNR) mode. The algorithm is validated on the large-scale Chicago Regional network using real-world trips against the Google Directions API and the Regional Transit Authority router.

Verbas, Omer↗
DOE OSTI2012

The maximum clique enumeration problem: algorithms, applications, and implementations

Background: The maximum clique enumeration (MCE) problem asks that we identify all maximum cliques in a finite, simple graph. MCE is closely related to two other well-known and widely-studied problems: the maximum clique optimization problem, which asks us to determine the size of a largest clique, and the maximal clique enumeration problem, which asks that we compile a listing of all maximal cliques. Naturally, these three problems are N P -hard, given that they subsume the classic version of the N P -complete clique decision problem. MCE can be solved in principle with standard enumeration methods due to Bron, Kerbosch, Kose and others. Unfortunately, these techniques are ill-suited to graphs encountered in our applications. We must solve MCE on instances deeply seeded in data mining and computational biology, where high-throughput data capture often creates graphs of extreme size and density. MCE can also be solved in principle using more modern algorithms based in part on vertex cover and the theory of fixed-parameter tractability (FPT). While FPT is an improvement, these algorithms too can fail to scale sufficiently well as the sizes and densities of our datasets grow. Results: An extensive testbed of benchmark graphs are created using publicly available transcriptomic datasets from the Gene Expression Omnibus (GEO). Empirical testing reveals crucial but latent features of such high-throughput biological data. In turn, it is shown that these features distinguish real data from random data intended to reproduce salient topological features. In particular, with real data there tends to be an unusually high degree of maximum clique overlap. Armed with this knowledge, novel decomposition strategies are tuned to the data and coupled with the best FPT MCE implementations. Conclusions: Several algorithmic improvements to MCE are made which progressively decrease the run time on graphs in the testbed. Frequently the final runtime improvement is several orders of magnitude. As a result, instances which were once prohibitively time-consuming to solve are brought into the domain of realistic feasibility.

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2022

Genetic algorithm-based optimisation of the few-group structure for lead fast reactors analysis

The optimal choice of the few-group structure for full-core transient analyses is still an open issue in reactor physics, especially for fast system like the lead fast reactor. One possible approach to select the group boundaries is represented by heuristic search algorithms, such as evolutionary ones. In this paper, a genetic algorithm coupled with the SIMMER code is employed to determine optimized six-group boundaries for the analysis of the ALFRED reactor. The Serpent Monte Carlo code is adopted to produce both the fine-group cross section library and the fine-group flux, used as a figure of merit to drive the genetic optimisation. The results show that the algorithm is indeed able to find satisfactory solutions that comply with the set objectives and can be reasonably interpreted in light of the underlying physics of the considered core. (authors)

21 SPECIFIC NUCLEAR REACTORS AND ASSOCIATED PLANTS↗
DOE OSTI2014

Gradient descent algorithm applied to wavefront retrieval from through-focus images by an extreme ultraviolet microscope with partially coherent source

The wavefront retrieval by gradient descent algorithm that is typically applied to coherent or incoherent imaging is extended to retrieve a wavefront from a series of through-focus images by partially coherent illumination. For accurate retrieval, we modeled partial coherence as well as object transmittance into the gradient descent algorithm. However, this modeling increases the computation time due to the complexity of partially coherent imaging simulation that is repeatedly used in the optimization loop. To accelerate the computation, we incorporate not only the Fourier transform but also an eigenfunction decomposition of the image. As a demonstration, the extended algorithm is applied to retrieve a field-dependent wavefront of a microscope operated at extreme ultraviolet wavelength (13.4 nm). The retrieved wavefront qualitatively matches the expected characteristics of the lens design.

36 MATERIALS SCIENCE↗
DOE OSTI2018

Expectation-maximization algorithm for amplitude estimation of saturated optical transient signals

This paper addresses parameter estimation for an optical transient signal when the received data has been right-censored. We develop an expectation-maximization (EM) algorithm to estimate the amplitude of a Poisson intensity with a known shape in the presence of additive background counts, where the measurements are subject to saturation effects. We then compare the results of our algorithm with those of an EM algorithm that is unaware of the censoring.

47 OTHER INSTRUMENTATION↗
DOE OSTI2022

Super-resolution demodulation for fiber sensor arrays based on the MUSIC algorithm

This paper studies the use of MUltiple SIgnal Classification (MUSIC) as a super-resolution algorithm to improve demodulation results for intrinsic Fabry–Perot interferometer (IFPI) sensor arrays. Through distinction between noise and signal subspaces in an observation matrix, this paper shows that a 38-fold improvement in the full width at half maximum (FWHM) estimation of IFPI optical path differences (OPD) can be achieved using this algorithm. Based on this improved method, this paper demonstrates that a tunable laser with a 1.3-nm tuning range can achieve the same sensor demodulation performance as a tunable laser with a 50-nm tuning range if a conventional Fourier transform-based algorithm is used. This paper presents a new approach to analyzing optical signals produced by multiple multiplexed interferometers with similar OPDs with potential applications for both single-mode and multiple-mode devices.

Li, Yuqi (ORCID:0000000291643663)↗
DOE OSTI2024

General algorithm for characterization of donor-acceptor pair recombination processes in solid-state materials

Radiative recombination processes can occur in solid-state systems through the pairing of donor and acceptor defects of the lattice. Recently, donor-acceptor pairs (DAP) have been proposed as promising candidates for quantum applications, and their signature has been observed in emerging low-dimensional materials. Therefore, the identification of such processes is gaining interest and requires methods to efficiently and reliably characterize them. Here, we introduce a general algorithm to identify DAP processes starting from the experimental photoluminescence (PL) emission spectrum and basic material parameters, including the lattice structure and dielectric constant. The algorithm recognizes possible DAP transitions from the emission pattern in the spectrum and returns the characteristic energy of the DAP transition and the separation between the donor and acceptor sites. By testing the algorithm on the photoluminescence spectrum of hexagonal boron nitride (hBN), we show that our method is robust against experimental errors and adds new capabilities to the investigation toolbox of semiconductors and their optical properties.

36 MATERIALS SCIENCE↗
DOE OSTI2016

Automated Algorithm for J-Tpeak and Tpeak-Tend Assessment of Drug-Induced Proarrhythmia Risk

Prolongation of the heart rate corrected QT (QTc) interval is a sensitive marker of torsade de pointes risk; however it is not specific as QTc prolonging drugs that block inward currents are often not associated with torsade. Recent work demonstrated that separate analysis of the heart rate corrected J-T peak c (J-T peak c) and T peak -T end intervals can identify QTc prolonging drugs with inward current block and is being proposed as a part of a new cardiac safety paradigm for new drugs (the “CiPA” initiative). In this work, we describe an automated measurement methodology for assessment of the J-T peak c and T peak -T end intervals using the vector magnitude lead. The automated measurement methodology was developed using data from one clinical trial and was evaluated using independent data from a second clinical trial. Comparison between the automated and the prior semi-automated measurements shows that the automated algorithm reproduces the semi-automated measurements with a mean difference of single-deltas <1 ms and no difference in intra-time point variability (p for all > 0.39). In addition, the time-profile of the baseline and placebo-adjusted changes are within 1 ms for 63% of the time-points (86% within 2 ms). Importantly, the automated results lead to the same conclusions about the electrophysiological mechanisms of the studied drugs. We have developed an automated algorithm for assessment of J-T peak c and T peak -T end intervals that can be applied in clinical drug trials. Under the CiPA initiative this ECG assessment would determine if there are unexpected ion channel effects in humans compared to preclinical studies. In conclusion, the algorithm is being released as open-source software.

60 APPLIED LIFE SCIENCES↗
DOE OSTI2020

QTG-Finder2: A Generalized Machine-Learning Algorithm for Prioritizing QTL Causal Genes in Plants

Linkage mapping has been widely used to identify quantitative trait loci (QTL) in many plants and usually requires a time-consuming and labor-intensive fine mapping process to find the causal gene underlying the QTL. Previously, we described QTG-Finder, a machine-learning algorithm to rationally prioritize candidate causal genes in QTLs. Although it showed good performance, QTG-Finder could only be used in Arabidopsis and rice because of the limited number of known causal genes in other species. Here we tested the feasibility of enabling QTG-Finder to work on species that have few or no known causal genes by using orthologs of known causal genes as training set. The model trained with orthologs could recall about 64% of Arabidopsis and 83% of rice causal genes when the top 20% ranked genes were considered, which is similar to the performance of models trained with known causal genes. The average precision was 0.027 for Arabidopsis and 0.029 for rice. We further extended the algorithm to include polymorphisms in conserved non-coding sequences and gene presence/absence variation as additional features. Using this algorithm, QTG-Finder2, we trained and cross-validated Sorghum bicolor and Setaria viridis models. The S. bicolor model was validated by causal genes curated from the literature and could recall 70% of causal genes when the top 20% ranked genes were considered. Furthermore, we applied the S. viridis model and public transcriptome data to prioritize a plant height QTL and identified 13 candidate genes. QTL-Finder2 can accelerate the discovery of causal genes in any plant species and facilitate agricultural trait improvement.

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2020

A Robust Statistical Algorithm for Boundary Detection in Liquid Sprays

This work presents a statistical algorithm to detect phase boundaries in liquid sprays. Experimental data were obtained in a nonevaporating acetone spray at atmospheric conditions to minimize the refractive index gradients and associated beam steering. Mie scattering and diffuse background illumination (DBI) diagnostics are implemented to demonstrate the robustness of the approach. The analysis shows that the present algorithm yields similar results for the two different diagnostics, unlike existing threshold-based methodologies providing inconsistent results. The algorithm can be used to identify partial liquid boundaries between single-phase liquid and vapor boundaries. Thus, for each case, liquid boundaries were defined in terms of liquid probability of 100% or less than 100%. Sprays from two different injectors were analyzed to demonstrate the versatility of the methodology. Finally, a parametric study was conducted to demonstrate that motion blur can affect an accurate detection of the phase boundaries, and hence, the exposure time in the experiment must be sufficiently small.

42 ENGINEERING↗
DOE OSTI2022

A Wrapper to Use a Machine-Learning-Based Algorithm for Earthquake Monitoring

Seismology is one of the main sciences used to monitor volcanic activity worldwide. Fast, efficient, and accurate seismicity detectors are crucial to assess the activity level of a volcano in near–real time and to issue timely warnings. Traditional real–time seismic processing software uses phase onset pickers followed by a phase association algorithm to declare an event and estimate its location. The pickers typically do not identify whether the detected phase is a P or S arrival, which can have a negative impact on hypocentral location quality and complicates phase association. We implemented the deep–neural–network–based method PhaseNet to identify in real time P and S seismic waves on data from one– and three–component seismometers. We tuned the Earthworm binder_ew associator module to use the phase identification from PhaseNet to detect and locate the events, which we archive in a SeisComP3 database. We assessed the performance of the algorithm by comparing the results with existing catalogs built to monitor seismic and volcanic activity in Mayotte and the Lesser Antilles region. Our algorithm, which we refer to as PhaseWorm, showed promising results in both contexts and clearly outperformed the previous automatic method implemented in Mayotte. As a result, this innovative real–time processing system is now operational for seismicity monitoring in Mayotte and Martinique.

58 GEOSCIENCES↗
DOE OSTI2012

A Linac Simulation Code for Macro-particles Tracking and Steering Algorithm Implementation

n this paper, a linac simulation code written in Fortran90 is presented and several simu lation examples are given. This code is optimized to implement linac alignment and steering algorithms, and evaluate the accelerator errors such as RF phase and acceleration gradient, quadrupole and BPM misalignment. It can track a single particle or a bunch of particles through normal linear accelerator elements such as quadrupole, RF cavity, dipole corrector and drift space. One-to-one steering algorithm and a global alignment (steering) algorithm are implemented in this code.

Accelerators↗
DOE OSTI2012

Polar Format Algorithm: Survey of Assumptions and Approximations

Since the Polar Format Algorithm (PFA) was first introduced by Jack Walker 30 years ago, digital processing and Moore’s law have provided the means by which to process an increasing amount of data, at finer resolutions, over a larger area, and in real-time. Inherent in the polar format algorithm are assumptions that limit the focused scene size. This report presents a development of PFA for a linear frequency modulated chirp pulsed radar utilizing stretch processing to illustrate how PFA approximations are used to form an image. Also techniques to mitigate the errors resulting from the approximations are presented from a survey of literature sources. There are many techniques that are successful at increasing the focused scene size, these include image corrections made after image formation, subaperture processing, and careful selection of processing coordinates. This report only considers methods that use the polar format algorithm.

97 MATHEMATICS AND COMPUTING↗