Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “decomposition 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 109 records · Page 6

A scalable mixed-integer decomposition approach for optimal power system restoration

The optimal restoration problem lies at the foundation of the evaluation and improvement of resilience in power systems. In this paper we present a scalable decomposition algorithm, based on the integer L-shaped method, for solving this problem for realistic power systems. The algorithm works by partitioning the problem into a master problem and a slave problem. The master problem optimizes over energization sequences of generators, buses and branches, for the entire restoration horizon, while respecting stylized energization requirements. The slave problem verifies that there exist power flow solutions supporting the energization sequences proposed by the master problem, adding cuts to the master if an infeasible sequence is detected. The power flow verification is carried out using a piece-wise linear approximation of the power flow equations, capable of capturing overvoltage situations common in restoration procedures. We develop specialized binary cuts and hybrid Benders-binary cuts for separating infeasible islands, which are stronger than regular no-good cuts, as well as heuristics for obtaining feasible solutions. We present numerical results for the IEEE 39- and 118-bus systems, and for the Chilean 1500-bus grid, where our algorithm finds near-optimal restoration sequences orders of magnitude faster than the state-of-the-art, demonstrating the effectiveness of the proposed approach.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Forward-Weighted CADIS Method for Variance Reduction of Monte Carlo Reactor Analyses

Current state-of-the-art tools and methods used to perform 'real' commercial reactor analyses use high-fidelity transport codes to produce few-group parameters at the assembly level for use in low-order methods applied at the core level. Monte Carlo (MC) methods, which allow detailed and accurate modeling of the full geometry and energy details and are considered the 'gold standard' for radiation transport solutions, are playing an ever-increasing role in correcting and/or verifying the several-decade-old methodology used in current practice. However, the prohibitive computational requirements associated with obtaining fully converged system-wide solutions restrict the role of MC to benchmarking deterministic results at a limited number of state-points for a limited number of relevant quantities. A goal of current research at Oak Ridge National Laboratory (ORNL) is to change this paradigm by enabling the direct use of MC for full-core reactor analyses. The most significant of the many technical challenges that must be overcome is the slow non-uniform convergence of system-wide MC estimates and the memory requirements associated with detailed solutions throughout a reactor (problems involving hundreds of millions of different material and tally regions due to fuel irradiation, temperature distributions, and the needs associated with multi-physics code coupling). To address these challenges, research has focused on development in the following two areas: (1) a hybrid deterministic/MC method for determining high-precision fluxes throughout the problem space in k-eigenvalue problems and (2) an efficient MC domain-decomposition algorithm that partitions the problem phase space onto multiple processors for massively parallel systems, with statistical uncertainty estimation. The focus of this paper is limited to the first area mentioned above. It describes the FW-CADIS method applied to variance reduction of MC reactor analyses and provides initial results for calculating group-wise fluxes throughout a generic 2-D pressurized water reactor (PWR) quarter core model.

21 SPECIFIC NUCLEAR REACTORS AND ASSOCIATED PLANTS↗

A 3D Parallel Algorithm for QR Decomposition

Interprocessor communication often dominates the runtime of large matrix computations. Here, we present a parallel algorithm for computing QR decompositions whose bandwidth cost (communication volume) can be decreased at the cost of increasing its latency cost (number of messages). By varying a parameter to navigate the bandwidth/latency tradeoff, we can tune this algorithm for machines with different communication costs.

97 MATHEMATICS AND COMPUTING↗

On Two Algorithms of Wavelet Decomposition for Spaces of Linear Splines

The purpose of this paper is to construct new types of wavelets for minimal splines on an irregular grid. The approach applied to construct spline-wavelet decompositions uses approximation relations as an initial structure for constructing the spaces of minimal splines. The advantages of this approach are the possibilities of using irregular grids and sufficiently arbitrary nonpolynomial spline-wavelets.

97 MATHEMATICS AND COMPUTING↗

Singular value decomposition utilizing parallel algorithms on graphical processors

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

