Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “algorithms”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

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

At least 757 records · Page 42

TH-CD-206-01: Expectation-Maximization Algorithm-Based Tissue Mixture Quantification for Perfusion MRI

Purpose: To investigate the feasibility of estimating the tissue mixture perfusions and quantifying cerebral blood flow change in arterial spin labeled (ASL) perfusion MR images. Methods: The proposed perfusion MR image analysis framework consists of 5 steps: (1) Inhomogeneity correction was performed on the T1- and T2-weighted images, which are available for each studied perfusion MR dataset. (2) We used the publicly available FSL toolbox to strip off the non-brain structures from the T1- and T2-weighted MR images. (3) We applied a multi-spectral tissue-mixture segmentation algorithm on both T1- and T2-structural MR images to roughly estimate the fraction of each tissue type - white matter, grey matter and cerebral spinal fluid inside each image voxel. (4) The distributions of the three tissue types or tissue mixture across the structural image array are down-sampled and mapped onto the ASL voxel array via a co-registration operation. (5) The presented 4-dimensional expectation-maximization (4D-EM) algorithm takes the down-sampled three tissue type distributions on perfusion image data to generate the perfusion mean, variance and percentage images for each tissue type of interest. Results: Experimental results on three volunteer datasets demonstrated that the multi-spectral tissue-mixture segmentation algorithm was effective to initialize tissue mixtures from T1- and T2-weighted MR images. Compared with the conventional ASL image processing toolbox, the proposed 4D-EM algorithm not only generated comparable perfusion mean images, but also produced perfusion variance and percentage images, which the ASL toolbox cannot obtain. It is observed that the perfusion contribution percentages may not be the same as the corresponding tissue mixture volume fractions estimated in the structural images. Conclusion: A specific application to brain ASL images showed that the presented perfusion image analysis method is promising for detecting subtle changes in tissue perfusions, which is valuable for the early diagnosis of certain brain diseases, e.g. multiple sclerosis.

60 APPLIED LIFE SCIENCES↗

Evaluation of a deformable registration algorithm for subsequent lung computed tomography imaging during radiochemotherapy

Purpose: Rating both a lung segmentation algorithm and a deformable image registration (DIR) algorithm for subsequent lung computed tomography (CT) images by different evaluation techniques. Furthermore, investigating the relative performance and the correlation of the different evaluation techniques to address their potential value in a clinical setting. Methods: Two to seven subsequent CT images (69 in total) of 15 lung cancer patients were acquired prior, during, and after radiochemotherapy. Automated lung segmentations were compared to manually adapted contours. DIR between the first and all following CT images was performed with a fast algorithm specialized for lung tissue registration, requiring the lung segmentation as input. DIR results were evaluated based on landmark distances, lung contour metrics, and vector field inconsistencies in different subvolumes defined by eroding the lung contour. Correlations between the results from the three methods were evaluated. Results: Automated lung contour segmentation was satisfactory in 18 cases (26%), failed in 6 cases (9%), and required manual correction in 45 cases (66%). Initial and corrected contours had large overlap but showed strong local deviations. Landmark-based DIR evaluation revealed high accuracy compared to CT resolution with an average error of 2.9 mm. Contour metrics of deformed contours were largely satisfactory. The median vector length of inconsistency vector fields was 0.9 mm in the lung volume and slightly smaller for the eroded volumes. There was no clear correlation between the three evaluation approaches. Conclusions: Automatic lung segmentation remains challenging but can assist the manual delineation process. Proven by three techniques, the inspected DIR algorithm delivers reliable results for the lung CT data sets acquired at different time points. Clinical application of DIR demands a fast DIR evaluation to identify unacceptable results, for instance, by combining different automated DIR evaluation methods.

60 APPLIED LIFE SCIENCES↗

Fast Mesh-to-Mesh Remaps Using Hash Algorithms

