Search NASA⌕ Search

SEARCH · Search NASA

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 505 records · Page 28

A Block-Based Triangle Counting Algorithm on Heterogeneous Environments

Triangle counting is a fundamental building block in graph algorithms. In this article, we propose a block-based triangle counting algorithm to reduce data movement during both sequential and parallel execution. Our block-based formulation makes the algorithm naturally suitable for heterogeneous architectures. The problem of partitioning the adjacency matrix of a graph is well-studied. Our task decomposition goes one step further: it partitions the set of triangles in the graph. By streaming these small tasks to compute resources, we can solve problems that do not fit on a device. We demonstrate the effectiveness of our approach by providing an implementation on a compute node with multiple sockets, cores and GPUs. The current state-of-the-art in triangle enumeration processes the Friendster graph in 2.1 seconds, not including data copy time between CPU and GPU. Using that metric, our approach is 20 percent faster. When copy times are included, our algorithm takes 3.2 seconds. This is 5.6 times faster than the fastest published CPU-only time.

97 MATHEMATICS AND COMPUTING↗

A Block-Based Triangle Counting Algorithm on Heterogeneous Environments

Triangle counting is a fundamental building block in graph algorithms. In this paper, we propose a block-based triangle counting algorithm to reduce data movement during both sequential and parallel execution. Our block-based formulation makes the algorithm naturally suitable for heterogeneous architectures. The problem of partitioning the adjacency matrix of a graph is well-studied. Our task decomposition goes one step further: it partitions the set of triangles in the graph. By streaming these small tasks to compute resources, we can solve problems that do not fit on a device. We demonstrate the effectiveness of our approach by providing an implementation on a compute node with multiple sockets, cores and GPUs. The current state-of-the-art in triangle enumeration processes the Friendster graph in 2.1 seconds, not including data copy time between CPU and GPU. Using that metric, our approach is 20 percent faster. When copy times are included, our algorithm takes 3.2 seconds. This is 5.6 times faster than the fastest published CPU-only time.

97 MATHEMATICS AND COMPUTING↗

Shape-constrained Input Estimation for Efficient Multi-shaker Vibration Testing

Multi-shaker vibration testing is gaining interest from structural dynamics test engineers as it can provide a much more accurate match to complicated field vibration responses than traditional single-axis shaker tests. However, the force capabilities of the small modal shakers typically used in multi-shaker vibration tests has limited the achievable response levels. To date, most multi-shaker vibration tests have been performed using a variety of standard, commercially-available control systems. While these control systems are adequate for a wide range of multiple-input/multiple-output tests, their control algorithms have not been tailored for the specific problem of multi-shaker vibration tests: efficiently coordinating the various shakers to work together to achieve a desired response. Here, a new input estimation algorithm is developed and demonstrated using simulations and actual test data. This algorithm, dubbed shape-constrained input estimation, is shown to effectively coordinate multiple shakers using a set of constraint vectors based on the deflection shapes of the test structure. This is accomplished by using the singular vector shapes of the system frequency response matrix, which allows the constraint vectors to automatically change as a function of frequency. Simulation and test results indicate a significant reduction in the input forces required to achieve a desired response. Finally, the results indicate that shape-constrained input estimation is an effective method to achieve higher response levels from limited shaker forces which will enable higher level multi-shaker vibration tests to be performed.

42 ENGINEERING↗

Writing the Programs of Programmable Catalysis

It has long been known that non-steady state and periodic catalytic reactor operation in terms of temperature, pressure, and composition can lead to higher overall productivity and/or product selectivity than the best steady operation. Recently, the emergence of catalysts whose intrinsic properties can be made to oscillate with time, introduces advanced forcing capabilities that can be “programmed” into the catalysts to broaden the scope and applicability of periodic operation to surface chemistry. In this work, an algorithmic approach is implemented to significantly accelerate the discovery and optimization of periodic steady states of catalytic reactors. Decomposition of complex dynamics into fundamental mechanistic fast–slow steps is seen to improve conceptual understanding of the relationship between binding energy oscillation protocols and overall catalytic rates. Finding structured forcing protocols, optimally tailored to the multiple time scales of a given individual mechanism, requires an efficient search of high-dimensional parameter spaces. Here, this is enabled here through active learning (Bayesian optimization, enhanced by our proposed Bayesian continuation). Implementation of these methods is shown to accelerate the evaluation of catalyst programs by up to several orders of magnitude. Faster screening of programmable catalysts to discover periodic steady states enables the optimization of catalytic operating protocols and thus opens the possibility for catalyst engineering based on optimal forcing programs to control rate and product selectivity, even for complex multistep catalytic mechanisms.

