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.

SourceResearch connectionFrom yearThrough year

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

At least 289 records · Page 16

All sources NASA NTRS DOE OSTI

NASA NTRS2011

A Universal Tare Load Prediction Algorithm for Strain-Gage Balance Calibration Data Analysis

An algorithm is discussed that may be used to estimate tare loads of wind tunnel strain-gage balance calibration data. The algorithm was originally developed by R. Galway of IAR/NRC Canada and has been described in the literature for the iterative analysis technique. Basic ideas of Galway's algorithm, however, are universally applicable and work for both the iterative and the non-iterative analysis technique. A recent modification of Galway's algorithm is presented that improves the convergence behavior of the tare load prediction process if it is used in combination with the non-iterative analysis technique. The modified algorithm allows an analyst to use an alternate method for the calculation of intermediate non-linear tare load estimates whenever Galway's original approach does not lead to a convergence of the tare load iterations. It is also shown in detail how Galway's algorithm may be applied to the non-iterative analysis technique. Hand load data from the calibration of a six-component force balance is used to illustrate the application of the original and modified tare load prediction method. During the analysis of the data both the iterative and the non-iterative analysis technique were applied. Overall, predicted tare loads for combinations of the two tare load prediction methods and the two balance data analysis techniques showed excellent agreement as long as the tare load iterations converged. The modified algorithm, however, appears to have an advantage over the original algorithm when absolute voltage measurements of gage outputs are processed using the non-iterative analysis technique. In these situations only the modified algorithm converged because it uses an exact solution of the intermediate non-linear tare load estimate for the tare load iteration.

balance calibration analysis↗

NASA NTRS2017

Computationally Efficient Motion Planning Algorithms for Agile Autonomous Vehicles in Cluttered Environments

Fast, real-time motion planning of an agile, autonomous vehicle in a cluttered environment, with many geometrically-fixed obstacles, is a very complex problem, especially because of the vehicle dynamics constraints and resource constrained computational capabilities onboard the vehicle. In this paper, we present computationally-efficient versions of our novel motion planning algorithm called the Spherical Expansion and Sequential Convex Programming (SE–SCP) algorithm. The SE–SCP algorithm first uses a spherical-expansion-based randomized sampling algorithm to explore the workspace. Oncea path is found from the start position to the goal position, the algorithm computes a locally optimal trajectory, within its homotopy class for a desired cost function, by solving a sequence of convex optimization problems. Thus, the SE–SCP algorithm is anytime locally optimal and the trajectory is globally optimal if the number of samples tends to infinity. In this paper, we further enhance the computational efficiency of the SE–SCP algorithm using uni-directional and bi-directional rewiring techniques. We also present a detailed proof of the local optimality characteristics of the new SE–SCP algorithms for aspecial case of vehicle dynamics. Simulation examples involving quadrotor and spacecraft help demonstrate the effectiveness of our new algorithms.

Bandyopadhyay, Saptarshi↗

NASA NTRS2022

Merging of the Case 2 Regional Coast Colour and Maximum‑Peak Height Chlorophyll‑a Algorithms: Validation and Demonstration of Satellite‑derived Retrievals Across US Lakes

