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 631 records · Page 35

Development of multi-hierarchy simulation model with non-uniform space grids for collisionless driven reconnection

A multi-hierarchy simulation model aimed at magnetic reconnection studies has been developed, in which macroscopic and microscopic physics are solved self-consistently and simultaneously. In this work, the previous multi-hierarchy model by these authors is extended to a more realistic one with non-uniform space grids. Based on the domain decomposition method, the multi-hierarchy model consists of three parts: a magnetohydrodynamics algorithm to express the macroscopic global dynamics, a particle-in-cell algorithm to describe the microscopic kinetic physics, and an interface algorithm to interlock macro and micro hierarchies. For its verification, plasma flow injection is simulated in this multi-hierarchy model and it is confirmed that the interlocking method can describe the correct physics. Furthermore, this model is applied to collisionless driven reconnection in an open system. Magnetic reconnection is found to occur in a micro hierarchy by injecting plasma from a macro hierarchy.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

Root-N Krylov-space correction vectors for spectral functions with the density matrix renormalization group

In this work, we propose a method to compute spectral functions of generic Hamiltonians using the density matrix renormalization group (DMRG) algorithm directly in the frequency domain, based on a modified Krylov-space decomposition to compute the correction vectors. Our approach entails the calculation of the root-N (N=2 is the standard square root) of the Hamiltonian propagator using Krylov-space decomposition and repeating this procedure N times to obtain the actual correction vector. We show that our method greatly alleviates the burden of keeping a large bond dimension at large target frequencies, a problem found with conventional correction-vector DMRG, whereas achieving better computational performance at large N. We apply our method to spin and charge spectral functions of t-J and Hubbard models in the challenging two-leg ladder geometry and provide evidence that the root-N approach reaches a much improved spectral resolution compared to the conventional correction vector.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗

Rolling Horizon Based Temporal Decomposition for the Offline Pickup and Delivery Problem with Time Windows

The offline pickup and delivery problem with time windows (PDPTW) is a classical combinatorial optimization problem in the transportation community, which has proven to be very challenging computationally. Due to the complexity of the problem, practical problem instances can be solved only via heuristics, which trade-off solution quality for computational tractability. Among the various heuristics, a common strategy is problem decomposition, that is, the reduction of a large-scale problem into a collection of smaller sub-problems, with spatial and temporal decompositions being two natural approaches. While spatial decomposition has been successful in certain settings, effective temporal decomposition has been challenging due to the difficulty of stitching together the sub-problem solutions across the decomposition boundaries. In this work, we introduce a novel temporal decomposition scheme for solving a class of PDPTWs that have narrow time windows, for which it is able to provide both fast and high-quality solutions. We utilize techniques that have been popularized recently in the context of online dial-a-ride problems along with the general idea of rolling horizon optimization. To the best of our knowledge, this is the first attempt to solve offline PDPTWs using such an approach. To show the performance and scalability of our framework, we use the optimization of paratransit services as a motivating example. Due to the lack of benchmark solvers similar to ours (i.e., temporal decomposition with an online solver), we compare our results with an offline heuristic algorithm using Google OR-Tools. In smaller problem instances (with an average of 129 requests per instance), the baseline approach is as competitive as our framework. However, in larger problem instances (approximately 2,500 requests per instance), our framework is more scalable and can provide good solutions to problem instances of varying degrees of difficulty, while the baseline algorithm often fails to find a feasible solution within comparable compute times.

Kim, Youngseo↗

TP099-CT-800DR Comparison Between SIRZ-2 and Surface Fit Method ($ρ_{e},Ζ_{e}$) Estimation

The primary objective of this test plan is to acquire dual-energy computed tomography (CT) data of 33 well-known specimens using the Leidos Reveal CT-80DR+ baggage scanner housed at LLNL (hereafter referred to as CT-80DR). These data sets will allow us to compare, for each specimen, the accuracy and precision of electron density ($ρ_{e}$) and effective atomic number ($Z_{e}$) estimates obtained from two different algorithmic methods— from TSL’s surface fits and from LLNL’s SIRZ-2 decomposition. A secondary objective is to determine how often it is necessary to acquire CT-80DR spectral response information.