catalysis↗

The Reverse Cuthill-McKee Algorithm in Distributed-Memory

Ordering vertices of a graph is key to minimize fill-in and data structure size in sparse direct solvers, maximize locality in iterative solvers, and improve performance in graph algorithms. Except for naturally parallelizable ordering methods such as nested dissection, many important ordering methods have not been efficiently mapped to distributed-memory architectures. In this paper, we present the first-ever distributed-memory implementation of the reverse Cuthill-McKee (RCM) algorithm for reducing the profile of a sparse matrix. Our parallelization uses a two-dimensional sparse matrix decomposition. We achieve high performance by decomposing the problem into a small number of primitives and utilizing optimized implementations of these primitives. Our implementation shows strong scaling up to 1024 cores for smaller matrices and up to 4096 cores for larger matrices.

97 MATHEMATICS AND COMPUTING↗

MO-FG-204-01: Improved Noise Suppression for Dual-Energy CT Through Entropy Minimization

Purpose: In dual energy CT (DECT), noise amplification during signal decomposition significantly limits the utility of basis material images. Since clinically relevant objects contain a limited number of materials, we propose to suppress noise for DECT based on image entropy minimization. An adaptive weighting scheme is employed during noise suppression to improve decomposition accuracy with limited effect on spatial resolution and image texture preservation. Methods: From decomposed images, we first generate a 2D plot of scattered data points, using basis material densities as coordinates. Data points representing the same material generate a highly asymmetric cluster. We orient an axis by minimizing the entropy in a 1D histogram of these points projected onto the axis. To suppress noise, we replace pixel values of decomposed images with center-of-mass values in the direction perpendicular to the optimal axis. To limit errors due to cluster overlap, we weight each data point’s contribution based on its high and low energy CT values and location within the image. The proposed method’s performance is assessed on physical phantom studies. Electron density is used as the quality metric for decomposition accuracy. Our results are compared to those without noise suppression and with a recently developed iterative method. Results: The proposed method reduces noise standard deviations of the decomposed images by at least one order of magnitude. On the Catphan phantom, this method greatly preserves the spatial resolution and texture of the CT images and limits induced error in measured electron density to below 1.2%. In the head phantom study, the proposed method performs the best in retaining fine, intricate structures. Conclusion: The entropy minimization based algorithm with adaptive weighting substantially reduces DECT noise while preserving image spatial resolution and texture. Future investigations will include extensive investigations on material decomposition accuracy that go beyond the current electron density calculations. This work was supported in part by the National Institutes of Health (NIH) under Grant Number R21 EB012700.

60 APPLIED LIFE SCIENCES↗

Dual energy CT: How well can pseudo-monochromatic imaging reduce metal artifacts?