Water quality monitoring is relevant for protecting the designated, or beneficial uses, of water such as drinking, aquatic life, recreation, irrigation, and food supply that support the economy, human well-being, and aquatic ecosystem health. Managing finite water resources to support these designated uses requires information on water quality so that managers can make sustainable decisions. Chlorophyll-a (chl-a, µg L−1) concentration can serve as a proxy for phytoplankton biomass and may be used as an indicator of increased anthropogenic nutrient stress. Satellite remote sensing may present a complement to in situ measures for assessments of water quality through the retrieval of chl-a with in-water algorithms. Validation of chl-a algorithms across US lakes improves algorithm maturity relevant for monitoring applications. This study compares performance of the Case 2 Regional Coast Colour (C2RCC) chl-a retrieval algorithm, a revised version of the Maximum-Peak Height (MPH(P)) algorithm, and three scenarios merging these two approaches. Satellite data were retrieved from the MEdium Resolution Imaging Spectrometer (MERIS) and the Ocean and Land Colour Instrument (OLCI), while field observations were obtained from 181 lakes matched with U.S. Water Quality Portal chl-a data. The best performance based on mean absolute multiplicative error (MAEmult) was demonstrated by the merged algorithm referred to as C15−M10 (MAEmult = 1.8, biasmult = 0.97, n = 836). In the C15−M10 algorithm, the MPH(P) chl-a value was retained if it was > 10 µg L−1; if the MPH(P) value was ≤ 10 µg L−1, the C2RCC value was selected, as long as that value was < 15 µg L−1. Time-series and lake-wide gradients compared against independent assessments from Lake Champlain and long-term ecological research stations in Wisconsin were used as complementary examples supporting water quality reporting requirements. Trophic state assessments for Wisconsin lakes provided examples in support of inland water quality monitoring applications. This study presents and assesses merged adaptations of chl-a algorithms previously reported independently. Additionally, it contributes to the transition of chl-a algorithm maturity by quantifying error statistics for a number of locations and times.

Satellite↗

NASA NTRSDate not supplied

A NASA Perspective on Quantum Computing: Algorithmic Opportunities and Challenges

In the last couple of decades, the world has seen several stunning instances of quantum algorithms that provably outperform the best classical algorithms. For most problems, however, it is currently unknown whether quantum algorithms can provide an advantage, and if so how to design quantum algorithms that realize such advantages. Today, classical heuristics are used to solve many of the most challenging computational problems arising in the practical world, algorithms that have been shown to be effective empirically but have not been mathematically proven to outperform other approaches. With the advent of quantum advantage, the ability of current quantum hardware to do certain computations beyond the ability of even that largest supercomputers, we have an unprecedented opportunity to explore heuristic quantum algorithms. The next few years will be exciting as empirical testing of quantum heuristic algorithms becomes more and more feasible. The talk will begin overview of the NASA QuAIL team’s ongoing quantum computing investigations, and then focus on both near-term and longer term algorithms for optimization, including distributed algorithms.

quantum computing↗

DOE OSTI2017

A hybrid optimization algorithm to explore atomic configurations of TiO 2 nanoparticles

Here in this paper we present a hybrid algorithm comprised of differential evolution, coupled with the Broyden–Fletcher–Goldfarb–Shanno quasi-Newton optimization algorithm, for the purpose of identifying a broad range of (meta)stable Ti n O 2 n nanoparticles, as an example system, described by Buckingham interatomic potential. The potential and its gradient are modified to be piece-wise continuous to enable use of these continuous-domain, unconstrained algorithms, thereby improving compatibility. To measure computational effectiveness a regression on known structures is used. This approach defines effectiveness as the ability of an algorithm to produce a set of structures whose energy distribution follows the regression as the number of Ti n O 2n increases such that the shape of the distribution is consistent with the algorithm’s stated goals. Our calculation demonstrates that the hybrid algorithm finds global minimum configurations more effectively than the differential evolution algorithms, widely employed in the field of materials science. Specifically, the hybrid algorithm is shown to reproduce the global minimum energy structures reported in the literature up to n = 5, and retains good agreement with the regression up to n = 25. For 25 < n < 100, where literature structures are unavailable, the hybrid effectively obtains structures that are in lower energies per TiO 2 unit as the system size increases.

36 MATERIALS SCIENCE↗

DOE OSTI2018

A class of customized proximal point algorithms for linearly constrained convex optimization

In this paper, we propose a class of customized proximal point algorithms for linearly constrained convex optimization problems. The algorithms are implementable, provided that the proximal operator of the objective function is easy to evaluate. We show that, with special setting of the algorithmic scalar, our algorithms contain the customized proximal point algorithm (He et al., Optim Appl 56:559–572, 2013), the linearized augmented Lagrangian method (Yang and Yuan, Math Comput 82:301–329, 2013), the Bregman Operator Splitting algorithm (Zhang et al., SIAM J Imaging Sci 3:253–276, 2010) as special cases. The global convergence and worst-case convergence rate measured by the iteration complexity are established for the proposed algorithms. Numerical results demonstrate that the algorithms work well for a wide range of the scalar.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2025

