Search NASA⌕ Search

SEARCH · Search NASA

Results for “Numerical algorithm”

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

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

At least 1,729 records · Page 96

High-Performance Sparse Matrix-Matrix Products on Intel KNL and Multicore Architectures

Sparse matrix-matrix multiplication (SpGEMM) is a computational primitive that is vastly used in areas ranging from traditional numerical applications to recent big data analysis and machine learning. While many SpGEMM algorithms have been proposed, hardware specific optimizations for multi- and many-core processors are lacking and a detailed analysis of their performance under various use cases and matrices is not available. We firstly identify and mitigate multiple bottlenecks with memory management and thread scheduling on Intel Xeon Phi (Knights Landing or KNL). Specifically targeting multi- and many-core processors, we develop a hash-table-based algorithm and optimize a heap-based shared-memory SpGEMM algorithm. We investigate their performance together with other publicly available codes. Different from the literature, our evaluation also includes use cases that are representative of real graph algorithms, such as multi-source breadth-first search or triangle counting. Our hash-table and heap-based algorithms are showing significant speedups from libraries in the majority of the cases while different algorithms dominate the other scenarios with different matrix size, sparsity, compression factor and operation type. We wrap up in-depth evaluation results and make a recipe to give the best SpGEMM algorithm for target scenario. In conclusion, a critical finding is that hash-table-based SpGEMM gets a significant performance boost if the nonzeros are not required to be sorted within each row of the output matrix.

97 MATHEMATICS AND COMPUTING↗

TensorID v1.0

This Python software package includes new and efficient algorithms for satellite and core interpolative decomposition of tensor data. In general, these algorithms target high-dimensional data reduction and compression. The software is purely numerical and can be applied by others to many important sources of tensor data generated by computation or experiment.