99 GENERAL AND MISCELLANEOUS↗

Scalable algorithms for domain decomposition of Monte Carlo neutral particle transport simulations on unstructured mesh

Monte Carlo simulations are the gold standard in particle transport simulations, for shielding and nuclear reactor simulations Full core simulations can require terabytes of memory for tracking pin-resolved (up to 50k pins), nuclide (200 tracked), axial (20-200 zones) reaction rates Domain decomposition, splitting the calculation and the memory storage, among several nodes is challenging as it involves communication of particles across domain boundaries We created a new MOOSE application, MaCaw, to study this problem Algorithms developed for ray tracing in MOOSE were adapted for simulating neutral particle transport Physics and tally routines in OpenMC, dynamically linked, are called from the application

22 GENERAL STUDIES OF NUCLEAR REACTORS↗

Quantum-classical tradeoffs and multi-controlled quantum gate decompositions in variational algorithms

The computational capabilities of near-term quantum computers are limited by the noisy execution of gate operations and a limited number of physical qubits. Hybrid variational algorithms are well-suited to near-term quantum devices because they allow for a wide range of tradeoffs between the amount of quantum and classical resources used to solve a problem. This paper investigates tradeoffs available at both the algorithmic and hardware levels by studying a specific case – applying the Quantum Approximate Optimization Algorithm (QAOA) to instances of the Maximum Independent Set (MIS) problem. We consider three variants of the QAOA which offer different tradeoffs at the algorithmic level in terms of their required number of classical parameters, quantum gates, and iterations of classical optimization needed. Since MIS is a constrained combinatorial optimization problem, the QAOA must respect the problem constraints. This can be accomplished by using many multi-controlled gate operations which must be decomposed into gates executable by the target hardware. We study the tradeoffs available at this hardware level, combining the gate fidelities and decomposition efficiencies of different native gate sets into a single metric called the gate decomposition cost .

Tomesh, Teague↗

A WAVELET-GALERKIN ALGORITHM OF THE E/B DECOMPOSITION OF COSMIC MICROWAVE BACKGROUND POLARIZATION MAPS

We develop an algorithm of separating the E and B modes of the cosmic microwave background (CMB) polarization from the noisy and discretized maps of Stokes parameters Q and U in a finite area. A key step of the algorithm is to take a wavelet-Galerkin discretization of the differential relation between the E, B and Q, U fields. This discretization allows derivative operator to be represented by a matrix, which is exactly diagonal in scale space, and narrowly banded in spatial space. We show that the effect of boundary can be eliminated by dropping a few discrete wavelet transform modes, located on or nearby the boundary. This method reveals that the derivative operators will cause large errors in the E and B power spectra on small scales if the Q and U maps contain Gaussian noise. It also reveals that if the Q and U maps are random, these fields lead to the mixing of E and B modes. Consequently, the B mode will be contaminated if the powers of E modes are much larger than that of B modes. Nevertheless, numerical tests show that the power spectra of both E and B on scales larger than the finest scale by a factor of 4 and higher can reasonably be recovered, even when the power ratio of E to B modes is as large as about 10{sup 2}, and the signal-to-noise ratio is equal to 10 and higher. This is because the Galerkin discretization is free of false correlations and keeps the contamination under control. As wavelet variables contain information of both spatial and scale spaces, the developed method is also effective to recover the spatial structures of the E and B mode fields.

79 ASTRONOMY AND ASTROPHYSICS↗

Parallel State Estimation Assessment with Practical Data

This paper presents a full-cycle parallel state estimation (PSE) implementation using a preconditioned conjugate gradient algorithm. The developed code is able to solve large-size power system state estimation within 5 seconds using real-world data, comparable to the Supervisory Control And Data Acquisition (SCADA) rate. This achievement allows the operators to know the system status much faster to help improve grid reliability. Case study results of the Bonneville Power Administration (BPA) system with real measurements are presented. The benefits of fast state estimation are also discussed.