Resilience–runtime tradeoff relations for quantum algorithms

Abstract A leading approach to algorithm design aims to minimize the number of operations in an algorithm’s compilation. One intuitively expects that reducing the number of operations may decrease the chance of errors. This paradigm is particularly prevalent in quantum computing, where gates are hard to implement and noise rapidly decreases a quantum computer’s potential to outperform classical computers. Here, we find that minimizing the number of operations in a quantum algorithm can be counterproductive, leading to a noise sensitivity that induces errors when running the algorithm in non-ideal conditions. To show this, we develop a framework to characterize the resilience of an algorithm to perturbative noises (including coherent errors, dephasing, and depolarizing noise). Some compilations of an algorithm can be resilient against certain noise sources while being unstable against other noises. We condense these results into a tradeoff relation between an algorithm’s number of operations and its noise resilience. We also show how this framework can be leveraged to identify compilations of an algorithm that are better suited to withstand certain noises.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

DOE OSTI2015

Influence of radiation dose and reconstruction algorithm in MDCT assessment of airway wall thickness: A phantom study

Purpose: Wall thickness (WT) is an airway feature of great interest for the assessment of morphological changes in the lung parenchyma. Multidetector computed tomography (MDCT) has recently been used to evaluate airway WT, but the potential risk of radiation-induced carcinogenesis—particularly in younger patients—might limit a wider use of this imaging method in clinical practice. The recent commercial implementation of the statistical model-based iterative reconstruction (MBIR) algorithm, instead of the conventional filtered back projection (FBP) algorithm, has enabled considerable radiation dose reduction in many other clinical applications of MDCT. The purpose of this work was to study the impact of radiation dose and MBIR in the MDCT assessment of airway WT. Methods: An airway phantom was scanned using a clinical MDCT system (Discovery CT750 HD, GE Healthcare) at 4 kV levels and 5 mAs levels. Both FBP and a commercial implementation of MBIR (Veo{sup TM}, GE Healthcare) were used to reconstruct CT images of the airways. For each kV–mAs combination and each reconstruction algorithm, the contrast-to-noise ratio (CNR) of the airways was measured, and the WT of each airway was measured and compared with the nominal value; the relative bias and the angular standard deviation in the measured WT were calculated. For each airway and reconstruction algorithm, the overall performance of WT quantification across all of the 20 kV–mAs combinations was quantified by the sum of squares (SSQs) of the difference between the measured and nominal WT values. Finally, the particular kV–mAs combination and reconstruction algorithm that minimized radiation dose while still achieving a reference WT quantification accuracy level was chosen as the optimal acquisition and reconstruction settings. Results: The wall thicknesses of seven airways of different sizes were analyzed in the study. Compared with FBP, MBIR improved the CNR of the airways, particularly at low radiation dose levels. For FBP, the relative bias and the angular standard deviation of the measured WT increased steeply with decreasing radiation dose. Except for the smallest airway, MBIR enabled significant reduction in both the relative bias and angular standard deviation of the WT, particularly at low radiation dose levels; the SSQ was reduced by 50%–96% by using MBIR. The optimal reconstruction algorithm was found to be MBIR for the seven airways being assessed, and the combined use of MBIR and optimal kV–mAs selection resulted in a radiation dose reduction of 37%–83% compared with a reference scan protocol with a dose level of 1 mGy. Conclusions: The quantification accuracy of airway WT is strongly influenced by radiation dose and reconstruction algorithm. The MBIR algorithm potentially allows the desired WT quantification accuracy to be achieved with reduced radiation dose, which may enable a wider clinical use of MDCT for the assessment of airway WT, particularly for younger patients who may be more sensitive to exposures with ionizing radiation.

60 APPLIED LIFE SCIENCES↗

DOE OSTI2016

Accelerated fast iterative shrinkage thresholding algorithms for sparsity-regularized cone-beam CT image reconstruction