42 ENGINEERING↗

Toward a More Robust Pruning Procedure for MLP Networks

Choosing a proper neural network architecture is a problem of great practical importance. Smaller models mean not only simpler designs but also lower variance for parameter estimation and network prediction. The widespread utilization of neural networks in modeling highlights an issue in human factors. The procedure of building neural models should find an appropriate level of model complexity in a more or less automatic fashion to make it less prone to human subjectivity. In this paper we present a Singular Value Decomposition based node elimination technique and enhanced implementation of the Optimal Brain Surgeon algorithm. Combining both methods creates a powerful pruning engine that can be used for tuning feedforward connectionist models. The performance of the proposed method is demonstrated by adjusting the structure of a multi-input multi-output model used to calibrate a six-component wind tunnel strain gage.

Stepniewski, Slawomir W.↗

Comparison of N2O Emissions from Soils at Three Temperate Agricultural Sites

Nitrous oxide (N2O) flux simulations by four models were compared with year-round field measurements from five temperate agricultural sites in three countries. The field sites included an unfertilized, semi-arid rangeland with low N2O fluxes in eastern Colorado, USA; two fertilizer treatments (urea and nitrate) on a fertilized grass ley cut for silage in Scotland; and two fertilized, cultivated crop fields in Germany where N2O loss during the winter was quite high. The models used were daily trace gas versions of the CENTURY model, DNDC, ExpertN, and the NASA-Ames version of the CASA model. These models included similar components (soil physics, decomposition, plant growth, and nitrogen transformations), but in some cases used very different algorithms for these processes. All models generated similar results for the general cycling of nitrogen through the agro-ecosystems, but simulated nitrogen trace gas fluxes were quite different. In most cases the simulated N20 fluxes were within a factor of about 2 of the observed annual fluxes, but even when models produced similar N2O fluxes they often produced very different estimates of gaseous N loss as nitric oxide (NO), dinitrogen (N2), and ammonia (NH3). Accurate simulation of soil moisture appears to be a key requirement for reliable simulation of N2O emissions. All models simulated the general pattern of low background fluxes with high fluxes following fertilization at the Scottish sites, but they could not (or were not designed to) accurately capture the observed effects of different fertilizer types on N2O flux. None of the models were able to reliably generate large pulses of N2O during brief winter thaws that were observed at the two German sites. All models except DNDC simulated very low N2O fluxes for the dry site in Colorado. The US Trace Gas Network (TRAGNET) has provided a mechanism for this model and site intercomparison. Additional intercomparisons are needed with these and other models and additional data sets; these should include both tropical agro-ecosystems and new agricultural management techniques designed for sustainability.

Frolking, S. E.↗

Heuristic Area Cost Estimation for Observational Coverage Schedulers

This paper presents a comparison of heuris- tics used to estimate the amount of time it would take for a spacecraft to image an area using Boustrophedon decomposition (Choset and Pignon 1998). Machine learning tech- niques are used to characterize algorithmic performance of coverage algorithms. It is shown that an ordinary least-squares linear model is among the most accurate in a set of constant and linear order regression models both in terms of memory consumption and schedule duration. These are demonstrated using the ASPEN planning system (Fukunaga et al. 1997) on the Eagle Eye domain.

Knight, Russell↗

Rolling Horizon with K-Position Search Method for Strategic Deconfliction of Package Delivery UAS

