Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “fast 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 379 records · Page 21
All sourcesNASA NTRSDOE OSTI
NASA NTRS1989

Efficient mapping algorithms for scheduling robot inverse dynamics computation on a multiprocessor system

Two efficient mapping algorithms for scheduling the robot inverse dynamics computation consisting of m computational modules with precedence relationship to be executed on a multiprocessor system consisting of p identical homogeneous processors with processor and communication costs to achieve minimum computation time are presented. An objective function is defined in terms of the sum of the processor finishing time and the interprocessor communication time. The minimax optimization is performed on the objective function to obtain the best mapping. This mapping problem can be formulated as a combination of the graph partitioning and the scheduling problems; both have been known to be NP-complete. Thus, to speed up the searching for a solution, two heuristic algorithms were proposed to obtain fast but suboptimal mapping solutions. The first algorithm utilizes the level and the communication intensity of the task modules to construct an ordered priority list of ready modules and the module assignment is performed by a weighted bipartite matching algorithm. For a near-optimal mapping solution, the problem can be solved by the heuristic algorithm with simulated annealing. These proposed optimization algorithms can solve various large-scale problems within a reasonable time. Computer simulations were performed to evaluate and verify the performance and the validity of the proposed mapping algorithms. Finally, experiments for computing the inverse dynamics of a six-jointed PUMA-like manipulator based on the Newton-Euler dynamic equations were implemented on an NCUBE/ten hypercube computer to verify the proposed mapping algorithms. Computer simulation and experimental results are compared and discussed.

Lee, C. S. G.↗
NASA NTRS1998

A New Approximate Chimera Donor Cell Search Algorithm

The objectives of this study were to develop chimera-based full potential methodology which is compatible with overflow (Euler/Navier-Stokes) chimera flow solver and to develop a fast donor cell search algorithm that is compatible with the chimera full potential approach. Results of this work included presenting a new donor cell search algorithm suitable for use with a chimera-based full potential solver. This algorithm was found to be extremely fast and simple producing donor cells as fast as 60,000 per second.

Holst, Terry L.↗
DOE OSTI2026

Demonstration and performance of an online data selection algorithm for liquid argon time projection chambers using MicroBooNE

The MicroBooNE detector is a liquid argon time projection chamber (LArTPC) that produces three-dimensional images of particle interactions using ionization charge collected by anode wire plane arrays and scintillation light collected by a light detection system. In addition to testing long-standing experimental neutrino anomalies and performing measurements of neutrino interactions with argon nuclei using the Fermilab Booster Neutrino Beam, MicroBooNE aims to develop methodologies for rare beyond the Standard Model and off-beam physics searches. Looking ahead to the upcoming Deep Underground Neutrino Experiment (DUNE), with MicroBooNE serving as a valuable testbed, achieving high sensitivity and livetime for off-beam physics while satisfying data processing and storage constraints will require data-driven, intelligent, and online or real-time data selection techniques. These techniques are essential for reducing data rates and preserving rare signals with high accuracy. In this paper, we describe a fast data selection algorithm suitable for online execution to identify electrons from stopping cosmic ray muons in the MicroBooNE detector utilizing ionization charge information, and present its performance. This represents the first demonstration of online data selection in a LArTPC using real data and charge information exclusively and provides an important proof-of-principle for applying such techniques to other LArTPC experiments such as the Short-Baseline Near Detector and DUNE.

Abratenko, P. [Tufts U. (main)]↗
DOE OSTI2023

Computing rank‐revealing factorizations of matrices stored out‐of‐core

This paper describes efficient algorithms for computing rank-revealing factorizations of matrices that are too large to fit in main memory (RAM), and must instead be stored on slow external memory devices such as disks (out-of-core or out-of-memory). Traditional algorithms for computing rank-revealing factorizations (such as the column pivoted QR factorization and the singular value decomposition) are very communication intensive as they require many vector-vector and matrix-vector operations, which become prohibitively expensive when data is not in RAM. Randomization allows to reformulate new methods so that large contiguous blocks of the matrix are processed in bulk. The paper describes two distinct methods. The first is a blocked version of column pivoted Householder QR, organized as a “left-looking” method to minimize the number of the expensive write operations. The second method results employs a UTV factorization. It is organized as an algorithm-by-blocks to overlap computations and I/O operations. As it incorporates power iterations, it is much better at revealing the numerical rank. Numerical experiments on several computers demonstrate that the new algorithms are almost as fast when processing data stored on slow memory devices as traditional algorithms are for data stored in RAM.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS2012