State Estimation, Preconditioned Conjugate Gradien↗

Big Data For Operation and Maintenance Cost Reduction

The purpose of this research is to develop a first-of-a-kind framework for integrating Big Data capability into the daily activities of our current fleet of nuclear power plants. Big Data is traditionally defined as data sets with high volume, velocity, and heterogeneity, and the existing Big Data analytics capabilities are now widely popular in fields such as finance, weather, e-commerce, healthcare and sports. In the nuclear industry, while the volume and velocity of data may present computational challenges for existing analytics capabilities, data heterogeneity are seen to present the major challenge. This research project mainly focuses on incorporating the wide range of data heterogeneities in nuclear power plants into an integrated Big Data Analytics capability. The primary end-product of this project is a Big Data framework that is capable of dealing with the large volume and heterogeneity of the data found in nuclear power plants to extract timely and valuable information on equipment performance. The framework can generate system insights that are actionable relations between measurable impacts and the corresponding maintenance action plans and enable optimization of plant operation and maintenance based on the extracted information. The developed framework is capable of handling heterogeneous data including both image data and time-series sensor data. Specifically, this developed framework includes the following components. The first component is an overarching maintenance ontology which includes system insights required by maintenance optimization. The maintenance ontology interacts with other components in the developed framework. The second component handles Piping & Instrumentation Diagram (P&ID) data. It can be used to extract system components and their relations automatically from the P&IDs. This extracted information is stored in the first component, i.e., maintenance ontology, and is also used as input to the third component, i.e., a tool for generating the fault tree for the corresponding system. The generated fault tree in turn is stored in the ontology for assessing risk that is used as a criterion in maintenance policy optimization. The fourth component is a tool for inferring the parameters in the Markov degradation model for a nuclear system. It uses basic information from the ontology. The fifth component is a tool for assessing the degradation level using sensor measurement data, for example, pressure, flowrate. This tool can be used for determining corrective maintenance actions. The results obtained from components four and five are returned to the ontology. The sixth component of the framework is a tool for optimizing the maintenance policy for a nuclear system of interest. It takes certain basic information from the ontology, e.g., costs of maintenance actions and system failures, as input, and returns the optimal maintenance policy to the ontology. This tool can be used for determining predictive maintenance actions. A set of experiments have also been conducted to verify the algorithms developed in this project for nuclear system degradation monitoring. The experiments are based on four solenoid valves, similar to the ones used in nuclear power plants. The analyses based on the experimental data using two algorithms, i.e., the Randomized Window Decomposition (RWD) algorithm and the particle filtering algorithm, and the results are introduced in the report. The Big Data framework developed in this project can be used as a support tool in daily activities of plant operation and maintenance and will reduce current costs while maintaining or improving safety levels. Overall, the project will not only benefit existing reactors, however it will open new frontiers to realize the long overdue value of Big Data Analytics in the nuclear sphere.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

A low-communication, parallel algorithm for solving PDEs based on range decomposition

This work proposes a new, low-communication algorithm for solving PDEs on massively parallel computers. The range decomposition (RD) algorithm exposes coarse-grain parallelism by applying nested iteration and adaptive mesh refinement locally before performing a global communication step. Just a few such steps are observed to be sufficient to obtain accuracy within a small multiple of discretization error. The target applications are petascale and exascale machines, where hierarchical parallelism is required and traditional parallel numerical PDE communication patterns are costly because of message latency. The RD algorithm uses a partition of unity to equally distribute the error, and thus, the work. The computational advantages of this approach are that the decomposed problems can be solved in parallel without any communication until the partitioned solutions are summed. This offers potential advantages in the paradigm of expensive communication but very cheap computation. This paper introduces the method and explains the details of the communication step. Two performance models are developed, showing that the latency cost associated with a traditional parallel implementation of nested iteration is proportional to log(P) 2 , whereas the RD method reduces the communication latency to log(P), while maintaining similar bandwidth costs. Numerical results for two problems, Laplace and advection diffusion, demonstrate the enhanced performance, and a heuristic argument explains why the method converges quickly.

