Search NASA⌕ Search

SEARCH · Search NASA

Results for “Decomposition 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 127 records · Page 7

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↗

Adaptive Wavelet Decomposition of Matrix Flows

Adaptive algorithms for constructing spline-wavelet decompositions of matrix flows from a linear space of matrices over a normed field are presented. The algorithms suggested provides for an a priori prescribed estimate of the deviation of the basic flow from the initial one. Comparative bounds of the volumes of data in the basic flow for various irregularity characteristics of the initial flow are obtained in the cases of pseudo-equidistant and adaptive grids. Limit characteristics of the above-mentioned volumes are given in the cases where the initial flow is generated by differentiable functions.

97 MATHEMATICS AND COMPUTING↗

Dynamic load balancing algorithm for molecular dynamics based on Voronoi cells domain decompositions

We present a new algorithm for automatic parallel load balancing in classical molecular dynamics. It assumes a spatial domain decomposition of particles into Voronoi cells. It is a gradient method which attempts to minimize a cost function by displacing Voronoi sites associated with each processor/sub-domain along steepest descent directions. Excellent load balance has been obtained for quasi-2D and 3D practical applications, with up to 440·10 6 particles on 65,536 MPI tasks.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗

Hierarchical Distributed Optimal Power Flow of HV and MV Distribution Networks With Continuous and Discrete Devices

With large-scale distributed photovoltaics (PVs) being integrated into distribution networks (DNs), coordinated optimal power flow (OPF) of high voltage (HV) and medium voltage (MV) DNs should be investigated to optimally dispatch the distributed PVs and other network devices. Here, this paper presents a hierarchical distributed OPF method for HV and MV DNs with on-load tap changers, reactive power compensators, feeder switches and distributed PVs. A hierarchical master-slave control architecture is applied to implement coordinated OPF of two-layer DNs. The HV master problem and MV subproblems are transformed into mixed-integer convex problems respectively with second order cone programming and LinDistFlow approximation. Since there is no efficient distributed algorithm to solve such OPF models with integer subproblems, a novel distributed algorithm is proposed in this paper to efficiently solve the hierarchical coordinated OPF model with integer subproblems in a distributed manner. In the proposed algorithm, the coordinated OPF model is solved in a branch-and-bound framework, where in each branch node generalized Benders decomposition (GBD) algorithm is applied to decompose the coordinated OPF model into a master problem and relaxed subproblems and solves them iteratively to get optimal solution. The GBD optimal and feasible cutting planes generated in a branch node are proved to be valid for its descendants. Moreover, three acceleration techniques are introduced into the proposed algorithm to improve computational efficiency. Finally, the effectiveness and accuracy of the proposed method are verified via simulation tests in Jinzhai DNs of China.

42 ENGINEERING↗

A tightly-coupled domain-decomposition approach for highly nonlinear stochastic multiphysics systems

Multiphysics simulations often involve nonlinear components that are driven by internally generated or externally imposed random fluctuations. When used with a domain-decomposition (DD) algorithm, such components have to be coupled in a way that both accurately propagates the noise between the subdomains and lends itself to a stable and cost-effective temporal integration. We develop a conservative DD approach in which tight coupling is obtained by using a Jacobian-free Newton–Krylov (JfNK) method with a generalized minimum residual iterative linear solver. This strategy is tested on a coupled nonlinear diffusion system forced by a truncated Gaussian noise at the boundary. Enforcement of path-wise continuity of the state variable and its flux, as opposed to continuity in the mean, at interfaces between subdomains enables the DD algorithm to correctly propagate boundary fluctuations throughout the computational domain. Reliance on a single Newton iteration (explicit coupling), rather than on the fully converged JfNK (implicit) coupling, may increase the solution error by an order of magnitude. Increase in communication frequency between the DD components reduces the explicit coupling's error, but makes it less efficient than the implicit coupling at comparable error levels for all noise strengths considered. Finally, the DD algorithm with the implicit JfNK coupling resolves temporally-correlated fluctuations of the boundary noise when the correlation time of the latter exceeds some multiple of an appropriately defined characteristic diffusion time.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Randomized algorithms for generalized singular value decomposition with application to sensitivity analysis

The generalized singular value decomposition (GSVD) is a valuable tool that has many applications in computational science. However, computing the GSVD for large-scale problems is challenging. Motivated by applications in hyper-differential sensitivity analysis (HDSA), in this work we propose new randomized algorithms for computing the GSVD which use randomized subspace iteration and weighted QR factorization. Detailed error analysis is given which provides insight into the accuracy of the algorithms and the choice of the algorithmic parameters. We demonstrate the performance of our algorithms on test matrices and a large-scale model problem where HDSA is used to study subsurface flow.