Real-Time Adaptive Lossless Hyperspectral Image Compression using CCSDS on Parallel GPGPU and Multicore Processor Systems

The proposed CCSDS (Consultative Committee for Space Data Systems) Lossless Hyperspectral Image Compression Algorithm was designed to facilitate a fast hardware implementation. This paper analyses that algorithm with regard to available parallelism and describes fast parallel implementations in software for GPGPU and Multicore CPU architectures. We show that careful software implementation, using hardware acceleration in the form of GPGPUs or even just multicore processors, can exceed the performance of existing hardware and software implementations by up to 11x and break the real-time barrier for the first time for a typical test application.

realtime↗
DOE OSTI2024

Multi-slice electron ptychographic tomography for three-dimensional phase-contrast microscopy beyond the depth of focus limits

Electron ptychography is a powerful computational method for atomic-resolution imaging with high contrast for weakly and strongly scattering elements. Modern algorithms coupled with fast and efficient detectors allow imaging specimens with tens of nanometers thicknesses with sub-0.5 Ångstrom lateral resolution. However, the axial resolution in these approaches is currently limited to a few nanometers, limiting their ability to solve novel atomic structures ab initio. Here, we experimentally demonstrate multi-slice ptychographic electron tomography, which allows atomic resolution three-dimensional phase-contrast imaging in a volume surpassing the depth of field limits. We reconstruct tilt-series 4D-STEM measurements of a $\mathrm{Co_3O_4}$ nanocube, yielding 2 Å axial and 0.7 Å transverse resolution in a reconstructed volume of $\mathrm{(18.2\,nm)^3}$. Our results demonstrate a 13.5-fold improvement in axial resolution compared to multi-slice ptychography while retaining the atomic lateral resolution and the capability to image volumes beyond the depth of field limit. Multi-slice ptychographic electron tomography significantly expands the volume of materials accessible using high-resolution electron microscopy. We discuss further experimental and algorithmic improvements necessary to also resolve single weakly scattering atoms in 3D.

36 MATERIALS SCIENCE↗
DOE OSTI2020

Distributed non-negative matrix factorization with determination of the number of latent features

The holistic analysis and understanding of the latent (that is, not directly observable) variables and patterns buried in large datasets is crucial for data-driven science, decision making and emergency response. Such exploratory analyses require devising unsupervised learning methods for data mining and extraction of the latent features, and non-negative matrix factorization (NMF) is one of the prominent such methods. NMF is based on compute-intense non-convex constrained minimization, which, for large datasets requires fast and distributed algorithms. However, current parallel implementations of NMF fail to estimate the number of latent features. In practice, identifying these features is both difficult and significant for pattern recognition and latent feature analysis, especially for large dense matrices. Here, we introduce a distributed NMF algorithm coupled with distributed custom clustering followed by a stability analysis on dense data, which we call DnMFk, to determine the number of latent variables. The results on synthetic data and the classical Swimmer data set demonstrate the accuracy of model determination while scaling nearly linearly across multiple processors for large data. Further, we employ DnMFk to determine the number of hidden features from a terabyte matrix.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Epistatic Net allows the sparse spectral regularization of deep neural networks for inferring fitness functions

Abstract Despite recent advances in high-throughput combinatorial mutagenesis assays, the number of labeled sequences available to predict molecular functions has remained small for the vastness of the sequence space combined with the ruggedness of many fitness functions. While deep neural networks (DNNs) can capture high-order epistatic interactions among the mutational sites, they tend to overfit to the small number of labeled sequences available for training. Here, we developed Epistatic Net (EN), a method for spectral regularization of DNNs that exploits evidence that epistatic interactions in many fitness functions are sparse. We built a scalable extension of EN, usable for larger sequences, which enables spectral regularization using fast sparse recovery algorithms informed by coding theory. Results on several biological landscapes show that EN consistently improves the prediction accuracy of DNNs and enables them to outperform competing models which assume other priors. EN estimates the higher-order epistatic interactions of DNNs trained on massive sequence spaces-a computational problem that otherwise takes years to solve.