97 MATHEMATICS AND COMPUTING↗

Compression of tokamak boundary plasma simulation data using a maximum volume algorithm for matrix skeleton decomposition

This report demonstrates satisfactory data compression of SOLPS-ITER simulation output ranging from 2D fields, 1D profiles, and 0D scalar variables with a novel matrix decomposition approach. The singular value decomposition (SVD) scales poorly for large matrix sizes and is unsuited to the application on high dimensional data common to fusion plasma physics simulation. In this work, we employ the columns-submatrix-rows (CUR) matrix factorization technique in order to compute a low-rank approximation up to two orders of magnitude faster than the SVD, but within a nominal L2-norm relative error of ε = 10 –2 . In addition, the CUR approach maintains the original format of the data, in its extracted columns and rows, allowing for interpretable data storage at the original resolution of the simulation. We utilize an iterative algorithm to compute the CUR decomposition of simulation output by maximizing the volume, or linearly independent information content, of a low-rank submatrix contained within the data. Experiments over $\textit{n} × \textit{n}$ randomized test matrices with embedded rank-deficient features show that this maximum volume implementation of CUR matrix approximation has reduced asymptotic computational complexity on the order of n compared to the SVD, which scales approximately as $n^3$. These results show that the CUR technique can be used to effectively select time step snapshots (columns) of over 140 SOLPS-ITER output variables and the associated discretized coordinate timeseries (rows) allowing for reconstruction of the complete simulation dynamics.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

Tensor Toolbox for MATLAB v. 3.0

Tensors (also known as multidimensional arrays or N-way arrays) are used in a variety of applications ranging from chemometrics to network analysis. The Tensor Toolbox provides classes for manipulating dense, sparse, and structured tensors using MATLAB's object-oriented features. It also provides algorithms for tensor decomposition and factorization, algorithms for computing tensor eigenvalues, and methods for visualization of results.

Kolda, Tamara↗

An exponential time 2-approximation algorithm for bandwidth

The bandwidth of a graph G on n vertices is the minimum b such that the vertices of G can be labeled from 1 to n such that the labels of every pair of adjacent vertices differ by at most b. In this paper, we present a 2-approximation algorithm for the Bandwidth problem that takes worst-case {Omicron}(1.9797{sup n}) = {Omicron}(3{sup 0.6217n}) time and uses polynomial space. This improves both the previous best 2- and 3-approximation algorithms of Cygan et al. which have an {Omicron}*(3{sup n}) and {Omicron}*(2{sup n}) worst-case time bounds, respectively. Our algorithm is based on constructing bucket decompositions of the input graph. A bucket decomposition partitions the vertex set of a graph into ordered sets (called buckets) of (almost) equal sizes such that all edges are either incident on vertices in the same bucket or on vertices in two consecutive buckets. The idea is to find the smallest bucket size for which there exists a bucket decomposition. The algorithm uses a simple divide-and-conquer strategy along with dynamic programming to achieve this improved time bound.

97 MATHEMATICS AND COMPUTING↗

Randomized Algorithms for Low-Rank Matrix and Tensor Decompositions

This paper surveys randomized algorithms in numerical linear algebra for low-rank decompositions of matrices and tensors. The survey begins with a review of classical matrix algorithms that can be accelerated by randomized dimensionality reduction, such as the singular value decomposition (SVD) or interpolative (ID) and CUR decompositions. Recent advances in randomized dimensionality reduction are discussed, including new methods of fast matrix sketching and sampling techniques, which are incorporated into classical matrix algorithms for fast low-rank matrix approximations. The extension of randomized matrix algorithms to tensors is then explored for several low-rank tensor decompositions in the CP and Tucker formats, including the higher-order SVD, ID, and CUR decomposition.

Pearce, Katherine J. [The University of Texas at A↗