In this research, the strategic deconfliction of unmanned aircraft systems for an urban package delivery environment with two depots and multiple drop-off locations is studied. This research aims to formulate a mathematical model to compute both the departure sequence and scheduled time of departure for each unmanned aircraft system at a depot, considering temporal constraints at en-route crossing waypoints and depots for strategic deconfliction. However, the problem formulation results in an NP-hard mixed-integer nonlinear programming problem for the global optimal solution, so instead, a "rolling horizon with𝑘-position search"heuristic method is developed. The simulation studies show that an increase in the value of𝑘(the parameter used to determine the size of the local neighborhood) reduces the average ground delay at the cost of an increase in the computation time for a given problem size. The study also shows an order of magnitude increase in the maximum number of flights scheduled with the integration of rolling horizon (time decomposition) compared to those without the integration of rolling horizon in the heuristic algorithm for a given computation time cut off.

UTM↗

Collective neutrino oscillations on a quantum computer with hybrid quantum-classical algorithm

We simulate the time evolution of collective neutrino oscillations in two-flavor settings on a quantum computer. We explore the generalization of Trotter-Suzuki approximation to time-dependent Hamiltonian dynamics. The trotterization steps are further optimized using the Cartan decomposition of two-qubit unitary gates U ϵ SU(4) in the minimum number of controlled-NOT (CNOT) gates making the algorithm more resilient to the hardware noise. As a result, a more efficient hybrid quantum-classical algorithm is also explored to solve the problem on noisy intermediate-scale quantum devices.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗

Low-rank factorization of electron integral tensors and its application in electronic structure theory

In this letter, we introduce the reverse Cuthill-McKee (RCM) algorithm, which is often used for the bandwidth reduction of sparse tensors, to transform the two-electron integral tensors to their block diagonal forms. By further applying the pivoted Cholesky decomposition (CD) on each of the diagonal blocks, we are able to represent the high-dimensional two-electron integral tensors in terms of permutation matrices and low-rank Cholesky vectors. This representation facilitates the low-rank factorization of the high-dimensional tensor contractions that are usually encountered in post-Hartree-Fock calculations. In this letter, we discuss the second-order Møller-Plesset (MP2) method and linear coupled- cluster model with doubles (L-CCD) as two simple examples to demonstrate the efficiency of the RCM-CD technique in representing two-electron integrals in a compact form.

electronic structure theory↗

Paradeisos: A perfect hashing algorithm for many-body eigenvalue problems

Here, we describe an essentially perfect hashing algorithm for calculating the position of an element in an ordered list, appropriate for the construction and manipulation of many-body Hamiltonian, sparse matrices. Each element of the list corresponds to an integer value whose binary representation reflects the occupation of single-particle basis states for each element in the many-body Hilbert space. The algorithm replaces conventional methods, such as binary search, for locating the elements of the ordered list, eliminating the need to store the integer representation for each element, without increasing the computational complexity. Combined with the “checkerboard” decomposition of the Hamiltonian matrix for distribution over parallel computing environments, this leads to a substantial savings in aggregate memory. While the algorithm can be applied broadly to many-body, correlated problems, we demonstrate its utility in reducing total memory consumption for a series of fermionic single-band Hubbard model calculations on small clusters with progressively larger Hilbert space dimension.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Stochastic scheduling of generating units with weekly energy storage: A hybrid decomposition approach

We propose a solution method for the large-scale stochastic unit commitment (SUC) problem with weekly-dispatched energy storage and significant weather-dependent stochastic generating capacity. Weekly storage facilities that mostly charge during weekends and discharge during weekdays require a weekly scheduling of generating units, which result in a large-scale optimization problem. This SUC problem is formulated as a two-stage stochastic model and we use the conditional value-at-risk as a risk measure. Using a Benders framework, the proposed solution method decomposes the problem into a mixed-integer linear master problem and linear and continuous subproblems. The master problem corresponds to the first-stage decisions throughout the week and includes all the commitment (binary) variables and their corresponding constraints. The subproblems correspond to the actual dispatch of the generating units on a weekly basis. Based on the success of column-and-constraint generation algorithms to solve robust optimization problems, we improve the low communication between the master problem and the subproblems in the standard Benders decomposition by adding primal variables and constraints from the subproblems to the master problem, which provides a better approximation of the recourse function. Furthermore, our computational experiments demonstrate the effectiveness of the proposed decomposition method using an instance of the South Carolina synthetic system with 90 generating units under 40 scenarios.