97 MATHEMATICS AND COMPUTING↗

Autonomous Polycrystalline Material Decomposition For Hyperspectral Neutron Tomography

Hyperspectral neutron tomography is an effective method for analyzing crystalline material samples with complex compositions in a non-destructive manner. Since the counts in the hyperspectral neutron radiographs directly depend on the neutron cross-sections, materials may exhibit contrasting neutron responses across wavelengths. Therefore, it is possible to extract the unique signatures associated with each material and use them to separate the crystalline phases simultaneously.We introduce an autonomous material decomposition (AMD) algorithm to automatically characterize and localize polycrystalline structures using Bragg edges with contrasting neutron responses from hyperspectral data. The algorithm estimates the linear attenuation coefficient spectra from the measured radiographs and then uses these spectra to perform polycrystalline material decomposition and reconstructs 3D material volumes to localize materials in the spatial domain. Our results demonstrate that the method can accurately estimate both the linear attenuation coefficient spectra and associated reconstructions on both simulated and experimental neutron data.

Samin nur chowdhury, Mohammad↗

Iterative stability analysis of spatial domain decomposition based on block Jacobi algorithm for the diamond-difference scheme

Here, we study convergence of the integral transport matrix method (ITMM) based on a parallel block Jacobi (PBJ) iterative strategy for solving particle transport problems. The ITMM is a spatial domain decomposition method proposed for massively parallel computations. AFourier analysis of the PBJ-based iterations applied to SN diamond-difference equations in 1D slab and 2D Cartesian geometries is performed. It is carried out for infinite-medium problems with homogeneous material properties. To analyze the performance of the ITMM with the PBJ algorithm and evaluate its potential in scalability we consider a limiting case of one spatial cell per subdomain. The analysis shows that in such limit the spectral radius of the iteration method is one without regard to values of the scattering ratio and optical thickness of the spatial cells. This implies lack of convergence in infinite medium. Numerical results of finite-medium problems are presented. They demonstrate effects of finite size of spatial domain on the performance of the iteration algorithm as well as its asymptotic behavior when the extent of the spatial domain increases. Finally, these numerical experiments also show that for finite domains iterative convergence to a finite criterion is achievable in a multiple of the sum of number of cells in each dimension.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

S-OPT: A Points Selection Algorithm for Hyper-Reduction in Reduced Order Models

While projection-based reduced order models can reduce the dimension of full order solutions, the resulting reduced models may still contain terms that scale with the full order dimension. Hyper-reduction techniques are sampling-based methods that further reduce this computational complexity by approximating such terms with a much smaller dimension. The goal of this work is to introduce the points selection algorithm developed by Shin and Xiu as a hyper-reduction method. The selection algorithm was originally proposed as a stochastic collocation method for uncertainty quantification. Since the algorithm aims at maximizing a quantity $\mathcal{S}$ that measures both the column orthogonality and the determinant, we refer to the algorithm as S-OPT. Numerical examples are provided to demonstrate the performance of S-OPT and to compare its performance with a gappy proper orthogonal decomposition (POD) algorithm. Here, we found that using the S-OPT algorithm is shown to predict the full order solutions with higher accuracy than gappy POD especially when the number of sampling points is small, although we note that S-OPT shows slow asymptotic convergence with respect to the number of samples for some applications, e.g., Lagrangian hydrodynamics.

97 MATHEMATICS AND COMPUTING↗

AUTONOMOUS GAUSSIAN DECOMPOSITION

We present a new algorithm, named Autonomous Gaussian Decomposition (AGD), for automatically decomposing spectra into Gaussian components. AGD uses derivative spectroscopy and machine learning to provide optimized guesses for the number of Gaussian components in the data, and also their locations, widths, and amplitudes. We test AGD and find that it produces results comparable to human-derived solutions on 21 cm absorption spectra from the 21 cm SPectral line Observations of Neutral Gas with the EVLA (21-SPONGE) survey. We use AGD with Monte Carlo methods to derive the H i line completeness as a function of peak optical depth and velocity width for the 21-SPONGE data, and also show that the results of AGD are stable against varying observational noise intensity. The autonomy and computational efficiency of the method over traditional manual Gaussian fits allow for truly unbiased comparisons between observations and simulations, and for the ability to scale up and interpret the very large data volumes from the upcoming Square Kilometer Array and pathfinder telescopes.