Here, we explore the potential uses of hash-based algorithms in the remap operation, mapping one computational mesh onto another. We implement and test optimizations designed to reduce memory operations and compare these optimizations in order to evaluate the performance impact across different meshes. In particular, we created a new remap method that creates a structured hierarchy of hashes. Tests were run on 2D meshes on up to 14 levels of mesh refinement and hundreds of millions of cells to measure the algorithms' relative speeds under differing circumstances. We show that our methods perform two orders of magnitude better than the standard kD-tree algorithm and that on different meshes different hash methods can be optimal. We explore these algorithms on serial CPUs, GPUs using OpenCL, and multi-core CPUs using OpenMP.

97 MATHEMATICS AND COMPUTING↗

Autotuning algorithmic choice for input sensitivity

A daunting challenge faced by program performance autotuning is input sensitivity, where the best autotuned configuration may vary with different input sets. This paper presents a novel two-level input learning algorithm to tackle the challenge for an important class of autotuning problems, algorithmic autotuning. Here, the new approach uses a two-level input clustering method to automatically refine input grouping, feature selection, and classifier construction. Its design solves a series of open issues that are particularly essential to algorithmic autotuning, including the enormous optimization space, complex influence by deep input features, high cost in feature extraction, and variable accuracy of algorithmic choices. Experimental results show that the new solution yields up to a 3x speedup over using a single configuration for all inputs, and a 34x speedup over a traditional one-level method for addressing input sensitivity in program optimizations.

97 MATHEMATICS AND COMPUTING↗

A Pattern Based Algorithmic Autotuner for Graph Processing on GPUs

This paper presents Gswitch, a pattern-based algorithmic autotuning system that dynamically switches to the suitable optimization variants with negligible overhead. Its novelty is a small set of algorithmic patterns that enables configurable assembling of algorithm variants. The fast transition of Gswitch is based on a machine learning model trained from 644 real graphs from the network repository. In addition, Gswitch provides succinct programming interface which hides all low-level tuning details. We evaluate Gswitch for typical graph algorithms (BFS, CC, PR, SSSP, and BC) on Nvidia Kepler and Pascal GPUs. The results show that Gswitch runs up to 10× faster than the best configuration of the state-of-the-art programmable GPU-based graph processing libraries on ten representative graphs. Gswitch wins on 92.4% cases of 644 graph data which is the largest dataset evaluation reported to date.

HPC, graph algorithms, GPUs, auto tuning↗

Quantum Algorithm Implementations for Beginners

As quantum computers become available to the general public, the need has arisen to train a cohort of quantum programmers, many of whom have been developing classical computer programs for most of their careers. While currently available quantum computers have less than 100 qubits, quantum computing hardware is widely expected to grow in terms of qubit count, quality, and connectivity. This review aims at explaining the principles of quantum programming, which are quite different from classical programming, with straightforward algebra that makes understanding of the underlying fascinating quantum mechanical principles optional. We give an introduction to quantum computing algorithms and their implementation on real quantum hardware. We survey 20 different quantum algorithms, attempting to describe each in a succinct and self-contained fashion. We show how these algorithms can be implemented on IBM’s quantum computer, and in each case, we discuss the results of the implementation with respect to differences between the simulator and the actual hardware runs. This article introduces computer scientists, physicists, and engineers to quantum algorithms and provides a blueprint for their implementations.

97 MATHEMATICS AND COMPUTING↗

Two-Stage Estimation and Variance Modeling for Latency-Constrained Variational Quantum Algorithms

The quantum approximate optimization algorithm (QAOA) has enjoyed increasing attention in noisy, intermediate-scale quantum computing with its application to combinatorial optimization problems. QAOA has the potential to demonstrate a quantum advantage for NP-hard combinatorial optimization problems. As a hybrid quantum-classical algorithm, the classical component of QAOA resembles a simulation optimization problem in which the simulation outcomes are attainable only through a quantum computer. The simulation that derives from QAOA exhibits two unique features that can have a substantial impact on the optimization process: (i) the variance of the stochastic objective values typically decreases in proportion to the optimality gap, and (ii) querying samples from a quantum computer introduces an additional latency overhead. In this paper, we introduce a novel stochastic trust-region method derived from a derivative-free, adaptive sampling trust-region optimization method intended to efficiently solve the classical optimization problem in QAOA by explicitly taking into account the two mentioned characteristics. The key idea behind the proposed algorithm involves constructing two separate local models in each iteration: a model of the objective function and a model of the variance of the objective function. Exploiting the variance model allows us to restrict the number of communications with the quantum computer and also helps navigate the nonconvex objective landscapes typical in QAOA optimization problems. In conclusion, we numerically demonstrate the superiority of our proposed algorithm using the SimOpt library and Qiskit when we consider a metric of computational burden that explicitly accounts for communication costs.