Purpose: The development of iterative image reconstruction algorithms for cone-beam computed tomography (CBCT) remains an active and important research area. Even with hardware acceleration, the overwhelming majority of the available 3D iterative algorithms that implement nonsmooth regularizers remain computationally burdensome and have not been translated for routine use in time-sensitive applications such as image-guided radiation therapy (IGRT). In this work, two variants of the fast iterative shrinkage thresholding algorithm (FISTA) are proposed and investigated for accelerated iterative image reconstruction in CBCT. Methods: Algorithm acceleration was achieved by replacing the original gradient-descent step in the FISTAs by a subproblem that is solved by use of the ordered subset simultaneous algebraic reconstruction technique (OS-SART). Due to the preconditioning matrix adopted in the OS-SART method, two new weighted proximal problems were introduced and corresponding fast gradient projection-type algorithms were developed for solving them. We also provided efficient numerical implementations of the proposed algorithms that exploit the massive data parallelism of multiple graphics processing units. Results: The improved rates of convergence of the proposed algorithms were quantified in computer-simulation studies and by use of clinical projection data corresponding to an IGRT study. The accelerated FISTAs were shown to possess dramatically improved convergence properties as compared to the standard FISTAs. For example, the number of iterations to achieve a specified reconstruction error could be reduced by an order of magnitude. Volumetric images reconstructed from clinical data were produced in under 4 min. Conclusions: The FISTA achieves a quadratic convergence rate and can therefore potentially reduce the number of iterations required to produce an image of a specified image quality as compared to first-order methods. We have proposed and investigated accelerated FISTAs for use with two nonsmooth penalty functions that will lead to further reductions in image reconstruction times while preserving image quality. Moreover, with the help of a mixed sparsity-regularization, better preservation of soft-tissue structures can be potentially obtained. The algorithms were systematically evaluated by use of computer-simulated and clinical data sets.

60 APPLIED LIFE SCIENCES↗

DOE OSTI2017

Quantum algorithms for Gibbs sampling and hitting-time estimation

In this paper, we present quantum algorithms for solving two problems regarding stochastic processes. The first algorithm prepares the thermal Gibbs state of a quantum system and runs in time almost linear in √Nβ/Ζ and polynomial in log(1/ϵ), where N is the Hilbert space dimension, β is the inverse temperature, Ζ is the partition function, and ϵ is the desired precision of the output state. Our quantum algorithm exponentially improves the dependence on 1/ϵ and quadratically improves the dependence on β of known quantum algorithms for this problem. The second algorithm estimates the hitting time of a Markov chain. For a sparse stochastic matrix Ρ, it runs in time almost linear in 1/(ϵΔ 3/2 ), where ϵ is the absolute precision in the estimation and Δ is a parameter determined by Ρ, and whose inverse is an upper bound of the hitting time. Our quantum algorithm quadratically improves the dependence on 1/ϵ and 1/Δ of the analog classical algorithm for hitting-time estimation. Finally, both algorithms use tools recently developed in the context of Hamiltonian simulation, spectral gap amplification, and solving linear systems of equations.

97 MATHEMATICS AND COMPUTING↗

NASA NTRS2012

Generating Global Leaf Area Index from Landsat: Algorithm Formulation and Demonstration

This paper summarizes the implementation of a physically based algorithm for the retrieval of vegetation green Leaf Area Index (LAI) from Landsat surface reflectance data. The algorithm is based on the canopy spectral invariants theory and provides a computationally efficient way of parameterizing the Bidirectional Reflectance Factor (BRF) as a function of spatial resolution and wavelength. LAI retrievals from the application of this algorithm to aggregated Landsat surface reflectances are consistent with those of MODIS for homogeneous sites represented by different herbaceous and forest cover types. Example results illustrating the physics and performance of the algorithm suggest three key factors that influence the LAI retrieval process: 1) the atmospheric correction procedures to estimate surface reflectances; 2) the proximity of Landsatobserved surface reflectance and corresponding reflectances as characterized by the model simulation; and 3) the quality of the input land cover type in accurately delineating pure vegetated components as opposed to mixed pixels. Accounting for these factors, a pilot implementation of the LAI retrieval algorithm was demonstrated for the state of California utilizing the Global Land Survey (GLS) 2005 Landsat data archive. In a separate exercise, the performance of the LAI algorithm over California was evaluated by using the short-wave infrared band in addition to the red and near-infrared bands. Results show that the algorithm, while ingesting the short-wave infrared band, has the ability to delineate open canopies with understory effects and may provide useful information compared to a more traditional two-band retrieval. Future research will involve implementation of this algorithm at continental scales and a validation exercise will be performed in evaluating the accuracy of the 30-m LAI products at several field sites. ©