79 ASTRONOMY AND ASTROPHYSICS↗

Extended dynamic mode decomposition for model reduction in fluid dynamics simulations

High computational cost and storage/memory requirements of fluid dynamics simulations constrain their usefulness as a predictive tool. Reduced-order models (ROMs) provide a viable solution to this challenge by extracting the key underlying dynamics of a complex system directly from data. We investigate the efficacy and robustness of an extended dynamic mode decomposition (xDMD) algorithm in constructing ROMs of three-dimensional cardiovascular computations. Focusing on the ROMs' accuracy in representation and interpolation, we relate these metrics to the truncation rank of singular value decomposition, which underpins xDMD and other approaches to ROM construction. Our key innovation is to relate the truncation rank to the singular values of the original flow problem. This result establishes a priori guidelines for the xDMD deployment and its likely success as a means of data compression and reconstruction of the system's dynamics from dominant spatiotemporal structures present in the data.

Mechanics↗

Parrallel Implementation of Fast Randomized Algorithms for Low Rank Matrix Decomposition

We analyze the parallel performance of randomized interpolative decomposition by de- composing low rank complex-valued Gaussian random matrices larger than 100 GB. We chose a Cray XMT supercomputer as it provides an almost ideal PRAM model permitting quick investigation of parallel algorithms without obfuscation from hardware idiosyncrasies. We obtain that on non-square matrices performance scales almost linearly with runtime about 100 times faster on 128 processors. We also verify that numerically discovered error bounds still hold on matrices two orders of magnitude larger than those previously tested.

Lucas, Andrew J.↗

Benders Cut Classification via Support Vector Machines for Solving Two-Stage Stochastic Programs

In this work, we consider Benders decomposition for solving two-stage stochastic programs with complete recourse based on finite samples of the uncertain parameters. We define the Benders cuts binding at the final optimal solution or the ones significantly improving bounds over iterations as valuable cuts. We propose a learning-enhanced Benders decomposition (LearnBD) algorithm, which adds a cut classification step in each iteration to selectively generate cuts that are more likely to be valuable cuts. The LearnBD algorithm includes two phases: (i) sampling cuts and collecting information from training problems and (ii) solving testing problems with a support vector machine (SVM) cut classifier. We run the LearnBD algorithm on instances of capacitated facility location and multicommodity network design under uncertain demand. Our results show that SVM cut classifier works effectively for identifying valuable cuts, and the LearnBD algorithm reduces the total solving time of all instances for different problems with various sizes and complexities.

97 MATHEMATICS AND COMPUTING↗

Development of Multiresolution Capabilities for the Holistic Energy Resource Optimization Network (HERON) tool A progress update

INL researchers work on technoeconomic analyses for integrated energy systems (IES) using the Framework for Optimization of ResourCes and Economics (FORCE). Within FORCE, researchers use the Holistic Energy Resource Optimization Network (HERON) tool to conduct optimization of grid portfolios under uncertain market conditions. These optimizations determine optimal capacities for all IES components and strategies for resource dispatch which maximize some economic metric (e.g., net present value). Resource dispatch occurs on finer timescales (typically hours) and thus are asked to respond to a given time series (e.g. hourly load demand profiles for a grid, or pre-determined electricity prices). Volatile and complex bidding dynamics as well as poorly forecasted weather events within deregulated markets add uncertainty to the time series; FORCE can address this uncertainty by training a reduced order model on historical time series and generate unique synthetic time series which represent individual scenarios or realizations of the market. The IES configuration can be simulated under these different sampled realizations and a stochastic optimization is conducted which optimizes the expected value of the desired economic metric. The training of a synthetic time series generator is limited by the chosen time resolution; dynamics can occur on different time scales. Seasonal demand trends can dominate faster dynamical events (such as power outages from certain sectors or severe weather events) which might not get captured correctly by the trained model. In this report, we investigate different ways of addressing the training and generation of time series on multiple time scales using three main algorithms: wavelet decomposition, dynamic mode decomposition, and generative adversarial networks for time series. We demonstrate a time series analysis that yields information on not just the frequency space but also temporal space: where a fast Fourier transform can provide what frequencies dominate, the new algorithms can provide when the frequencies dominate as well. These analyses can help improve IES optimization by allowing researchers to couple simulations at different timescales when it is most needed - seasonal, day-ahead, and real time optimization - with greater computational efficiency. Future work will include implementation of a subset of the proposed algorithms into the FORCE toolset and application of these analyses into multiple timescale optimization.

22 GENERAL STUDIES OF NUCLEAR REACTORS↗