Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “approximation 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 1,405 records · Page 78

Speeding Up Hartree–Fock in JuliaChem with Density Fitting

In this work, the density fitting (DF) approximation is added to the restricted Hartree–Fock (RHF) implementation in the JuliaChem computational chemistry code. Utilizing a DF algorithm that uses symmetry and integral screening, a significant reduction in time to compute the Fock matrix is achieved. The symmetry and screening DF-RHF techniques were adapted to be performed on graphics processing units (GPUs), which are well suited to perform the matrix multiplications that comprise the bulk of the Fock build time in DF-RHF. The JuliaChem DF-RHF GPU algorithm employs a novel approach that automatically switches between two DF-RHF algorithms depending on the number of basis functions in the calculation. The JuliaChem GPU DF-RHF implementation demonstrates up to 2× speedup for Fock build times compared to the existing best-in-class GPU DF-RHF implementation by operating directly on screened intermediate matrices. Due to the high portability of the Julia language code, the JuliaChem CPU and GPU DF-RHF implementations could be benchmarked on a variety of CPU and GPU architectures from multiple hardware vendors.

Hayes, John J. [Ames Laboratory, and Iowa State Un↗

Fermi GBM Early Trigger Characteristics

Since the launch of the Fermi observatory on June 11 2008, the Gamma-ray Burst Monitor (GBM) has seen approximately 250 triggers of which about 150 were cosmic gamma-ray bursts (GRBs). GBM operates dozens of trigger algorithms covering various energy bands and timescales and is therefore sensitive to a wide variety of phenomena, both astrophysical and not.

79 ASTRONOMY AND ASTROPHYSICS↗

Correlated pair ansatz with a binary tree structure

We develop an efficient algorithm to implement the recently introduced binary tree state (BTS) ansatz on a classical computer. BTS allows a simple approximation to permanents arising from the computationally intractable antisymmetric product of interacting geminals and respects size-consistency. We show how to compute BTS overlap and reduced density matrices efficiently. We also explore two routes for developing correlated BTS approaches: Jastrow coupled cluster on BTS and linear combinations of BT states. Here, the resulting methods show great promise in benchmark applications to the reduced Bardeen–Cooper–Schrieffer Hamiltonian and the one-dimensional XXZ Heisenberg Hamiltonian.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Differentiable Earth mover’s distance for data compression at the high-luminosity LHC

Abstract The Earth mover’s distance (EMD) is a useful metric for image recognition and classification, but its usual implementations are not differentiable or too slow to be used as a loss function for training other algorithms via gradient descent. In this paper, we train a convolutional neural network (CNN) to learn a differentiable, fast approximation of the EMD and demonstrate that it can be used as a substitute for computing-intensive EMD implementations. We apply this differentiable approximation in the training of an autoencoder-inspired neural network (encoder NN) for data compression at the high-luminosity LHC at CERN The goal of this encoder NN is to compress the data while preserving the information related to the distribution of energy deposits in particle detectors. We demonstrate that the performance of our encoder NN trained using the differentiable EMD CNN surpasses that of training with loss functions based on mean squared error.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

Eigenvector Continuation with Subspace Learning

A common challenge faced in quantum physics is finding the extremal eigenvalues and eigenvectors of a Hamiltonian matrix in a vector space so large that linear algebra operations on general vectors are not possible. There are numerous efficient methods developed for this task, but they generally fail when some control parameter in the Hamiltonian matrix exceeds some threshold value. In this Letter we present a new technique called eigenvector continuation that can extend the reach of these methods. The key insight is that while an eigenvector resides in a linear space with enormous dimensions, the eigenvector trajectory generated by smooth changes of the Hamiltonian matrix is well approximated by a very low-dimensional manifold. We prove this statement using analytic function theory and propose an algorithm to solve for the extremal eigenvectors. We benchmark the method using several examples from quantum many-body theory.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

NISQ+: Boosting quantum computing power by approximating quantum error correction

Quantum computers are growing in size, and design decisions are being made now that attempt to squeeze more computation out of these machines. In this spirit, we design a method to boost the computational power of near-term quantum computers by adapting protocols used in quantum error correction to implement "Approximate Quantum Error Correction (AQEC)." By approximating fully-fledged error correction mechanisms, we can increase the compute volume (qubits × gates, or "Simple Quantum Volume (SQV)") of near-term machines. The crux of our design is a fast hardware decoder that can approximately decode detected error syndromes rapidly. Specifically, we demonstrate a proof-of-concept that approximate error decoding can be accomplished online in near-term quantum systems by designing and implementing a novel algorithm in Single-Flux Quantum (SFQ) superconducting logic technology. This avoids a critical decoding backlog, hidden in all offline decoding schemes, that leads to idle time exponential in the number of T gates in a program. Our design utilizes one SFQ processing module per physical qubit. Employing state-of-the-art SFQ synthesis tools, we show that the circuit area, power, and latency are within the constraints of contemporary quantum system designs. Under pure dephasing error models, the proposed accelerator and AQEC solution is able to expand SQV by factors between 3,402 and 11,163 on expected near-term machines. The decoder achieves a 5% accuracy-threshold and pseudo-thresholds of ~ 5%,4.75%,4.5%, and 3.5% physical error-rates for code distances 3,5,7, and 9. Decoding solutions are achieved in a maximum of ~20 nanoseconds on the largest code distances studied. By avoiding the exponential idle time in offline decoders, we achieve a 10x reduction in required code distances to achieve the same logical performance as alternative designs.

97 MATHEMATICS AND COMPUTING↗

Random Walks With Tweedie: A Unified View of Score-Based Diffusion Models [In the Spotlight]

We present a concise derivation for several influential score-based diffusion models that relies on only a few textbook results. Diffusion models have recently emerged as powerful tools for generating realistic, synthetic signals—particularly natural images—and often play a role in state-of-the-art algorithms for inverse problems in image processing. While these algorithms are often surprisingly simple, the theory behind them is not, and multiple complex theoretical justifications exist in the literature. Here, in this study, we provide a simple and largely self-contained theoretical justification for score-based diffusion models that is targeted towards the signal processing community. This approach leads to generic algorithmic templates for training and generating samples with diffusion models. We show that several influential diffusion models correspond to particular choices within these templates and demonstrate that alternative, more straightforward algorithmic choices can provide comparable results. This approach has the added benefit of enabling conditional sampling without any likelihood approximation.

97 MATHEMATICS AND COMPUTING↗

The Bloch equation for spin dynamics in electron storage rings: Computational and theoretical aspects

In this paper, we describe our work on spin polarization in high-energy electron storage rings which we base on the Full Bloch equation (FBE) for the polarization density and which aims towards the [Formula: see text] option of the proposed Future Circular Collider (FCC-ee) and the proposed Circular Electron Positron Collider (CEPC). The FBE takes into account non spin-flip and spin-flip effects due to synchrotron radiation including the spin-diffusion effects and the Sokolov–Ternov effect with its Baier–Katkov generalization as well as the kinetic-polarization effect. This mathematical model is an alternative to the standard mathematical model based on the Derbenev–Kondratenko formulas. For our numerical and analytical studies of the FBE, we develop an approximation to the latter to obtain an effective FBE. This is accomplished by finding a third mathematical model based on a system of stochastic differential equations (SDEs) underlying the FBE and by approximating that system via the method of averaging from perturbative ODE theory. We also give an overview of our algorithm for numerically integrating the effective FBE. This discretizes the phase space using spectral methods and discretizes time via the additive Runge–Kutta (ARK) method which is a high-order semi-implicit method. We also discuss the relevance of the third mathematical model for spin tracking.

Physics↗

Phased: Phase-Aware Submodularity-Based Energy Disaggregation

Energy disaggregation is the task of discerning the energy consumption of individual appliances from aggregated measurements, which holds promise for understanding and reducing energy usage. In this paper, we propose PHASED, an optimization approach for energy disaggregation that has two key features: PHASED (i) exploits the structure of power distribution systems to make use of readily available measurements that are neglected by existing methods, and (ii) poses the problem as a minimization of a difference of sub-modular functions. We leverage this form by applying a discrete optimization variant of the majorization-minimization algorithm to iteratively minimize a sequence of global upper bounds of the cost function to obtain high-quality approximate solutions. PHASED improves the disaggregation accuracy of state-of-the-art models by up to 61% and achieves better prediction on heavy load appliances.

ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATION↗

cuAlign: Scalable Network Alignment on GPU Accelerators

Given two graphs, the objective of network alignment is to find the best one-to-one mapping of vertices in one graph (??) to vertices in the other (??), such that the number of overlaps is maximized. We say that edges(??, ??) ???and(??', ??') ??? are overlapped if ?? is mapped to ??' and ?? is mapped to??'. Network alignment is an important optimization problem with several applications in bioinformatics, computer vision and ontology matching. Since it is an NP-hard problem, efficient heuristics and scalable implementations are necessary. In this work, we introduce a new framework that combines the concepts of intra-network proximity using vertex embedding,Belief Propagation (BP) and approximate weighted matching, and provides qualitative improvements up to22%over state-of-the-art approaches. We also provide scalable implementations on GPU accelerators, demonstrating up to19×speedup for Belief Propagation and 3× speedup for approximate weighted matching relative to previous multithreaded implementation. A combination of combinatorial and algebraic kernels within the network alignment algorithm poses significant hurdles for parallelization. Load imbalance and irregular DRAM traffic limit achievable performance on GPUs. Our novel approach identifies and exploits unique structural proper-ties of the BP-based algorithm and employs code fusion to reduce data movement between different steps of the algorithm. Using a diverse set of inputs, we demonstrate qualitative improvements of our algorithms, and performance gains of our GPU-accelerated implementation. We believe that our work will enable algorithmic improvements and practical applications of network alignment.

Xiang, Lizhi↗

Learning the ground state of a non-stoquastic quantum Hamiltonian in a rugged neural network landscape

Strongly interacting quantum systems described by non-stoquastic Hamiltonians exhibit rich low-temperature physics. Yet, their study poses a formidable challenge, even for state-of-the-art numerical techniques. Here, we investigate systematically the performance of a class of universal variational wave-functions based on artificial neural networks, by considering the frustrated spin- 1/2 1 / 2 J_1-J_2 J 1 − J 2 Heisenberg model on the square lattice. Focusing on neural network architectures without physics-informed input, we argue in favor of using an ansatz consisting of two decoupled real-valued networks, one for the amplitude and the other for the phase of the variational wavefunction. By introducing concrete mitigation strategies against inherent numerical instabilities in the stochastic reconfiguration algorithm we obtain a variational energy comparable to that reported recently with neural networks that incorporate knowledge about the physical system. Through a detailed analysis of the individual components of the algorithm, we conclude that the rugged nature of the energy landscape constitutes the major obstacle in finding a satisfactory approximation to the ground state wavefunction, and prevents learning the correct sign structure. In particular, we show that in the present setup the neural network expressivity and Monte Carlo sampling are not primary limiting factors.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Lead Slowing-Down Spectrometry Time Spectral Analysis for Spent Fuel Assay: FY12 Status Report

Executive Summary Developing a method for the accurate, direct, and independent assay of the fissile isotopes in bulk materials (such as used fuel) from next-generation domestic nuclear fuel cycles is a goal of the Office of Nuclear Energy, Fuel Cycle R&D, Material Protection and Control Technology (MPACT) Campaign. To meet this goal, MPACT supports a multi-institutional collaboration, of which PNNL is a part, to study the feasibility of Lead Slowing Down Spectroscopy (LSDS). This technique is an active nondestructive assay method that has the potential to provide independent, direct measurement of Pu and U isotopic masses in used fuel with an uncertainty considerably lower than the approximately 10% typical of today’s confirmatory methods. This document is a progress report for FY2012 PNNL analysis and algorithm development. Progress made by PNNL in FY2012 continues to indicate the promise of LSDS analysis and algorithms applied to used fuel assemblies. PNNL further refined the semi-empirical model developed in FY2011 based on singular value decomposition (SVD) to numerically account for the effects of self-shielding. The average uncertainty in the Pu mass across the NGSI-64 fuel assemblies was shown to be less than 3% using only six calibration assemblies with a 2% uncertainty in the isotopic masses. When calibrated against the six NGSI-64 fuel assemblies, the algorithm was able to determine the total Pu mass within <2% uncertainty for the 27 diversion cases also developed under NGSI. Two purely empirical algorithms were developed that do not require the use of Pu isotopic fission chambers. The semi-empirical and purely empirical algorithms were successfully tested using MCNPX simulations as well applied to experimental data measured by RPI using their LSDS. The algorithms were able to describe the 235U masses of the RPI measurements with an average uncertainty of 2.3%. Analyses were conducted that provided valuable insight with regard to design requirements (e.g. Pb stack size, neutron source location) of an LSDS for the purpose of assaying used fuel assemblies. Sensitivity studies were conducted that provide insight as to how the LSDS instrument can be improved by making it more sensitive to the center of the fuel assemblies. In FY2013, PNNL will continue efforts to develop and refine design requirements of an LSDS for the ultimate purpose of assaying used fuel assemblies. Future efforts will be directed toward more extensive experimental benchmarking of currently implemented time-spectra analysis algorithms.

Kulisek, Jonathan A.↗

Non-Intrusive Parallel-in-Time Solvers for Partial Differential Equations (Final Report)

Many time-dependent problems and simulations are often modeled using Partial Differential Equations. Traditional modeling approaches that use sequential time-stepping are reaching a bottleneck in optimizing efficiency. The Center of Applied Science and Computing at Lawrence Livermore National Laboratory extensively works on parallelizing these algorithms to leverage the increasing computational power from the growing number of processors in computer hardware. In particular, they aim to design non-intrusive algorithms that can generalize to a variety of problems and sizes without requiring additional information from or modifications on the original problems. Multigrid Reduction in Time (MGRIT) is a parallel-in-time algorithm that is designed to be non-intrusive. This project focuses on increasing the efficiency of MGRIT by approximating the coarse-grid operator using machine learning approaches as a means to find the most non-intrusive, or general, solution.

97 MATHEMATICS AND COMPUTING↗

Method to analyze remotely sensed spectral data

A fast and rigorous multivariate curve resolution (MCR) algorithm is applied to remotely sensed spectral data. The algorithm is applicable in the solar-reflective spectral region, comprising the visible to the shortwave infrared (ranging from approximately 0.4 to 2.5 .mu.m), midwave infrared, and thermal emission spectral region, comprising the thermal infrared (ranging from approximately 8 to 15 .mu.m). For example, employing minimal a priori knowledge, notably non-negativity constraints on the extracted endmember profiles and a constant abundance constraint for the atmospheric upwelling component, MCR can be used to successfully compensate thermal infrared hyperspectral images for atmospheric upwelling and, thereby, transmittance effects. Further, MCR can accurately estimate the relative spectral absorption coefficients and thermal contrast distribution of a gas plume component near the minimum detectable quantity.

97 MATHEMATICS AND COMPUTING↗

Gradient Coding With Iterative Block Leverage Score Sampling

Gradient coding is a method for mitigating straggling servers in a centralized computing network that uses erasure-coding techniques to distributively carry out first-order optimization methods. Randomized numerical linear algebra uses randomization to develop improved algorithms for large-scale linear algebra computations. In this study, we propose a method for distributed optimization that combines gradient coding and randomized numerical linear algebra. The proposed method uses a randomized ℓ 2 -subspace embedding and a gradient coding technique to distribute blocks of data to the computational nodes of a centralized network, and at each iteration the central server only requires a small number of computations to obtain the steepest descent update. The novelty of our approach is that the data is replicated according to importance scores, called block leverage scores, in contrast to most gradient coding approaches that uniformly replicate the data blocks. Furthermore, we do not require a decoding step at each iteration, avoiding a bottleneck in previous gradient coding schemes. We show that our approach results in a valid ℓ 2 -subspace embedding, and that our resulting approximation converges to the optimal solution.

97 MATHEMATICS AND COMPUTING↗

Monte Carlo simulation methods in moment-based scale-bridging algorithms for thermal radiative-transfer problems

We present a moment-based acceleration algorithm applied to Monte Carlo simulation of thermal radiative-transfer problems. Our acceleration algorithm employs a continuum system of moments to accelerate convergence of stiff absorption–emission physics. The combination of energy-conserving tallies and the use of an asymptotic approximation in optically thick regions remedy the difficulties of local energy conservation and mitigation of statistical noise in such regions. We demonstrate the efficiency and accuracy of the developed method. We also compare directly to the standard linearization-based method of Fleck and Cummings [1]. A factor of 40 reduction in total computational time is achieved with the new algorithm for an equivalent (or more accurate) solution as compared with the Fleck–Cummings algorithm.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

DSMC moving-boundary algorithms for simulating MEMS geometries with opening and closing gaps.

Moving-boundary algorithms for the Direct Simulation Monte Carlo (DSMC) method are investigated for a microbeam that moves toward and away from a parallel substrate. The simpler but analogous one-dimensional situation of a piston moving between two parallel walls is investigated using two moving-boundary algorithms. In the first, molecules are reflected rigorously from the moving piston by performing the reflections in the piston frame of reference. In the second, molecules are reflected approximately from the moving piston by moving the piston and subsequently moving all molecules and reflecting them from the moving piston at its new or old position.

99 GENERAL AND MISCELLANEOUS↗

MO-F-CAMPUS-J-04: Tissue Segmentation-Based MR Electron Density Mapping Method for MR-Only Radiation Treatment Planning of Brain

Purpose: Automatically derive electron density of tissues using MR images and generate a pseudo-CT for MR-only treatment planning of brain tumours. Methods: 20 stereotactic radiosurgery (SRS) patients’ T1-weighted MR images and CT images were retrospectively acquired. First, a semi-automated tissue segmentation algorithm was developed to differentiate tissues with similar MR intensities and large differences in electron densities. The method started with approximately 12 slices of manually contoured spatial regions containing sinuses and airways, then air, bone, brain, cerebrospinal fluid (CSF) and eyes were automatically segmented using edge detection and anatomical information including location, shape, tissue uniformity and relative intensity distribution. Next, soft tissues - muscle and fat were segmented based on their relative intensity histogram. Finally, intensities of voxels in each segmented tissue were mapped into their electron density range to generate pseudo-CT by linearly fitting their relative intensity histograms. Co-registered CT was used as a ground truth. The bone segmentations of pseudo-CT were compared with those of co-registered CT obtained by using a 300HU threshold. The average distances between voxels on external edges of the skull of pseudo-CT and CT in three axial, coronal and sagittal slices with the largest width of skull were calculated. The mean absolute electron density (in Hounsfield unit) difference of voxels in each segmented tissues was calculated. Results: The average of distances between voxels on external skull from pseudo-CT and CT were 0.6±1.1mm (mean±1SD). The mean absolute electron density differences for bone, brain, CSF, muscle and fat are 78±114 HU, and 21±8 HU, 14±29 HU, 57±37 HU, and 31±63 HU, respectively. Conclusion: The semi-automated MR electron density mapping technique was developed using T1-weighted MR images. The generated pseudo-CT is comparable to that of CT in terms of anatomical position of tissues and similarity of electron density assignment. This method can allow MR-only treatment planning.

60 APPLIED LIFE SCIENCES↗