Landsat↗

NASA NTRS2016

Soil Moisture Active Passive (SMAP) Project Algorithm Theoretical Basis Document SMAP L1B Radiometer Data Product: L1B_TB

The purpose of the Soil Moisture Active Passive (SMAP) radiometer calibration algorithm is to convert Level 0 (L0) radiometer digital counts data into calibrated estimates of brightness temperatures referenced to the Earth's surface within the main beam. The algorithm theory in most respects is similar to what has been developed and implemented for decades for other satellite radiometers; however, SMAP includes two key features heretofore absent from most satellite borne radiometers: radio frequency interference (RFI) detection and mitigation, and measurement of the third and fourth Stokes parameters using digital correlation. The purpose of this document is to describe the SMAP radiometer and forward model, explain the SMAP calibration algorithm, including approximations, errors, and biases, provide all necessary equations for implementing the calibration algorithm and detail the RFI detection and mitigation process. Section 2 provides a summary of algorithm objectives and driving requirements. Section 3 is a description of the instrument and Section 4 covers the forward models, upon which the algorithm is based. Section 5 gives the retrieval algorithm and theory. Section 6 describes the orbit simulator, which implements the forward model and is the key for deriving antenna pattern correction coefficients and testing the overall algorithm.

microwave radiometers↗

DOE OSTI2017

The WTP Immobilized LAW Formulation Algorithm: Recent Efforts Toward Software Development - 17342

The immobilized low-activity waste (ILAW) product from WTP must meet certain requirements and processing constraints. The strategy for controlling ILAW product composition uses the ILAW formulation algorithm. This algorithm is approved by the DOE Office of River Protection (ORP) for use in calculating melter feed recipes that will produce acceptable ILAW product during Low-Activity Waste (LAW) Facility commissioning. The calculations performed by the algorithm have been demonstrated using a sophisticated spreadsheet, but this spreadsheet is not expected to support continuous operation. Efforts are underway to develop software that will support glass formulation during operation. Recent work toward software development includes an examination of assumptions made in the algorithm about expected LAW Facility operation, and spreadsheet calculations to formulate glass for potential LAW compositions under the direct feed LAW (DFLAW) strategy that ORP has adopted. The documentation of the ILAW algorithm is the planned basis for software development. However, some assumptions made in the current algorithm's mass balance logic do not match the matured design and expected operation of the LAW Facility. A self-assessment effort evaluated the validity of these assumptions by reviewing design documents, in order to identify opportunities to align the algorithm's mass balance logic with the matured design and ensure that the developed software supports continuous LAW Facility operation. Several improvement opportunities were identified and are discussed. The results of ILAW algorithm calculations to formulate glass for eighteen challenging LAW compositions indicate that the current WTP baseline LAW glass models are sufficiently robust to accommodate DFLAW. (authors)

12 MANAGEMENT OF RADIOACTIVE AND NON-RADIOACTIVE W↗

DOE OSTI2016

Algorithmic Improvements for Portable Event-Based Monte Carlo Transport Using the Nvidia Thrust Library