25 ENERGY STORAGE↗

A Scalable Mixed-Integer Decomposition Method for Security-Constrained Optimal Power Flow with Complementarity Constraints

This project aimed to develop a scalable algorithm for security-constrained optimal power flow (SCOPF) under contingency scenarios. In particular, the SCOPF problem targeted in the GO Competition is challenging because of the nonconvexity, its nonsmoothness, and the problem size, which increases with the number of contingency events. Complementarity constraints imposed in post-contingency variables are particularly challenging because they lead to a violation of constraint qualifications at any feasible point.

97 MATHEMATICS AND COMPUTING↗

Noise suppression for dual-energy CT via penalized weighted least-square optimization with similarity-based regularization

Purpose: Dual-energy CT (DECT) expands applications of CT imaging in its capability to decompose CT images into material images. However, decomposition via direct matrix inversion leads to large noise amplification and limits quantitative use of DECT. Their group has previously developed a noise suppression algorithm via penalized weighted least-square optimization with edge-preservation regularization (PWLS-EPR). In this paper, the authors improve method performance using the same framework of penalized weighted least-square optimization but with similarity-based regularization (PWLS-SBR), which substantially enhances the quality of decomposed images by retaining a more uniform noise power spectrum (NPS). Methods: The design of PWLS-SBR is based on the fact that averaging pixels of similar materials gives a low-noise image. For each pixel, the authors calculate the similarity to other pixels in its neighborhood by comparing CT values. Using an empirical Gaussian model, the authors assign high/low similarity value to one neighboring pixel if its CT value is close/far to the CT value of the pixel of interest. These similarity values are organized in matrix form, such that multiplication of the similarity matrix to the image vector reduces image noise. The similarity matrices are calculated on both high- and low-energy CT images and averaged. In PWLS-SBR, the authors include a regularization term to minimize the L-2 norm of the difference between the images without and with noise suppression via similarity matrix multiplication. By using all pixel information of the initial CT images rather than just those lying on or near edges, PWLS-SBR is superior to the previously developed PWLS-EPR, as supported by comparison studies on phantoms and a head-and-neck patient. Results: On the line-pair slice of the Catphan{sup ©}600 phantom, PWLS-SBR outperforms PWLS-EPR and retains spatial resolution of 8 lp/cm, comparable to the original CT images, even at 90% reduction in noise standard deviation (STD). Similar performance on spatial resolution is observed on an anthropomorphic head phantom. In addition, results of PWLS-SBR show substantially improved image quality due to preservation of image NPS. On the Catphan{sup ©}600 phantom, NPS using PWLS-SBR has a correlation of 93% with that via direct matrix inversion, while the correlation drops to −52% for PWLS-EPR. Electron density measurement studies indicate high accuracy of PWLS-SBR. On seven different materials, the measured electron densities calculated from the decomposed material images using PWLS-SBR have a root-mean-square error (RMSE) of 1.20%, while the results of PWLS-EPR have a RMSE of 2.21%. In the study on a head-and-neck patient, PWLS-SBR is shown to reduce noise STD by a factor of 3 on material images with image qualities comparable to CT images, whereas fine structures are lost in the PWLS-EPR result. Additionally, PWLS-SBR better preserves low contrast on the tissue image. Conclusions: The authors propose improvements to the regularization term of an optimization framework which performs iterative image-domain decomposition for DECT with noise suppression. The regularization term avoids calculation of image gradient and is based on pixel similarity. The proposed method not only achieves a high decomposition accuracy, but also improves over the previous algorithm on NPS as well as spatial resolution.

60 APPLIED LIFE SCIENCES↗

Data Analysis with Graphical Models: Software Tools