Derivative-free Optimization↗

Inhomogeneous phase shifting: an algorithm for nonconstant phase displacements

In this work, we have developed a different algorithm than the classical one on phase-shifting interferometry. These algorithms typically use constant or homogeneous phase displacements and they can be quite accurate and insensitive to detuning, taking appropriate weight factors in the formula to recover the wrapped phase. However, these algorithms have not been considered with variable or inhomogeneous displacements. We have generalized these formulas and obtained some expressions for an implementation with variable displacements and ways to get partially insensitive algorithms with respect to these arbitrary error shifts.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Recursive algorithm for constructing antisymmetric fermionic states in first quantization mapping

We devise a deterministic quantum algorithm to produce antisymmetric states of single-particle orbitals in the first quantization mapping. Unlike sorting-based antisymmetrization algorithms, which require ordered input states and high Clifford-gate overhead, our approach initializes the state of each particle independently. For a system of $η$ particles and $N$ single-particle states, our algorithm prepares antisymmetrized states of non-trivial localized (e.g., Hartree-Fock) orbitals using $O(η^2\sqrt{N})$ $T$-gates, outperforming alternative algorithms when $η ≲ \sqrt{N}$. To achieve such scaling, we require $O(\sqrt{N})$ dirty ancilla qubits for intermediate calculations. Knowledge of the single-particle states to be antisymmetrized can be leveraged to further improve the efficiency of the circuit, and a measurement-based variant reduces gate cost by roughly a factor of two. We show example circuits for two- and three-particle systems and discuss the generalization to an arbitrary number of particles. For a specific three-particle example, we decompose the circuit into Clifford $+T$ gates and study the impact of noise on the prepared state.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗

Turbulent Mixing Simulation via a Quantum Algorithm

Probability density function (PDF) methods have been very useful in describing many physical aspects of turbulent mixing. In applications of these methods, modeled PDF transport equations are commonly simulated via classical Monte Carlo techniques, which provide estimates of moments of the PDF at arbitrary accuracy. In this paper, recently developed techniques in quantum computing and quantum enhanced measurements (quantum metrology) are used to construct a quantum algorithm that accelerates the computation of such estimates. This quantum algorithm provides a quadratic speedup over classical Monte Carlo methods in terms of the number of repetitions needed to achieve the desired precision. This paper illustrates the power of this algorithm by considering a binary scalar mixing process modeled by means of the coalescence/dispersion (C/D) closure. The equation is first simulated using classical Monte Carlo methods, where error estimates for the computation of central moments are provided. Then the quantum algorithm for this problem is simulated by sampling from the same probability distribution as that of the output of a quantum computer, and it is shown that significantly fewer resources are required to achieve the same precision. Finally, the results demonstrate potential applications of future quantum computers for simulation of turbulent mixing, and large classes of related problems.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

FIRED (Fire Events Delineation): An Open, Flexible Algorithm and Database of US Fire Events Derived from the MODIS Burned Area Product (2001–2019)

Harnessing the fire data revolution, i.e., the abundance of information from satellites, government records, social media, and human health sources, now requires complex and challenging data integration approaches. Defining fire events is key to that effort. In order to understand the spatial and temporal characteristics of fire, or the classic fire regime concept, we need to critically define fire events from remote sensing data. Events, fundamentally a geographic concept with delineated spatial and temporal boundaries around a specific phenomenon that is homogenous in some property, are key to understanding fire regimes and more importantly how they are changing. Here, we describe Fire Events Delineation (FIRED), an event-delineation algorithm, that has been used to derive fire events (N = 51,871) from the MODIS MCD64 burned area product for the coterminous US (CONUS) from January 2001 to May 2019. The optimized spatial and temporal parameters to cluster burned area pixels into events were an 11-day window and a 5-pixel (2315 m) distance, when optimized against 13,741 wildfire perimeters in the CONUS from the Monitoring Trends in Burn Severity record. The linear relationship between the size of individual FIRED and Monitoring Trends in Burn Severity (MTBS) events for the CONUS was strong (R2 = 0.92 for all events). Importantly, this algorithm is open-source and flexible, allowing the end user to modify the spatio-temporal threshold or even the underlying algorithm approach as they see fit. We expect the optimized criteria to vary across regions, based on regional distributions of fire event size and rate of spread. We describe the derived metrics provided in a new national database and how they can be used to better understand US fire regimes. The open, flexible FIRED algorithm could be utilized to derive events in any satellite product. We hope that this open science effort will help catalyze a community-driven, data-integration effort (termed OneFire) to build a more complete picture of fire.