Aghazadeh, Amirali (ORCID:0000000302230873)↗
DOE OSTI2025

Leveraging prior mean models for faster Bayesian optimization of particle accelerators

Tuning particle accelerators is a challenging and time-consuming task that can be automated and carried out efficiently using suitable optimization algorithms, such as model-based Bayesian optimization techniques. One of the major advantages of Bayesian algorithms is the ability to incorporate prior information about beam physics and historical behavior into the model used to make control decisions. In this work, we examine incorporating prior accelerator physics information into Bayesian optimization algorithms by utilizing fast executing, neural network models trained on simulated or historical datasets as prior mean functions in Gaussian process models. We show that in ideal cases, this technique substantially increases convergence speed to optimal solutions in high-dimensional tuning parameter spaces. Additionally, we demonstrate that even in non-ideal cases, where prior models of beam dynamics do not exactly match experimental conditions, the use of this technique can still enhance convergence speed. Finally, we demonstrate how these methods can be used to improve optimization in practical applications, such as transferring information gained from beam dynamics simulations to online control of the LCLS injector, and transferring knowledge gained from experimental measurements across different operating modes, such as accelerating different ion species at the ATLAS heavy ion accelerator.

43 PARTICLE ACCELERATORS↗
DOE OSTI2020

Fast transformations between configuration state function and Slater determinant bases for direct configuration interaction

A hybrid configuration state function (CSF) and Slater determinant (SD) basis full configuration interaction (CI) program was developed to simultaneously take advantage of fast SD basis algorithms for σ = Hc formation and the smaller CI vector length and more robust convergence offered by a CSF basis. Graphical processing unit acceleration of the direct CSF-SD and SD-CSF basis transformation algorithms ensures that the combined transformation time per iteration relative to σ formation is small (~15%). In addition to the obvious benefits of reducing the memory footprint of the CI vector, additional computational savings are demonstrated that rely directly on the size of the CI basis, in one particular case reducing the CI time-to-solution of a HF-CAS-(16,16)-CI/6-31G calculation of ethylene from 1954.79 s to 956 s by using a CSF basis, a 2.0× speedup.

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

Performance of modern color decompositions for standard candle LHC tree amplitudes

In the last decade, developments of matrix element and phase space generators have focused on providing good efficiency and maximal flexibility and automation for a wide range of physical processes. However, as recent studies have shown, they are a major bottleneck in the established Monte Carlo event generator toolchains. With the advent of the HL-LHC and ever rising precision requirements, future developments will need to focus on computational performance, especially at intermediate to large jet multiplicities. We present the novel BlockGen family of fast matrix element algorithms that are amenable for GPU acceleration, making use of modern, minimal color decompositions. Moreover, we discuss the performance achieved for standard candle processes such as V +jets and tt̄+jets production.

Bothmann, E. [Gottingen U.]↗
DOE OSTI2020

Reconstruction of signal amplitudes in the CMS electromagnetic calorimeter in the presence of overlapping proton-proton interactions

A template fitting technique for reconstructing the amplitude of signals produced by the lead tungstate crystals of the CMS electromagnetic calorimeter is described. This novel approach is designed to suppress the contribution to the signal of the increased number of out-of-time interactions per beam crossing following the reduction of the accelerator bunch spacing from 50 to 25 ns at the start of Run 2 of the LHC. Execution of the algorithm is sufficiently fast for it to be employed in the CMS high-level trigger. It is also used in the offline event reconstruction. Results obtained from simulations and from Run 2 collision data (2015–2018) demonstrate a substantial improvement in the energy resolution of the calorimeter over a range of energies extending from a few GeV to several tens of GeV.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗
DOE OSTI2020

Exact and fast calculation of the X-ray pair distribution function

A fast and exact algorithm to calculate the powder pair distribution function (PDF) for the case of periodic structures is presented. The new algorithm calculates the PDF by a detour via reciprocal space. The calculated normalized total powder diffraction pattern is transferred into the PDF via the sine Fourier transform. The calculation of the PDF via the powder pattern avoids the conventional simplification of X-ray and electron atomic form factors. It is thus exact for these types of radiation, as is the conventional calculation for the case of neutron diffraction. The new algorithm further improves the calculation speed. Additional advantages are the improved detection of errors in the primary data, the handling of preferred orientation, the ease of treatment of magnetic scattering and a large improvement to accommodate more complex instrumental resolution functions.