High performance computing environments are progressively moving towards many-core computing architectures. The Los Alamos National Laboratory Trinity machine, available in late 2016, will use both Intel Xeon Haswell processors and Intel Xeon Phi Knights Landing many integrated core (MIC) coprocessors. The Lawrence Livermore National Laboratory Sierra machine, available in 2018, will use an IBM PowerPC architecture along with Nvidia graphics processing units (GPUs). Applications that must work in this supercomputing environment must continue to adapt in order to take advantage of the diverse hardware architectures that are coming. A significant consideration is not only the performance of the application on a given platform but also the portability of the application to other platforms. The algorithmic improvements presented in this paper build upon recently-reported work on event-based Monte Carlo transport in the ALPSMC code that models particle transport in one-dimensional binary stochastic media. That paper discussed the lack of available vectorization in the traditional history-based algorithm used for Monte Carlo transport and presented a data parallel event-based algorithm implemented using the Nvidia Thrust library for portability. The performance of the data parallel event-based algorithm implemented using Thrust was compared to a native CUDA implementation. The conclusions from that work were that the Thrust library abstraction technique caused too significant a loss in performance but that the event-based method was a viable option that should be further investigated. In this paper, we describe algorithmic improvements to the data parallel event-based algorithm previously presented. We made further algorithmic optimizations to the event-based CUDA implementation, most notably: data structure changes, a new conditional particle removal scheme in the event-based process, and the use of multiple GPUs. In addition to improvements to the algorithm, we re-implemented the Thrust version from the now further optimized CUDA version, giving a greater chance for success at a performant abstraction. Finally, we revisited our previous assumptions about the inability of the history-based method to achieve performance on vector style architectures such as the MICs and GPUs, with surprising and promising results. (authors)

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗

DOE OSTI2020

Finite spatial-grid effects in energy-conserving particle-in-cell algorithms

Finite-grid (or aliasing) instabilities are pervasive in particle-in-cell (PIC) plasma simulation algorithms, and force the modeler to resolve the smallest (Debye) length scale in the problem regardless of dynamical relevance. These instabilities originate in the aliasing of interpolation errors between mesh quantities and particles (which live in the space–time continuum). Recently, strictly energy-conserving PIC (EC-PIC) algorithms have been developed that promise enhanced robustness against aliasing instabilities. In this study, we confirm by analysis that EC-PIC is stable against aliasing instabilities for stationary plasmas. For drifting plasmas, we demonstrate by analysis and numerical experiments that, while EC-PIC algorithms are not free from these instabilities in principle, they feature a benign stability threshold for finite-temperature plasmas that make them usable in practice for a large class of problems (featuring ambipolarity and realistic ion-electron mass ratios) without the need to consider the size of the Debye length. We also demonstrate that this threshold is absent for the popular momentum-conserving PIC algorithms, which are therefore unstable for both drifting and stationary plasmas beyond a threshold in cell size compared to Debye length. Finite-grid (or aliasing) instabilities are pervasive in particle-in-cell (PIC) plasma simulation algorithms, and force the modeler to resolve the smallest (Debye) length scale in the problem regardless of dynamical relevance. These instabilities originate in the aliasing of interpolation errors between mesh quantities and particles (which live in the space–time continuum). Recently, strictly energy-conserving PIC (EC-PIC) algorithms have been developed that promise enhanced robustness against aliasing instabilities. In this study, we confirm by analysis that EC-PIC is stable against aliasing instabilities for stationary plasmas. For drifting plasmas, we demonstrate by analysis and numerical experiments that, while EC-PIC algorithms are not free from these instabilities in principle, they feature a benign stability threshold for finite-temperature plasmas that make them usable in practice for a large class of problems (featuring ambipolarity and realistic ion-electron mass ratios) without the need to consider the size of the Debye length. Finally, we also demonstrate that this threshold is absent for the popular momentum-conserving PIC algorithms, which are therefore unstable for both drifting and stationary plasmas beyond a threshold in cell size compared to Debye length.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2017

Pencil Beam Algorithms Are Unsuitable for Proton Dose Calculations in Lung