Purpose: Dual Energy CT (DECT) provides so-called monoenergetic images based on a linear combination of the original polychromatic images. At certain patient-specific energy levels, corresponding to certain patient- and slice-dependent linear combination weights, e.g., E = 160 keV corresponds to α = 1.57, a significant reduction of metal artifacts may be observed. The authors aimed at analyzing the method for its artifact reduction capabilities to identify its limitations. The results are compared with raw data-based processing. Methods: Clinical DECT uses a simplified version of monochromatic imaging by linearly combining the low and the high kV images and by assigning an energy to that linear combination. Those pseudo-monochromatic images can be used by radiologists to obtain images with reduced metal artifacts. The authors analyzed the underlying physics and carried out a series expansion of the polychromatic attenuation equations. The resulting nonlinear terms are responsible for the artifacts, but they are not linearly related between the low and the high kV scan: A linear combination of both images cannot eliminate the nonlinearities, it can only reduce their impact. Scattered radiation yields additional noncanceling nonlinearities. This method is compared to raw data-based artifact correction methods. To quantify the artifact reduction potential of pseudo-monochromatic images, they simulated the FORBILD abdomen phantom with metal implants, and they assessed patient data sets of a clinical dual source CT system (100, 140 kV Sn) containing artifacts induced by a highly concentrated contrast agent bolus and by metal. In each case, they manually selected an optimal α and compared it to a raw data-based material decomposition in case of simulation, to raw data-based material decomposition of inconsistent rays in case of the patient data set containing contrast agent, and to the frequency split normalized metal artifact reduction in case of the metal implant. For each case, the contrast-to-noise ratio (CNR) was assessed. Results: In the simulation, the pseudo-monochromatic images yielded acceptable artifact reduction results. However, the CNR in the artifact-reduced images was more than 60% lower than in the original polychromatic images. In contrast, the raw data-based material decomposition did not significantly reduce the CNR in the virtual monochromatic images. Regarding the patient data with beam hardening artifacts and with metal artifacts from small implants the pseudo-monochromatic method was able to reduce the artifacts, again with the downside of a significant CNR reduction. More intense metal artifacts, e.g., as those caused by an artificial hip joint, could not be suppressed. Conclusions: Pseudo-monochromatic imaging is able to reduce beam hardening, scatter, and metal artifacts in some cases but it cannot remove them. In all cases, the CNR is significantly reduced, thereby rendering the method questionable, unless special post processing algorithms are implemented to restore the high CNR from the original images (e.g., by using a frequency split technique). Raw data-based dual energy decomposition methods should be preferred, in particular, because the CNR penalty is almost negligible.

60 APPLIED LIFE SCIENCES↗

Quantum Solver Using Singular Value Decomposition for Computational Fluid Dynamics

Numerical solutions for fluid flow problems are challenging and have been focus of Computational Fluid Dynamics (CFD) research for past several decades. The advent of quantum computing promises exponential speedup in comparison to existing classical methods and alleviate computational constraints posed by CFD problems. Although solutions for most problems of interest in fluid dynamics using quantum computing are distant, recent advances in algorithms, software and hardware provide a path towards realizing this goal. Quantum linear solver algorithms (QLSA) such as Harrow–Hassidim–Lloyd (HHL) and Variational Quantum Linear Solver (VQLS) have been successfully implemented to solve for canonical problems such as Hele-Shaw flow. However, these algorithms still suffer to scale and address problems with ill-conditioned Jacobians. In the current paper, we alleviate these restrictions with a new quantum solver based on Singular Value Decomposition (SVD) and simulate flow past a 2D cylinder. The fidelity of the SVD based quantum solver in predicting the flow past 2D cylinder is computed along with an assessment of errors. Classical and quantum solutions for the flow are compared for different resolutions. Finally, we discuss variation in the solutions based on number of shots used.