54 ENVIRONMENTAL SCIENCES↗

Solar Flare Prediction Model with Three Machine-learning Algorithms using Ultraviolet Brightening and Vector Magnetograms

We developed a flare prediction model using machine learning, which is optimized to predict the maximum class of flares occurring in the following 24 hr. Machine learning is used to devise algorithms that can learn from and make decisions on a huge amount of data. We used solar observation data during the period 2010–2015, such as vector magnetograms, ultraviolet (UV) emission, and soft X-ray emission taken by the Solar Dynamics Observatory and the Geostationary Operational Environmental Satellite . We detected active regions (ARs) from the full-disk magnetogram, from which ∼60 features were extracted with their time differentials, including magnetic neutral lines, the current helicity, the UV brightening, and the flare history. After standardizing the feature database, we fully shuffled and randomly separated it into two for training and testing. To investigate which algorithm is best for flare prediction, we compared three machine-learning algorithms: the support vector machine, k-nearest neighbors (k-NN), and extremely randomized trees. The prediction score, the true skill statistic, was higher than 0.9 with a fully shuffled data set, which is higher than that for human forecasts. It was found that k-NN has the highest performance among the three algorithms. The ranking of the feature importance showed that previous flare activity is most effective, followed by the length of magnetic neutral lines, the unsigned magnetic flux, the area of UV brightening, and the time differentials of features over 24 hr, all of which are strongly correlated with the flux emergence dynamics in an AR.

79 ASTRONOMY AND ASTROPHYSICS↗

Application of Fireworks Algorithm in Gamma-Ray Spectrum Fitting for Radioisotope Identification

We present that identification of radioisotopic signature patterns in gamma-ray spectra is of paramount importance in various applications of gamma spectroscopy. Therefore, there are several active research efforts to develop accurate and precise methods to perform automated spectroscopic analysis and subsequently recognize gamma-ray signatures. In this work, the authors present a new method for radioisotope identification in gamma-ray spectra obtained with a low resolution radiation detector. The method fits the obtained spectrum with a linear combina-tion of known template signature patterns. Coefficients of the linear combination are evaluated by computing the solution of a single objective optimization problem, whose objective is the Theil-1 inequality coefficient. Optimization of the problem is performed by the Fireworks Algorithm, which identifies a set of coefficients that minimize the Theil-1 value. The computed coefficients are statistically tested for being significantly different than zero or not, and if at least one is found to be zero then the Fireworks Algorithm is used to reiterate fitting using the non-zero templates. Fitting iterations are continued up to the point that no linear coefficients are found to be zero. The output of the method is a list that contains the radioisotopes that have been identified in the measured spectrum. The method is tested on a set of both simulated and real experimental gamma-ray spectra comprised of a variety of isotopes, and compared to a multiple linear regression fitting, and genetic algorithm Theil-1 based fitting. Finally, results demonstrate the potentiality of the Fireworks Algorithm based method, expressed as higher accuracy and similar precision over the other two tested methodologies for radioisotope signature pattern identification in the framework of gamma-ray spectrum fitting.

Theil Coefficient↗

Comparing Coordinated Garbage Collection Algorithms for Arrays of Solid-state Drives