Purpose: To compare analytic and Monte Carlo–based algorithms for proton dose calculations in the lung, benchmarked against anthropomorphic lung phantom measurements. Methods and Materials: A heterogeneous anthropomorphic moving lung phantom has been irradiated at numerous proton therapy centers. At 5 centers the treatment plan could be calculated with both an analytic and Monte Carlo algorithm. The doses calculated in the treatment plans were compared with the doses delivered to the phantoms, which were measured using thermoluminescent dosimeters and film. Point doses were compared, as were planar doses using a gamma analysis. Results: The analytic algorithms overestimated the dose to the center of the target by an average of 7.2%, whereas the Monte Carlo algorithms were within 1.6% of the physical measurements on average. In some regions of the target volume, the analytic algorithm calculations differed from the measurement by up to 31% in the internal gross target volume (iGTV) (46% in the planning target volume), over-predicting the dose. All comparisons showed a region of at least 15% dose discrepancy within the iGTV between the analytic calculation and the measured dose. The Monte Carlo algorithm recalculations showed dramatically improved agreement with the measured doses, showing mean agreement within 4% for all cases and a maximum difference of 12% within the iGTV. Conclusions: Analytic algorithms often do a poor job predicting proton dose in lung tumors, over-predicting the dose to the target by up to 46%, and should not be used unless extensive validation counters the consistent results of the present study. Monte Carlo algorithms showed dramatically improved agreement with physical measurements and should be implemented to better reflect actual delivered dose distributions.

62 RADIOLOGY AND NUCLEAR MEDICINE↗

DOE OSTI2019

A communication-avoiding 3D algorithm for sparse LU factorization on heterogeneous systems

We propose a new algorithm to improve the strong scalability of right-looking sparse LU factorization on distributed memory systems. Our 3D algorithm for sparse LU uses a three-dimensional MPI process grid, exploits elimination tree parallelism, and trades off increased memory for reduced per-process communication. We also analyze the asymptotic improvements for planar graphs (e.g., those arising from 2D grid or mesh discretizations) and certain non-planar graphs (specifically for 3D grids and meshes). For a planar graph with $n$ vertices, our algorithm reduces communication volume asymptotically in $n$ by a factor of $\mathscr{O}$ $\Big(\sqrt{log \ n}\Big)$ and latency by a factor of $\mathscr{O}$ $(log \ n)$. For nonplanar cases, our algorithm can reduce the per-process communication volume by 3× and latency by $\mathscr{O}$ $\Big(n^\frac13\Big)$ times. In all cases, the memory needed to achieve these gains is a constant factor. We implemented our algorithm by extending the 2D data structure used in SuperLU_DIST. Our new 3D code achieves empirical speedups up to 27× for planar graphs and up to 3.3× for non-planar graphs over the baseline 2D SuperLU_DIST when run on 24,000 cores of a Cray XC30. We extend the 3D algorithm for heterogeneous architectures by adding the Highly Asynchronous Lazy Offload (Halo) algorithm for co-processor offload. On 4096 nodes of a Cray XK7 with 32,768 CPU cores and 4096 Nvidia K20x GPUs, the 3D algorithm achieves empirical speedups up to 24× for planar graphs and 3.5× for non-planar graphs over the baseline 2D SuperLU_DIST with co-processor acceleration.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2021

Intercomparison of Thermal Regime Algorithms in 1-D Lake Models

Lakes are an important component of the global weather and climate system, but the modeling of their thermal regimes has shown large uncertainties due to the highly diverse lake properties and model configurations. Here we evaluate the algorithms of four key lake thermal processes including turbulent heat fluxes, wind-driven mixing, light extinction, and snow density, using a highly diverse lake dataset provided by the Inter-sectoral Impact Model Intercomparison Project (ISIMIP) 2a lake sector. Algorithm codes are configured and run separately within the same parent model to rule out any interference from factors apart from the algorithms examined. Evaluations are based on both simulation accuracy and recalibration complexity for application to global lakes. For turbulent heat fluxes, the non-Monin-Obukhov similarity (MOS) based, more simplified algorithms perform better in predicting lake epilimnion temperatures and achieve high convergence in the values of the calibrated parameters. For wind-driven mixing, a two-algorithm strategy considering lake shape and season is suggested with the regular mixing algorithm used for spring and earlier summer and the mixing-enhanced algorithm for summer steady stratification and fall overturn periods. There are no evident differences in the simulated thermocline depths using different light extinction algorithms or the observation. Finally, for lake ice phenology, a constant snow density at around 110 kg m-3 is found to be sufficient for most northern lakes while the Arctic lakes require a higher value. Our study provides highly practical guides for improving 1-D lake models and feasible parameterization strategies to better simulate global lake thermal regimes.

58 GEOSCIENCES↗