36 MATERIALS SCIENCE↗
DOE OSTI2026

Rolling Root Mean Square Based Multimodal Anomaly Detection for Real Time Monitoring of Smart Grid

Reliable real-time monitoring is valuable for maintaining the operational integrity of modern electrical smart grids. Deployment of heterogeneous sensing technologies in substations has enabled high-resolution, multichannel waveform monitoring, but also introduces challenges for anomaly detection due to noise, baseline drift, and modality-dependent signal characteristics. In this work, we present a computationally efficient unsupervised method for multimodal event detection based on Rolling Root Mean Square based Event Detection (RRMSED). The method is developed using in-house, field deployed sensors collecting data at a utility substation. The sensing system comprises voltage and current sensors, triaxial accelerometers, and magnetometers, collectively capturing electrical, vibrational, and magnetic waveform measurements at high temporal resolution. RRMSED operates by extracting rolling RMS energy features and their first-order temporal differences from consecutive waveform segments for each channel and then applying channel-specific statistical thresholds learned from historical data. A persistence-based exceedance logic is employed to robustly identify transient events while suppressing impulsive noise, and to provide precise temporal localization with high resolution. The framework is designed for continuous server-side operation and can be deployed in real time without requiring complex models. Experiments on simulated waveform data with known ground truth demonstrate low false positive (FP) and false negative (FN) rates. Application to real substation data shows RRMSED to identify events that are not captured by conventional monitoring indicators including fast transient detection algorithm currently deployed in the system. These results indicate that rolling RMS based features provide an effective and practical basis for real-time multimodal event detection in smart-grid substations.

Mukherjee, Subrata [ORNL] (ORCID:0000000309930338)↗
DOE OSTI2020

Computationally Efficient Decompositions of Oblique Projection Matrices

Oblique projection matrices arise in problems in weighted least squares, signal processing, and optimization. While these matrices can be potentially very large, their low-rank structure can be exploited for efficient computation. Here, we propose fast and scalable algorithms for computing their eigendecomposition and singular value decomposition (SVD). Numerical experiments that compare our proposed approaches to existing methods, including randomized SVD, are presented. In addition, we test their accuracy on linear systems from equality constrained optimization problems.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Can changes in deformation regimes be inferred from crystallographic preferred orientations in polar ice?

Creep due to ice flow is generally thought to be the main cause for the formation of crystallographic preferred orientations (CPOs) in polycrystalline anisotropic ice. However, linking the development of CPOs to the ice flow history requires a proper understanding of the ice aggregate's microstructural response to flow transitions. In this contribution the influence of ice deformation history on the CPO development is investigated by means of full-field numerical simulations at the microscale. We simulate the CPO evolution of polycrystalline ice under combinations of two consecutive deformation events up to high strain, using the code VPFFT (visco-plastic fast Fourier transform algorithm) within ELLE. A volume of ice is first deformed under coaxial boundary conditions, which results in a CPO. The sample is then subjected to different boundary conditions (coaxial or non-coaxial) in order to observe how the deformation regime switch impacts the CPO. The model results indicate that the second flow event tends to destroy the first, inherited fabric with a range of transitional fabrics. However, the transition is slow when crystallographic axes are critically oriented with respect to the second imposed regime. Therefore, interpretations of past deformation events from observed CPOs must be carried out with caution, particularly in areas with complex deformation histories.

54 ENVIRONMENTAL SCIENCES↗
NASA NTRS1972

Unique solutions of spacecraft structural dynamics problems.

New ideas and techniques recently put to use at the Jet Propulsion Laboratory for structural dynamics of spacecraft are presented. This paper deals with practical problems rather than elaborate mathematical theories and is concerned with the system approach for structural dynamics, an approach which has received attention in the recent past owing to the use of the fast Fourier transform algorithm which permits an economical use of digital computers. Concept of dynamics mass in the frequency domain is introduced. Reaction forces and moments at the base of a spacecraft in boosted flight configuration are determined. A combination of digital and analog techniques for special problems is presented. The examples reported are on actual spacecraft.

Trubert, M. R.↗