Solid-State Drives (SSDs) offer significant performance improvements over hard disk drives (HDD) on a number of workloads. The frequency of garbage collection (GC) activity is directly correlated with the pattern, frequency, and volume of write requests, and scheduling of GC is controlled by logic internal to the SSD. SSDs can exhibit significant performance degradations when garbage collection (GC) conflicts with an ongoing I/O request stream. When using SSDs in a RAID array, the lack of coordination of the local GC processes amplifies these performance degradations. No RAID controller or SSD available today has the technology to overcome this limitation. In our previous work, we presented a Global Garbage Collection (GGC) mechanism to improve response times and reduce performance variability for a RAID array of SSDs. A coordination method is employed so that GCs in the array can run at the same time. The coordination can exhibit substantial performance improvement. In this paper, we explore various GC coordination algorithms. We develop reactive and proactive GC coordination algorithms and evaluate their I/O performance and block erase counts for various workloads. We show that a proactive GC coordination algorithm can improve the I/O response times by up to 9% further and increase the lifetime of SSDs by reducing the number of block erase counts by up to 79% compared to a reactive algorithm.

99 GENERAL AND MISCELLANEOUS↗

Rayleigh wave numerical dispersion in a 3D finite-difference algorithm.

A Rayleigh wave propagates laterally without dispersion in the vicinity of the plane stress-free surface of a homogeneous and isotropic elastic halfspace. The phase speed is independent of frequency and depends only on the Poisson ratio of the medium. However, after temporal and spatial discretization, a Rayleigh wave simulated by a 3D staggered-grid finite-difference (FD) seismic wave propagation algorithm suffers from frequency- and direction-dependent numerical dispersion. The magnitude of this dispersion depends critically on FD algorithm implementation details. Nevertheless, proper gridding can control numerical dispersion to within an acceptable level, leading to accurate Rayleigh wave simulations. Many investigators have derived dispersion relations appropriate for body wave propagation by various FD algorithms. However, the situation for surface waves is less well-studied. We have devised a numerical search procedure to estimate Rayleigh phase speed and group speed curves for 3D O(2,2) and O(2,4) staggered-grid FD algorithms. In contrast with the continuous time-space situation (where phase speed is obtained by extracting the appropriate root of the Rayleigh cubic), we cannot develop a closed-form mathematical formula governing the phase speed. Rather, we numerically seek the particular phase speed that leads to a solution of the discrete wave propagation equations, while holding medium properties, frequency, horizontal propagation direction, and gridding intervals fixed. Group speed is then obtained by numerically differentiating the phase speed with respect to frequency. The problem is formulated for an explicit stress-free surface positioned at two different levels within the staggered spatial grid. Additionally, an interesting variant involving zero-valued medium properties above the surface is addressed. We refer to the latter as an implicit free surface. Our preliminary conclusion is that an explicit free surface, implemented with O(4) spatial FD operators and positioned at the level of the compressional stress components, leads to superior numerical dispersion performance. Phase speeds measured from fixed-frequency synthetic seismograms agree very well with the numerical predictions.

58 GEOSCIENCES↗

Design and Implementation of Broadcast Algorithms for Extreme-Scale Systems

The scalability and performance of collective communication operations limit the scalability and performance of many scientific applications. This paper presents two new blocking and nonblocking Broadcast algorithms for communicators with arbitrary communication topology, and studies their performance. These algorithms benefit from increased concurrency and a reduced memory footprint, making them suitable for use on large-scale systems. Measuring small, medium, and large data Broadcasts on a Cray-XT5, using 24,576 MPI processes, the Cheetah algorithms outperform the native MPI on that system by 51%, 69%, and 9%, respectively, at the same process count. These results demonstrate an algorithmic approach to the implementation of the important class of collective communications, which is high performing, scalable, and also uses resources in a scalable manner.

99 GENERAL AND MISCELLANEOUS↗

Singular value decomposition utilizing parallel algorithms on graphical processors