Probabilistic graphical models (directed and undirected Markov fields, and combined in chain graphs) are used widely in expert systems, image processing and other areas as a framework for representing and reasoning with probabilities. They come with corresponding algorithms for performing probabilistic inference. This paper discusses an extension to these models by Spiegelhalter and Gilks, plates, used to graphically model the notion of a sample. This offers a graphical specification language for representing data analysis problems. When combined with general methods for statistical inference, this also offers a unifying framework for prototyping and/or generating data analysis algorithms from graphical specifications. This paper outlines the framework and then presents some basic tools for the task: a graphical version of the Pitman-Koopman Theorem for the exponential family, problem decomposition, and the calculation of exact Bayes factors. Other tools already developed, such as automatic differentiation, Gibbs sampling, and use of the EM algorithm, make this a broad basis for the generation of data analysis software.

Buntine, Wray L.↗

A Domain Decomposition Parallelization of the Fast Marching Method

In this paper, the first domain decomposition parallelization of the Fast Marching Method for level sets has been presented. Parallel speedup has been demonstrated in both the optimal and non-optimal domain decomposition case. The parallel performance of the proposed method is strongly dependent on load balancing separately the number of nodes on each side of the interface. A load imbalance of nodes on either side of the domain leads to an increase in communication and rollback operations. Furthermore, the amount of inter-domain communication can be reduced by aligning the inter-domain boundaries with the interface normal vectors. In the case of optimal load balancing and aligned inter-domain boundaries, the proposed parallel FMM algorithm is highly efficient, reaching efficiency factors of up to 0.98. Future work will focus on the extension of the proposed parallel algorithm to higher order accuracy. Also, to further enhance parallel performance, the coupling of the domain decomposition parallelization to the G(sub 0)-based parallelization will be investigated.

Herrmann, M.↗

A Parallel Ghosting Algorithm for The Flexible Distributed Mesh Database

Critical to the scalability of parallel adaptive simulations are parallel control functions including load balancing, reduced inter-process communication and optimal data decomposition. In distributed meshes, many mesh-based applications frequently access neighborhood information for computational purposes which must be transmitted efficiently to avoid parallel performance degradation when the neighbors are on different processors. This article presents a parallel algorithm of creating and deleting data copies, referred to as ghost copies, which localize neighborhood data for computation purposes while minimizing inter-process communication. The key characteristics of the algorithm are: (1) It can create ghost copies of any permissible topological order in a 1D, 2D or 3D mesh based on selected adjacencies. (2) It exploits neighborhood communication patterns during the ghost creation process thus eliminating all-to-all communication. (3) For applications that need neighbors of neighbors, the algorithm can create n number of ghost layers up to a point where the whole partitioned mesh can be ghosted. Strong and weak scaling results are presented for the IBM BG/P and Cray XE6 architectures up to a core count of 32,768 processors. The algorithm also leads to scalable results when used in a parallel super-convergent patch recovery error estimator, an application that frequently accesses neighborhood data to carry out computation.

Mubarak, Misbah↗

Asynchronous and Load-Balanced Union-Find for Distributed and Parallel Scientific Data Visualization and Analysis

We present a novel distributed union-find algorithm that features asynchronous parallelism and k-d tree based load balancing for scalable visualization and analysis of scientific data. Applications of union-find include level set extraction and critical point tracking, but distributed union-find can suffer from high synchronization costs and imbalanced workloads across parallel processes. In this study, we prove that global synchronizations in existing distributed union-find can be eliminated without changing final results, allowing overlapped communications and computations for scalable processing. We also use a k-d tree decomposition to redistribute inputs, in order to improve workload balancing. We benchmark the scalability of our algorithm with up to 1,024 processes using both synthetic and application data. Here, we demonstrate the use of our algorithm in critical point tracking and super-level set extraction with high-speed imaging experiments and fusion plasma simulations, respectively.

97 MATHEMATICS AND COMPUTING↗