Gottiparthi, Kalyan [ORNL] (ORCID:0000000213540255↗

Rigorous justification for the space–split sensitivity algorithm to compute linear response in Anosov systems

Ruelle gave a formula for linear response of transitive Anosov diffeomorphisms. Recently, practically computable realizations of Ruelle's formula have emerged that potentially enable sensitivity analysis of certain high-dimensional chaotic numerical simulations encountered in the applied sciences. In this paper, we provide full mathematical justification for the convergence of one such efficient computation, the space–split sensitivity, or S3, algorithm. In S3, Ruelle's formula is computed as a sum of two terms obtained by decomposing the perturbation vector field into a coboundary and a remainder that is parallel to the unstable direction. Such a decomposition results in a splitting of Ruelle's formula that is amenable to efficient computation. Here, we prove the existence of the S3 decomposition and the convergence of the computations of both resulting components of Ruelle's formula.

97 MATHEMATICS AND COMPUTING↗

Spatially quasi-periodic bifurcations from periodic traveling water waves and a method for detecting bifurcations using signed singular values

We present a method of detecting bifurcations by locating zeros of a signed version of the smallest singular value of the Jacobian. This enables the use of quadratically convergent root-bracketing techniques or Chebyshev interpolation to locate bifurcation points. Only positive singular values have to be computed, though the method relies on the existence of an analytic or smooth singular value decomposition (SVD). The sign of the determinant of the Jacobian, computed as part of the bidiagonal reduction in the SVD algorithm, eliminates slope discontinuities at the zeros of the smallest singular value. We use the method to search for spatially quasi-periodic traveling water waves that bifurcate from large-amplitude periodic waves. The water wave equations are formulated in a conformal mapping framework to facilitate the computation of the quasi-periodic Dirichlet-Neumann operator. We find examples of pure gravity waves with zero surface tension and overhanging gravity-capillary waves. In both cases, the waves have two spatial quasi-periods whose ratio is irrational. We follow the secondary branches via numerical continuation beyond the realm of linearization about solutions on the primary branch to obtain traveling water waves that extend over the real line with no two crests or troughs of exactly the same shape. The pure gravity wave problem is of relevance to ocean waves, where capillary effects can be neglected. Such waves can only exist through secondary bifurcation as they do not persist to zero amplitude. The gravity-capillary wave problem demonstrates the effectiveness of using the signed smallest singular value as a test function for multi-parameter bifurcation problems. This test function becomes mesh independent once the mesh is fine enough.

97 MATHEMATICS AND COMPUTING↗

Density-based Energy Decomposition Analysis for Intermolecular Interactions with Variationally Determined Intermediate State Energies

The first purely density-based energy decomposition analysis (EDA) for intermolecular binding is developed within the density functional theory. The most important feature of this scheme is to variationally determine the frozen density energy, based on a constrained search formalism and implemented with the Wu-Yang algorithm [Q. Wu and W. Yang, J. Chem. Phys. 118, 2498 (2003) ]. This variational process dispenses with the Heitler-London antisymmetrization of wave functions used in most previous methods and calculates the electrostatic and Pauli repulsion energies together without any distortion of the frozen density, an important fact that enables a clean separation of these two terms from the relaxation (i.e., polarization and charge transfer) terms. The new EDA also employs the constrained density functional theory approach [Q. Wu and T. Van Voorhis, Phys. Rev. A 72, 24502 (2005)] to separate out charge transfer effects. Because the charge transfer energy is based on the density flow in real space, it has a small basis set dependence. Applications of this decomposition to hydrogen bonding in the water dimer and the formamide dimer show that the frozen density energy dominates the binding in these systems, consistent with the noncovalent nature of the interactions. A more detailed examination reveals how the interplay of electrostatics and the Pauli repulsion determines the distance and angular dependence of these hydrogen bonds.

08 HYDROGEN↗

Graph-based modeling and simulation of complex systems

We present graph-based modeling abstractions to represent cyber-physical dependencies arising in complex systems. Specifically, we propose an algebraic graph abstraction to capture physical connectivity in complex optimization models and a computing graph abstraction to capture communication connectivity in computing architectures. The proposed abstractions are scalable and are used as the backbone of a Julia-based software package that we call Plasmo.j1. Here, we show how the algebraic graph abstraction facilitates the implementation, analysis, and decomposition of optimization problems and we show how the computing graph abstraction facilitates the implementation of optimization and control algorithms and their simulation in virtual environments that involve distributed, centralized, and hierarchical computing architectures.

97 MATHEMATICS AND COMPUTING↗

Cross-scale efficient tensor contractions for coupled cluster computations through multiple programming model backends

Coupled-cluster methods provide highly accurate models of molecular structure through explicit numerical calculation of tensors representing the correlation between electrons. These calculations are dominated by a sequence of tensor contractions, motivating the development of numerical libraries for such operations. While based on matrix–matrix multiplication, these libraries are specialized to exploit symmetries in the molecular structure and in electronic interactions, and thus reduce the size of the tensor representation and the complexity of contractions. The resulting algorithms are irregular and their parallelization has been previously achieved via the use of dynamic scheduling or specialized data decompositions. We introduce our efforts to extend the Libtensor framework to work in the distributed memory environment in a scalable and energy-efficient manner. We achieve up to 240× speedup compared with the optimized shared memory implementation of Libtensor. We attain scalability to hundreds of thousands of compute cores on three distributed-memory architectures (Cray XC30 and XC40, and IBM Blue Gene/Q), and on a heterogeneous GPU-CPU system (Cray XK7). As the bottlenecks shift from being compute-bound DGEMM's to communication-bound collectives as the size of the molecular system scales, we adopt two radically different parallelization approaches for handling load-imbalance, tasking and bulk synchronous models. Nevertheless, we preserve a unified interface to both programming models to maintain the productivity of computational quantum chemists.

97 MATHEMATICS AND COMPUTING↗

Quantum control landscape of bipartite systems

The control landscape of a quantum system A interacting with another quantum system B is studied. Only system A is accessible through time dependent controls, while system B is not accessible. The objective is to find controls that implement a desired unitary transformation on A, regardless of the evolution on B, at a sufficiently large final time. The freedom in the evolution on B is used to define an extended control landscape on which the critical points are investigated in terms of kinematic and dynamic gradients. A spectral decomposition of the corresponding extended unitary system simplifies the landscape analysis which provides: (i) a sufficient condition on the rank of the dynamic gradient of the extended landscape that guarantees a trap free search for the final time unitary matrix of system A, and (ii) a detailed decomposition of the components of the overall dynamic gradient matrix. Consequently, if the rank condition is satisfied, a gradient algorithm will find the controls that implements the target unitary on system A. It is shown that even if the dynamic gradient with respect to the controls alone is not full rank, the additional flexibility due to the parameters that define the extended landscape still can allow for the rank condition of the extended landscape to hold. Moreover, satisfaction of the latter rank condition subsumes any assumptions about controllability, reachability and control resources. Here satisfaction of the rank condition is taken as an assumption. The conditions which ensure that it holds remain an open research question. We lend some numerical support with two common examples for which the rank condition holds.

97 MATHEMATICS AND COMPUTING↗

Trapped-ion quantum simulation of collective neutrino oscillations

It is well known that the neutrino flavor in extreme astrophysical environments changes under the effect of three contributions: the vacuum oscillation, the interaction with the surrounding matter, and the collective oscillations due to interactions between different neutrinos. The latter adds a nonlinear contribution to the equations of motion, making the description of their dynamics complex. In this work we study various strategies to simulate the coherent collective oscillations of a system of N neutrinos in the two-flavor approximation using quantum computation. This was achieved by using a pair-neutrino decomposition designed to account for the fact that the flavor Hamiltonian, in the presence of the neutrino-neutrino term, presents an all-to-all interaction that makes the implementation of the evolution dependent on the qubit topology. We analyze the Trotter error caused by the decomposition demonstrating that the complexity of the implementation of time evolution scales polynomially with the number of neutrinos and that the noise from near-term quantum device simulation can be reduced by optimizing the quantum circuit decomposition and exploiting a full-qubit connectivity. We find that the gate complexity using second order Trotter-Suzuki formulas scales better with system size than with other decomposition methods such as quantum signal processing. In conclusion, we finally present the application and the results of our algorithm on a real quantum device based on trapped-ion qubits.

79 ASTRONOMY AND ASTROPHYSICS↗

Cross-scale Efficient Tensor Contractions for Coupled Cluster Computations Through Multiple Programming Model Backends

Coupled-cluster methods provide highly accurate models of molecular structure by explicit numerical calculation of tensors representing the correlation between electrons. These calculations are dominated by a sequence of tensor contractions, motivating the development of numerical libraries for such operations. While based on matrix-matrix multiplication, these libraries are specialized to exploit symmetries in the molecular structure and in electronic interactions, and thus reduce the size of the tensor representation and the complexity of contractions. The resulting algorithms are irregular and their parallelization has been previously achieved via the use of dynamic scheduling or specialized data decompositions. We introduce our efforts to extend the Libtensor framework to work in the distributed memory environment in a scalable and energy efficient manner. We achieve up to 240 speedup compared with the best optimized shared memory implementation. We attain scalability to hundreds of thousands of compute cores on three distributed-memory architectures, (Cray XC30&XC40, BlueGene/Q), and on a heterogeneous GPU-CPU system (Cray XK7). As the bottlenecks shift from being compute-bound DGEMM's to communication-bound collectives as the size of the molecular system scales, we adopt two radically different parallelization approaches for handling load-imbalance. Nevertheless, we preserve a uni ed interface to both programming models to maintain the productivity of computational quantum chemists.

74 ATOMIC AND MOLECULAR PHYSICS↗