One of the current challenges in underwater acoustic array signal processing is the detection of quiet targets in the presence of noise. In order to enable robust detection, one of the key processing steps requires data and replica whitening. This, in turn, involves the eigen-decomposition of the sample spectral matrix, Cx = 1/K xKX(k)XH(k) where X(k) denotes a single frequency snapshot with an element for each element of the array. By employing the singular value decomposition (SVD) method, the eigenvectors and eigenvalues can be determined directly from the data without computing the sample covariance matrix, reducing the computational requirements for a given level of accuracy (van Trees, Optimum Array Processing). (Recall that the SVD of a complex matrix A involves determining V, , and U such that A = U VH where U and V are orthonormal and is a positive, real, diagonal matrix containing the singular values of A. U and V are the eigenvectors of AAH and AHA, respectively, while the singular values are the square roots of the eigenvalues of AAH.) Because it is desirable to be able to compute these quantities in real time, an efficient technique for computing the SVD is vital. In addition, emerging multicore processors like graphical processing units (GPUs) are bringing parallel processing capabilities to an ever increasing number of users. Since the computational tasks involved in array signal processing are well suited for parallelization, it is expected that these computations will be implemented using GPUs as soon as users have the necessary computational tools available to them. Thus, it is important to have an SVD algorithm that is suitable for these processors. This work explores the effectiveness of two different parallel SVD implementations on an NVIDIA Tesla C2050 GPU (14 multiprocessors, 32 cores per multiprocessor, 1.15 GHz clock - peed). The first algorithm is based on a two-step algorithm which bidiagonalizes the matrix using Householder transformations, and then diagonalizes the intermediate bidiagonal matrix through implicit QR shifts. This is similar to that implemented for real matrices by Lahabar and Narayanan ("Singular Value Decomposition on GPU using CUDA", IEEE International Parallel Distributed Processing Symposium 2009). The implementation is done in a hybrid manner, with the bidiagonalization stage done using the GPU while the diagonalization stage is done using the CPU, with the GPU used to update the U and V matrices. The second algorithm is based on a one-sided Jacobi scheme utilizing a sequence of pair-wise column orthogonalizations such that A is replaced by AV until the resulting matrix is sufficiently orthogonal (that is, equal to U ). V is obtained from the sequence of orthogonalizations, while can be found from the square root of the diagonal elements of AH A and, once is known, U can be found from column scaling the resulting matrix. These implementations utilize CUDA Fortran and NVIDIA's CUB LAS library. The primary goal of this study is to quantify the comparative performance of these two techniques against themselves and other standard implementations (for example, MATLAB). Considering that there is significant overhead associated with transferring data to the GPU and with synchronization between the GPU and the host CPU, it is also important to understand when it is worthwhile to use the GPU in terms of the matrix size and number of concurrent SVDs to be calculated.

99 GENERAL AND MISCELLANEOUS↗

DEVELOPMENT AND TESTING OF FAULT-DIAGNOSIS ALGORITHMS FOR REACTOR PLANT SYSTEMS

Argonne National Laboratory is further developing fault diagnosis algorithms for use by the operator of a nuclear plant to aid in improved monitoring of overall plant condition and performance. The objective is better management of plant upsets through more timely, informed decisions on control actions with the ultimate goal of improved plant safety, production, and cost management. Integration of these algorithms with visual aids for operators is taking place through a collaboration under the concept of an operator advisory system. This is a software entity whose purpose is to manage and distill the enormous amount of information an operator must process to understand the plant state, particularly in off-normal situations, and how the state trajectory will unfold in time. The fault diagnosis algorithms were exhaustively tested using computer simulations of twenty different faults introduced into the chemical and volume control system (CVCS) of a pressurized water reactor (PWR). The algorithms are unique in that each new application to a facility requires providing only the piping and instrumentation diagram (PID) and no other plant-specific information; a subject-matter expert is not needed to install and maintain each instance of an application. The testing approach followed accepted procedures for verifying and validating software. It was shown that the code satisfies its functional requirement which is to accept sensor information, identify process variable trends based on this sensor information, and then to return an accurate diagnosis based on chains of rules related to these trends. The validation and verification exercise made use of GPASS, a one-dimensional systems code, for simulating CVCS operation. Plant components were failed and the code generated the resulting plant response. Parametric studies with respect to the severity of the fault, the richness of the plant sensor set, and the accuracy of sensors were performed as part of the validation exercise. The background and overview of the software will be presented to give an overview of the approach. Following, the verification and validation effort using the GPASS code for simulation of plant transients including a sensitivity study on important parameters will be presented

Fault Diagnosis Algorithm↗