Zhang, Yifan [Lawrence Berkeley National Laborator↗

First observations of tracking clouds using scanning ARM cloud radars

Tracking clouds using scanning cloud radars can help to document the temporal evolution of cloud properties well before large drop formation (‘‘first echo’’). These measurements complement cloud and precipitation tracking using geostationary satellites and weather radars. Here, two-dimensional (2-D) Along-Wind Range Height Indicator (AW-RHI) observations of a population of shallow cumuli (with and without precipitation) from the 35-GHz scanning ARM cloud radar (SACR) at the DOE Atmospheric Radiation Measurements (ARM) program Southern Great Plains (SGP) site are presented. Observations from the ARM SGP network of scanning precipitation radars are used to provide the larger scale context of the cloud field and to highlight the advantages of the SACR to detect the numerous, small, non-precipitating cloud elements. A new Cloud Identification and Tracking Algorithm (CITA) is developed to track cloud elements. In CITA, a cloud element is identified as a region having a contiguous set of pixels exceeding a preset reflectivity and size threshold. The high temporal resolution of the SACR 2-D observations (30 sec) allows for an area superposition criteria algorithm to match cloud elements at consecutive times. Following CITA, the temporal evolution of cloud element properties (number, size, and maximum reflectivity) is presented. The vast majority of the designated elements during this cumulus event were short-lived non-precipitating clouds having an apparent life cycle shorter than 15 minutes. The advantages and disadvantages of cloud tracking using an SACR are discussed.

54 ENVIRONMENTAL SCIENCES↗

Machine Learning–Adjusted WRF Forecasts to Support Wind Energy Needs in Black Start Operations

Abstract The push for increased capacity of renewable sources of electricity has led to the growth of wind-power generation, with a need for accurate forecasts of winds at hub height. Forecasts for these levels were uncommon until recently, and that, combined with the nocturnal collapse of the well-mixed boundary layer and daytime growth of the boundary layer through the levels important for energy generation, has contributed to errors in numerical modeling of wind generation resources. The present study explores several machine learning algorithms to both forecast and correct standard WRF Model forecasts of winds and temperature at hub height within wind turbine plants over several different time periods that are critical for the anticipation of potential blackouts and aiding in black start operations on the power grid. It was found that mean square error for day-2 wind forecasts from the WRF Model can be improved by over 90% with the use of a multioutput neural network, and that 60-min forecasts of WRF error, which can then be used to adjust forecasts, can be made with an LSTM with great accuracy. Nowcasting of temperature and wind speed over a 10-min period using an LSTM produced very low error and especially skillful forecasts of maximum and minimum values over the turbine plant area.

17 WIND ENERGY↗

Development of Spectral and Atomic Models for Diagnosing Energetic Particle Characteristics in Fast Ignition Experiments

This Final Report summarizes work performed under DOE STTR Phase II Grant No. DE-FG02-05ER86258 during the project period from August 2006 to August 2009. The project, “Development of Spectral and Atomic Models for Diagnosing Energetic Particle Characteristics in Fast Ignition Experiments,” was led by Prism Computational Sciences (Madison, WI), and involved collaboration with subcontractors University of Nevada-Reno and Voss Scientific (Albuquerque, NM). In this project, we have: Developed and implemented a multi-dimensional, multi-frequency radiation transport model in the LSP hybrid fluid-PIC (particle-in-cell) code [1,2]. Updated the LSP code to support the use of accurate equation-of-state (EOS) tables generated by Prism’s PROPACEOS [3] code to compute more accurate temperatures in high energy density physics (HEDP) plasmas. Updated LSP to support the use of Prism’s multi-frequency opacity tables. Generated equation of state and opacity data for LSP simulations for several materials being used in plasma jet experimental studies. Developed and implemented parallel processing techniques for the radiation physics algorithms in LSP. Benchmarked the new radiation transport and radiation physics algorithms in LSP and compared simulation results with analytic solutions and results from numerical radiation-hydrodynamics calculations. Performed simulations using Prism radiation physics codes to address issues related to radiative cooling and ionization dynamics in plasma jet experiments. Performed simulations to study the effects of radiation transport and radiation losses due to electrode contaminants in plasma jet experiments. Updated the LSP code to generate output using NetCDF to provide a better, more flexible interface to SPECT3D [4] in order to post-process LSP output. Updated the SPECT3D code to better support the post-processing of large-scale 2-D and 3-D datasets generated by simulation codes such as LSP. Updated atomic physics modeling to provide for more comprehensive and accurate atomic databases that feed into the radiation physics modeling (spectral simulations and opacity tables). Developed polarization spectroscopy modeling techniques suitable for diagnosing energetic particle characteristics in HEDP experiments. A description of these items is provided in this report. The above efforts lay the groundwork for utilizing the LSP and SPECT3D codes in providing simulation support for DOE-sponsored HEDP experiments, such as plasma jet and fast ignition physics experiments. We believe that taken together, the LSP and SPECT3D codes have unique capabilities for advancing our understanding of the physics of these HEDP plasmas. Based on conversations early in this project with our DOE program manager, Dr. Francis Thio, our efforts emphasized developing radiation physics and atomic modeling capabilities that can be utilized in the LSP PIC code, and performing radiation physics studies for plasma jets. A relatively minor component focused on the development of methods to diagnose energetic particle characteristics in short-pulse laser experiments related to fast ignition physics. The period of performance for the grant was extended by one year to August 2009 with a one-year no-cost extension, at the request of subcontractor University of Nevada-Reno.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

Multilevel summation methods for efficient evaluation of long-range pairwise interactions in atomistic and coarse-grained molecular simulation.

The availability of efficient algorithms for long-range pairwise interactions is central to the success of numerous applications, ranging in scale from atomic-level modeling of materials to astrophysics. This report focuses on the implementation and analysis of the multilevel summation method for approximating long-range pairwise interactions. The computational cost of the multilevel summation method is proportional to the number of particles, N, which is an improvement over FFTbased methods who s cost is asymptotically proportional to N logN. In addition to approximating electrostatic forces, the multilevel summation method can be use to efficiently approximate convolutions with long-range kernels. As an application, we apply the multilevel summation method to a discretized integral equation formulation of the regularized generalized Poisson equation. Numerical results are presented using an implementation of the multilevel summation method in the LAMMPS software package. Preliminary results show that the computational cost of the method scales as expected, but there is still a need for further optimization.

Bond, Stephen D.↗

Polarimetric ISAR: Simulation and image reconstruction

In polarimetric ISAR the illumination platform, typically airborne, carries a pair of antennas that are directed toward a fixed point on the surface as the platform moves. During platform motion, the antennas maintain their gaze on the point, creating an effective aperture for imaging any targets near that point. The interaction between the transmitted fields and targets (e.g. ships) is complicated since the targets are typically many wavelengths in size. Calculation of the field scattered from the target typically requires solving Maxwell’s equations on a large three-dimensional numerical grid. This is prohibitive to use in any real-world imaging algorithm, so the scattering process is typically simplified by assuming the target consists of a cloud of independent, non-interacting, scattering points (centers). Imaging algorithms based on this scattering model perform well in many applications. Since polarimetric radar is not very common, the scattering model is often derived for a scalar field (single polarization) where the individual scatterers are assumed to be small spheres. However, when polarization is important, we must generalize the model to explicitly account for the vector nature of the electromagnetic fields and its interaction with objects. In this note, we present a scattering model that explicitly includes the vector nature of the fields but retains the assumption that the individual scatterers are small. The response of the scatterers is described by electric and magnetic dipole moments induced by the incident fields. We show that the received voltages in the antennas are linearly related to the transmitting currents through a scattering impedance matrix that depends on the overall geometry of the problem and the nature of the scatterers.

42 ENGINEERING↗

Planetary Boundary Layer Height (PBL) Value Added Product (VAP): Radiosonde Retrievals

The planetary boundary layer (PBL) can be defined as “that part of the troposphere that is directly influenced by the presence of the earth’s surface…” (Stull 1988). The PBL height (or mixing layer depth) can vary significantly with time due to a number of factors including large-scale dynamics, cloudiness, convective mixing, and the diurnal cycle of solar radiation. The structure and depth of the PBL is important to a wide range of atmospheric processes, including cloud formation; aerosol mixing, transport, and transformation; and chemical mixing, transport, and transformation. Errors in the determination of the PBL height in models can significantly impact the formation and maintenance of low-level clouds (Zeng et al. 2004). Routine estimates of PBL height are useful for a wide range of research projects and therefore, it was proposed that a PBL height value added product (VAP) be developed for the Atmospheric Radiation Measurement (ARM) program. Numerous instruments (e.g., radiosonde, ceilometer, backscatter lidar, Doppler wind lidar, and sodar) and algorithms have been used for PBL height detection, each with their own strengths and weaknesses (Seibert et al. 2000). In order to speed development of a PBL height product, it was decided to take a phased approach to data set development and begin with relatively simple and mature algorithms that can be applied to instruments available at all ARM sites before moving on to more sophisticated algorithms and/or instrumentation. In the first phase of the VAP development (described in this technical report), we describe the implementation of a PBL Height VAP for radiosonde measurements, which we refer to as the PBLHeightSonde VAP. Radiosonde measurements are one of the most common methods for determining PBL or mixing layer height. Often, experienced meteorologists manually estimate PBL height by examining profiles of potential temperature and moisture; however, several operational PBL height estimation methods have been developed (Seibert et al. 2000). As there is no “truth” to evaluate PBL height estimates and since the definition of PBL height is somewhat subjective, we implemented several different methods of estimating PBL or mixed layer height from radiosonde profiles. The differences between the estimates from the various methods can be considered a partial estimate of the uncertainty in the PBL height values.

54 ENVIRONMENTAL SCIENCES↗

Online Energy-optimal Routing for Electric Vehicles with Combinatorial Multi-arm Semi-Bandit

We have seen a rapid growth in the adoption of electric vehicle in today’s commercial mobility service market, from carrying passengers to the delivery of goods. One cardinal issue concerning the operation of EVs is the optimal routing of EV fleets with limited battery capacity. In this study, we investigate the energy-optimal online routing problem for the fleet of EVs, which focuses on identifying real-time minimum electricity consumption paths (MECP) for multiple OD pairs with limited information. We develop a multi-OD combinatorial multi-arm semi-bandit model (MCMAB) that uses the fleet of EVs as sensors in the transportation network and promotes the utilization of common information shared by different OD pairs. We further enrich the model with the path elimination policy to obtain MECP of high confidence while significantly reducing the number of learning iterations and the number of explorations needed. We demonstrate the effectiveness of the MCMAB and the efficiency of the path elimination policy with comprehensive numerical experiments in Manhattan, NYC. The results show that the proposed online routing algorithms can achieve near-optimal MECPs efficiently, and the quality of the solutions is significantly better than using the shortest travel time paths as approximate MECPs.

Chen, Xiaowei↗

Apprentice for Event Generator Tuning

Apprentice is a tool developed for event generator tuning. It contains a range of conceptual improvements and extensions over the tuning tool Professor. Its core functionality remains the construction of a multivariate analytic surrogate model to computationally expensive Monte-Carlo event generator predictions. The surrogate model is used for numerical optimization in chi-square minimization and likelihood evaluation. Apprentice also introduces algorithms to automate the selection of observable weights to minimize the effect of mis-modeling in the event generators. We illustrate our improvements for the task of MC-generator tuning and limit setting.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

Development of a Convolutional Neural Network Classifier for Data Starved Spectra - 20199

The Institute for Clean Energy Technology (ICET) at Mississippi State University is exploring the utility of machine learning in augmenting its mobile radiation surveying platforms, which are currently being developed as means to survey depleted uranium contaminated areas in support of remediation and decommissioning efforts. Mobile survey platforms provide a means to efficiently scan large areas of interest while reducing human exposure to radiation and other hazards. The survey platforms can also be used for scanning for any gamma emitting isotope in addition to depleted uranium. The spectral data that the platforms collect may be data starved with relatively low counts and poorly defined spectral features depending on the speed of the platforms and scintillation detector selection. Such data-starved spectra are difficult to use for isotope identification, requiring advanced knowledge of the possible radionuclides that could be present and environmental factors that could attenuate signals or introduce background noise. These factors in combination with the volume of survey data increases the time it takes to perform analysis of survey data when the source type is unknown. There are a number of algorithms in the field of machine learning that can be used to classify data that would be challenging and time-consuming for a human to identify. Supervised machine learning algorithms train models based on extensive amounts of human-labeled training data. Once sufficiently trained, these models can be used to quickly make high-fidelity predictions on new data. Convolutional neural networks are machine learning algorithms that excel in learning representations of 'shapes'. They do this by taking numerical input data and convolving them with spatial feature detectors referred to as filters. These filters are incrementally adjusted to reduce the prediction error on the data during the backpropagation step of training. Discussed in this paper is the development of a convolutional neural network classifier (CNNC) that can utilize spectral survey data for source discrimination and isotope identification. Bench-top laboratory experiments data using LaBr{sub 3}(Ce) scintillation detectors were used to train and evaluate the performance of the developed CNNC. The CNNC is capable of discriminating a variety of gamma emitting source types, differentiating different forms of uranium (depleted vs. natural), and estimating the amount of uranium for a known geometry. The discussed CNNC may be useful in scenarios where survey systems are deployed in situations where hazardous radioactive material maybe present, but the type is unknown. When used in remediation applications the CNNC can be used to screen-out false positives, helping reduce remediation costs. (authors)

07 ISOTOPE AND RADIATION SOURCES↗

Code Verification of a Warm Electron Diode Using the EMPIRE Plasma Simulation Code.

This report documents recent code verification exercises for a warm electron diode problem using the EMPIRE plasma code. This computationally expensive test was performed three times, including two different code versions and two different time integration algorithms, and the resulting code responses were analyzed for convergence to the analytical solution and orders-of-convergence using the StREEQ numerical error estimation tool. Significant deviations from the exact solution and expected orders-of-convergence, as well as changes in code behavior over time and due to choice of time integration algorithm were observed, illustrating the need to fix fundamental code issues as well as additional code verification testing before the code can be relied upon to accurately solve critical problems within its application space.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

Sparsity of the electron repulsion integral tensor using different localized virtual orbital representations in local second-order Møller–Plesset theory

Utilizing localized orbitals, local correlation theory can reduce the unphysically high system-size scaling of post-Hartree–Fock (post-HF) methods to linear scaling in insulating molecules. The sparsity of the four-index electron repulsion integral (ERI) tensor is central to achieving this reduction. For second-order Møller–Plesset theory (MP2), one of the simplest post-HF methods, only the (ia|jb) ERIs are needed, coupling occupied orbitals i, j and virtuals a, b. In this paper, we compare the numerical sparsity (called the “ragged list”) and two other approaches revealing the low-rank sparsity of the ERI. The ragged list requires only one set of (localized) virtual orbitals, and we find that the orthogonal valence virtual-hard virtual set of virtuals originally proposed by Subotnik et al. gives the sparsest ERI tensor. To further compress the ERI tensor, the pair natural orbital (PNO) type representation uses different sets of virtual orbitals for different occupied orbital pairs, while the occupied-specific virtual (OSV) approach uses different virtuals for each occupied orbital. Here, our results indicate that while the low-rank PNO representation achieves significant rank reduction, it also requires more memory than the ragged list. The OSV approach requires similar memory to that of the ragged list, but it involves greater algorithmic complexity. An approximation (called the “fixed sparsity pattern”) for solving the local MP2 equations using the numerically sparse ERI tensor is proposed and tested to be sufficiently accurate and to have highly controllable error. A low-scaling local MP2 algorithm based on the ragged list and the fixed sparsity pattern is therefore promising.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

A model and variance reduction method for computing statistical outputs of stochastic elliptic partial differential equations

We present a model and variance reduction method for the fast and reliable computation of statistical outputs of stochastic elliptic partial differential equations. Our method consists of three main ingredients: (1) the hybridizable discontinuous Galerkin (HDG) discretization of elliptic partial differential equations (PDEs), which allows us to obtain high-order accurate solutions of the governing PDE; (2) the reduced basis method for a new HDG discretization of the underlying PDE to enable real-time solution of the parameterized PDE in the presence of stochastic parameters; and (3) a multilevel variance reduction method that exploits the statistical correlation among the different reduced basis approximations and the high-fidelity HDG discretization to accelerate the convergence of the Monte Carlo simulations. The multilevel variance reduction method provides efficient computation of the statistical outputs by shifting most of the computational burden from the high-fidelity HDG approximation to the reduced basis approximations. Furthermore, we develop a posteriori error estimates for our approximations of the statistical outputs. Based on these error estimates, we propose an algorithm for optimally choosing both the dimensions of the reduced basis approximations and the sizes of Monte Carlo samples to achieve a given error tolerance. We provide numerical examples to demonstrate the performance of the proposed method.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

L{sub 1/2} regularization based numerical method for effective reconstruction of bioluminescence tomography

Even though bioluminescence tomography (BLT) exhibits significant potential and wide applications in macroscopic imaging of small animals in vivo, the inverse reconstruction is still a tough problem that has plagued researchers in a related area. The ill-posedness of inverse reconstruction arises from insufficient measurements and modeling errors, so that the inverse reconstruction cannot be solved directly. In this study, an l{sub 1/2} regularization based numerical method was developed for effective reconstruction of BLT. In the method, the inverse reconstruction of BLT was constrained into an l{sub 1/2} regularization problem, and then the weighted interior-point algorithm (WIPA) was applied to solve the problem through transforming it into obtaining the solution of a series of l{sub 1} regularizers. The feasibility and effectiveness of the proposed method were demonstrated with numerical simulations on a digital mouse. Stability verification experiments further illustrated the robustness of the proposed method for different levels of Gaussian noise.

60 APPLIED LIFE SCIENCES↗

Optimizing power system restoration with damaged communications

Utility procedures for power system blackstart and restoration typically assume that energization decisions can be reliably communicated across the grid. In reality, the communications and control network would likely also be affected in power outages, such as those caused by extreme weather events or cyber-attacks. This paper studies the effect of damage to the power system communications and control infrastructure on restoration operations following a blackout. We model the communications infrastructure as a graph, overlaying the power grid, and imposing the requirement that every energized element in the power grid be observable from a control center. We expand on a specialized branch-and-bound algorithm from the literature to optimize the restoration process and devise an initialization heuristic and a rounding heuristic to improve solution speed. We perform numerical experiments on synthetic systems for Illinois and Texas with outages based on a solar flare or hurricane. We compare the results of our specialized branch-and-bound algorithm to the results from (i) the initialization heuristic alone, (ii) a variation of this heuristic that we use as a baseline, and (iii) the restoration optimization for the power system without communications constraints. Here, we find that damage to the communications infrastructure significantly increases the time required to re-energize the grid. Moreover, by simultaneously optimizing communications repairs and grid energization decisions, we are able to re-energize the grid significantly faster than if communications repairs and energization decisions were made independently or with partial coordination, motivating improvements to current industry practice.

97 MATHEMATICS AND COMPUTING↗

Tensor Decompositions for Count Data that Leverage Stochastic and Deterministic Optimization

There is growing interest to extend low-rank matrix decompositions to multi-way arrays, or tensors. One fundamental low-rank tensor decomposition is the canonical polyadic decomposition (CPD). The challenge of fitting a low-rank, nonnegative CPD model to Poisson-distributed count data is of particular interest. Several popular algorithms use local search methods to approximate the global maximum likelihood estimator from local minima. Simultaneously, a recent trend in theoretical computer science and numerical linear algebra leverages randomization to solve very large, hard problems. The typical approach is to use randomization for a fast approximation and determinism for refinement to yield effective algorithms with theoretical guarantees. Two popular algorithms for Poisson CPD reflect that emergent dichotomy: CP Alternating Poisson Regression is a deterministic algorithm and Generalized Canonical Polyadic decomposition makes use of stochastic algorithms in several variants. This work extends recent work to develop two new methods that leverage randomized and deterministic algorithms for improved accuracy and performance.

97 MATHEMATICS AND COMPUTING↗

Where did the tumor start? An inverse solver with sparse localization for tumor growth models

In this work, we present a numerical scheme for solving an inverse problem for parameter estimation in tumor growth models for glioblastomas, a form of aggressive primary brain tumor. The growth model is a reaction–diffusion partial differential equation (PDE) for the tumor concentration. We use a PDE-constrained optimization formulation for the inverse problem. The unknown parameters are the reaction coefficient (proliferation), the diffusion coefficient (infiltration), and the initial condition field for the tumor PDE. Segmentation of magnetic resonance imaging (MRI) scans drive the inverse problem where segmented tumor regions serve as partial observations of the tumor concentration. Like most cases in clinical practice, we use data from a single time snapshot. Moreover, the precise time relative to the initiation of the tumor is unknown, which poses an additional difficulty for inversion. We perform a frozen-coefficient spectral analysis and show that the inverse problem is severely ill-posed. We introduce a biophysically motivated regularization on the structure and magnitude of the tumor initial condition. In particular, we assume that the tumor starts at a few locations (enforced with a sparsity constraint on the initial condition of the tumor) and that the initial condition magnitude in the maximum norm is equal to one. We solve the resulting optimization problem using an inexact quasi-Newton method combined with a compressive sampling algorithm for the sparsity constraint. Our implementation uses PETSc and AccFFT libraries. We conduct numerical experiments on synthetic and clinical images to highlight the improved performance of our solver over a previously existing solver that uses standard two-norm regularization for the calibration parameters. The existing solver is unable to localize the initial condition. Our new solver can localize the initial condition and recover infiltration and proliferation. In clinical datasets (for which the ground truth is unknown), our solver results in qualitatively different solutions compared to the two-norm regularized solver.

97 MATHEMATICS AND COMPUTING↗