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 775 records · Page 43

SU-F-J-148: A Collapsed Cone Algorithm Can Be Used for Quality Assurance for Monaco Treatment Plans for the MR-Linac

Purpose: Treatment plans for the MR-linac, calculated in Monaco v5.19, include direct simulation of the effects of the 1.5T B{sub 0}-field. We tested the feasibility of using a collapsed-cone (CC) algorithm in Oncentra, which does not account for effects of the B{sub 0}-field, as a fast online, independent 3D check of dose calculations. Methods: Treatment plans for six patients were generated in Monaco with a 6 MV FFF beam and the B{sub 0}-field. All plans were recalculated with a CC model of the same beam. Plans for the same patients were also generated in Monaco without the B{sub 0}-field. The mean dose (Dmean) and doses to 10% (D10%) and 90% (D90%) of the volume were determined, as percentages of the prescribed dose, for target volumes and OARs in each calculated dose distribution. Student’s t-tests between paired parameters from Monaco plans and corresponding CC calculations were performed. Results: Figure 1 shows an example of the difference between dose distributions calculated in Monaco, with the B{sub 0}-field, and the CC algorithm. Figure 2 shows distributions of (absolute) difference between parameters for Monaco plans, with the B{sub 0}-field, and CC calculations. The Dmean and D90% values for the CTVs and PTVs were significantly different, but differences in dose distributions arose predominantly at the edges of the target volumes. Inclusion of the B{sub 0}-field had little effect on agreement of the Dmean values, as illustrated by Figure 3, nor on agreement of the D10% and D90% values. Conclusion: Dose distributions recalculated with a CC algorithm show good agreement with those calculated with Monaco, for plans both with and without the B{sub 0}-field, indicating that the CC algorithm could be used to check online treatment planning for the MRlinac. Agreement for a wider range of treatment sites, and the feasibility of using the γ-test as a simple pass/fail criterion, will be investigated.

60 APPLIED LIFE SCIENCES↗

SU-F-J-198: A Cross-Platform Adaptation of An a Priori Scatter Correction Algorithm for Cone-Beam Projections to Enable Image- and Dose-Guided Proton Therapy

Purpose: Cone-beam CT (CBCT) imaging may enable image- and dose-guided proton therapy, but is challenged by image artefacts. The aim of this study was to demonstrate the general applicability of a previously developed a priori scatter correction algorithm to allow CBCT-based proton dose calculations. Methods: The a priori scatter correction algorithm used a plan CT (pCT) and raw cone-beam projections acquired with the Varian On-Board Imager. The projections were initially corrected for bow-tie filtering and beam hardening and subsequently reconstructed using the Feldkamp-Davis-Kress algorithm (rawCBCT). The rawCBCTs were intensity normalised before a rigid and deformable registration were applied on the pCTs to the rawCBCTs. The resulting images were forward projected onto the same angles as the raw CB projections. The two projections were subtracted from each other, Gaussian and median filtered, and then subtracted from the raw projections and finally reconstructed to the scatter-corrected CBCTs. For evaluation, water equivalent path length (WEPL) maps (from anterior to posterior) were calculated on different reconstructions of three data sets (CB projections and pCT) of three parts of an Alderson phantom. Finally, single beam spot scanning proton plans (0–360 deg gantry angle in steps of 5 deg; using PyTRiP) treating a 5 cm central spherical target in the pCT were re-calculated on scatter-corrected CBCTs with identical targets. Results: The scatter-corrected CBCTs resulted in sub-mm mean WEPL differences relative to the rigid registration of the pCT for all three data sets. These differences were considerably smaller than what was achieved with the regular Varian CBCT reconstruction algorithm (1–9 mm mean WEPL differences). Target coverage in the re-calculated plans was generally improved using the scatter-corrected CBCTs compared to the Varian CBCT reconstruction. Conclusion: We have demonstrated the general applicability of a priori CBCT scatter correction, potentially opening for CBCT-based image/dose-guided proton therapy, including adaptive strategies. Research agreement with Varian Medical Systems, not connected to the present project.

60 APPLIED LIFE SCIENCES↗

SU-G-BRA-02: Development of a Learning Based Block Matching Algorithm for Ultrasound Tracking in Radiotherapy

Purpose: To develop an ultrasound learning-based tracking algorithm with the potential to provide real-time motion traces of anatomy-based fiducials that may aid in the effective delivery of external beam radiation. Methods: The algorithm was developed in Matlab R2015a and consists of two main stages: reference frame selection, and localized block matching. Immediately following frame acquisition, a normalized cross-correlation (NCC) similarity metric is used to determine a reference frame most similar to the current frame from a series of training set images that were acquired during a pretreatment scan. Segmented features in the reference frame provide the basis for the localized block matching to determine the feature locations in the current frame. The boundary points of the reference frame segmentation are used as the initial locations for the block matching and NCC is used to find the most similar block in the current frame. The best matched block locations in the current frame comprise the updated feature boundary. The algorithm was tested using five features from two sets of ultrasound patient data obtained from MICCAI 2014 CLUST. Due to the lack of a training set associated with the image sequences, the first 200 frames of the image sets were considered a valid training set for preliminary testing, and tracking was performed over the remaining frames. Results: Tracking of the five vessel features resulted in an average tracking error of 1.21 mm relative to predefined annotations. The average analysis rate was 15.7 FPS with analysis for one of the two patients reaching real-time speeds. Computations were performed on an i5-3230M at 2.60 GHz. Conclusion: Preliminary tests show tracking errors comparable with similar algorithms at close to real-time speeds. Extension of the work onto a GPU platform has the potential to achieve real-time performance, making tracking for therapy applications a feasible option. This work is partially funded by NIH grant R01CA190298.

60 APPLIED LIFE SCIENCES↗

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↗

New Efficient Sparse Space Time Algorithms for Superparameterization on Mesoscales

Superparameterization (SP) is a large-scale modeling system with explicit representation of small-scale and mesoscale processes provided by a cloud-resolving model (CRM) embedded in each column of a large-scale model. New efficient sparse space-time algorithms based on the original idea of SP are presented. The large-scale dynamics are unchanged, but the small-scale model is solved in a reduced spatially periodic domain to save the computation cost following a similar idea applied by one of the authors for aquaplanet simulations. In addition, the time interval of integration of the small-scale model is reduced systematically for the same purpose, which results in a different coupling mechanism between the small- and large-scale models. The new algorithms have been applied to a stringent two-dimensional test suite involving moist convection interacting with shear with regimes ranging from strong free and forced squall lines to dying scattered convection as the shear strength varies. The numerical results are compared with the CRM and original SP. It is shown here that for all of the regimes of propagation and dying scattered convection, the large-scale variables such as horizontal velocity and specific humidity are captured in a statistically accurate way (pattern correlations above 0.75) based on space-time reduction of the small-scale models by a factor of 1/3; thus, the new efficient algorithms for SP result in a gain of roughly a factor of 10 in efficiency while retaining a statistical accuracy on the large-scale variables. Even the models with 1/6 reduction in space-time with a gain of 36 in efficiency are able to distinguish between propagating squall lines and dying scattered convection with a pattern correlation above 0.6 for horizontal velocity and specific humidity. These encouraging results suggest the possibility of using these efficient new algorithms for limited-area mesoscale ensemble forecasting.

99 GENERAL AND MISCELLANEOUS↗

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↗