SEARCH · Engineering Papers

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.

SourceResearch connectionFrom yearThrough year

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 271 records · Page 15

All sources NASA NTRS DOE OSTI

DOE OSTI2022

Final Technical Report for "Cloud-based Low-Scaling Quantum Chemistry Simulations for Materials"

The objective of phase I was to develop the basic infrastructure for performing efficient hybrid DFT calculations on solid materials with a turnaround time amenable to the use in large-scale data-driven approaches. To fulfill the goal we have developed a novel algorithm that significantly reduces the cost of exchange matrix formation. The algorithm does so by making use of three ingredients (a) interpolative decomposition of the electron integrals (b) robust pseudospectral method and (c) occ-RI approach. Our published work demonstrates that the algorithm is orders of magnitude faster than any other hybrid-DFT method and is on the order of only 3-4 times slower than pure DFT. All steps of the algorithm developed during phase I can be accelerated to the point that, for large enough systems, the diagonalization of the Fock matrix will become the most expensive step. To treat such large systems we have created an interface to the ASCR-funded PEXSI library. The PEXSI method is used to compute the density matrix directly from the Fock matrix in a manner that preserves the sparsity of the local representation.

Shiozaki, Toru↗

NASA NTRS1991

Algorithm For Solution Of Subset-Regression Problems

Reliable and flexible algorithm for solution of subset-regression problem performs QR decomposition with new column-pivoting strategy, enables selection of subset directly from originally defined regression parameters. This feature, in combination with number of extensions, makes algorithm very flexible for use in analysis of subset-regression problems in which parameters have physical meanings. Also extended to enable joint processing of columns contaminated by noise with those free of noise, without using scaling techniques.

Verhaegen, Michel↗

NASA NTRS1993

A simple parallel prefix algorithm for compact finite-difference schemes

A compact scheme is a discretization scheme that is advantageous in obtaining highly accurate solutions. However, the resulting systems from compact schemes are tridiagonal systems that are difficult to solve efficiently on parallel computers. Considering the almost symmetric Toeplitz structure, a parallel algorithm, simple parallel prefix (SPP), is proposed. The SPP algorithm requires less memory than the conventional LU decomposition and is highly efficient on parallel machines. It consists of a prefix communication pattern and AXPY operations. Both the computation and the communication can be truncated without degrading the accuracy when the system is diagonally dominant. A formal accuracy study was conducted to provide a simple truncation formula. Experimental results were measured on a MasPar MP-1 SIMD machine and on a Cray 2 vector machine. Experimental results show that the simple parallel prefix algorithm is a good algorithm for the compact scheme on high-performance computers.

Sun, Xian-He↗

DOE OSTI2024

A Local Macroscopic Conservative (LoMaC) Low Rank Tensor Method for the Vlasov Dynamics

Abstract In this paper, we propose a novel Local Macroscopic Conservative (LoMaC) low rank tensor method for simulating the Vlasov-Poisson (VP) system. The LoMaC property refers to the exact local conservation of macroscopic mass, momentum and energy at the discrete level. This is a follow-up work of our previous development of a conservative low rank tensor approach for Vlasov dynamics ( arXiv:2201.10397 ). In that work, we applied a low rank tensor method with a conservative singular value decomposition to the high dimensional VP system to mitigate the curse of dimensionality, while maintaining the local conservation of mass and momentum. However, energy conservation is not guaranteed, which is a critical property to avoid unphysical plasma self-heating or cooling. The new ingredient in the LoMaC low rank tensor algorithm is that we simultaneously evolve the macroscopic conservation laws of mass, momentum and energy using a flux-difference form with kinetic flux vector splitting; then the LoMaC property is realized by projecting the low rank kinetic solution onto a subspace that shares the same macroscopic observables by a conservative orthogonal projection. The algorithm is extended to the high dimensional problems by hierarchical Tuck decomposition of solution tensors and a corresponding conservative projection algorithm. Extensive numerical tests on the VP system are showcased for the algorithm’s efficacy.

Guo, Wei↗

NASA NTRS1995

A Parallel Prefix Algorithm for Almost Toeplitz Tridiagonal Systems

A compact scheme is a discretization scheme that is advantageous in obtaining highly accurate solutions. However, the resulting systems from compact schemes are tridiagonal systems that are difficult to solve efficiently on parallel computers. Considering the almost symmetric Toeplitz structure, a parallel algorithm, simple parallel prefix (SPP), is proposed. The SPP algorithm requires less memory than the conventional LU decomposition and is efficient on parallel machines. It consists of a prefix communication pattern and AXPY operations. Both the computation and the communication can be truncated without degrading the accuracy when the system is diagonally dominant. A formal accuracy study has been conducted to provide a simple truncation formula. Experimental results have been measured on a MasPar MP-1 SIMD machine and on a Cray 2 vector machine. Experimental results show that the simple parallel prefix algorithm is a good algorithm for symmetric, almost symmetric Toeplitz tridiagonal systems and for the compact scheme on high-performance computers.

Sun, Xian-He↗

DOE OSTI2022

A Scalable Space-Time Domain Decomposition Approach for Solving Large Scale Nonlinear Regularized Inverse Ill Posed Problems in 4D Variational Data Assimilation

We address the development of innovative algorithms designed to solve the strong-constraint Four Dimensional Variational Data Assimilation (4DVar DA) problems in large scale applications. We present a space-time decomposition approach which employs the whole domain decomposition, i.e. both along the spacial and temporal direction in the overlapping case, and the partitioning of both the solution and the operator. Starting from the global functional defined on the entire domain, we get to a sort of regularized local functionals on the set of sub domains providing the order reduction of both the predictive and the Data Assimilation models. The algorithm convergence is developed. Performance in terms of reduction of time complexity and algorithmic scalability is discussed on the Shallow Water Equations on the sphere. The number of state variables in the model, the number of observations in an assimilation cycle, as well as numerical parameters as the discretization step in time and in space domain are defined on the basis of discretization grid used by data available at repository Ocean Synthesis/Reanalysis Directory of Hamburg University.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2026

Rank-Limiting Strategies for Optimizing Tensor-Train Finite-Difference Time-Domain Simulations

We introduce rank-limiting strategies to optimize tensor-train decompositions for three-dimensional finite-difference time-domain simulations using the relationship between the tensors and their specific dimensionality. These include the use of hard caps on the inner ranks of the tensor train decomposition and the use of a group rounding algorithm taking into account all field components simultaneously. Here, several numerical examples are considered to verify the efficacy of the proposed optimization strategies.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

NASA NTRS1994

Preconditioned domain decomposition scheme for three-dimensional aerodynamic sensitivity analysis

A discrete sensitivity analysis algorithm had previously been developed and applied to two-dimensional aerodynamic optimization problems, where the computational domains were discretized by using single grids. The sparse, unsymmetric systems of linear equations resulting from this algorithm were solved by a direct matrix inversion matrix. However, for large two-dimensional problems and, practically, all three-dimensional problems, direct inversion methods become inapplicable, primarily due to the prohibitive computer storage needed. In an attempt to alleviate such hindrances, the sensitivity analysis with domain decomposition (SADD) scheme was developed. This scheme divides the computational domain into smaller and nonoverlapping subdomains (multiblock grids) that are solved separately. Then, the final solution is constructed from the subdomain solutions. As the number of grid points in the interface boundaries of the subdomains becomes large, the computer memory required to store the effective coefficient matrix of these interface points starts to increase. Presented in this Technical Note is a preconditioned iterative procedure to overcome this particular problem.

Eleshaky, Mohamed E.↗

DOE OSTI2024

Communication Lower Bounds and Optimal Algorithms for Multiple Tensor-Times-Matrix Computation

Multiple tensor-times-matrix (Multi-TTM) is a key computation in algorithms for computing and operating with the Tucker tensor decomposition, which is frequently used in multidimensional data analysis. Here, we establish communication lower bounds that determine how much data movement is required (under mild conditions) to perform the Multi-TTM computation in parallel. The crux of the proof relies on analytically solving a constrained, nonlinear optimization problem. We also present a parallel algorithm to perform this computation that organizes the processors into a logical grid with twice as many modes as the input tensor. We show that, with correct choices of grid dimensions, the communication cost of the algorithm attains the lower bounds and is therefore communication optimal. Finally, we show that our algorithm can significantly reduce communication compared to the straightforward approach of expressing the computation as a sequence of tensor-times-matrix operations when the input and output tensors vary greatly in size.

HBL-inequalities↗

NASA NTRS1988

A parallel householder tridiagonalization stratagem using scattered row decomposition

Householder's method for tridiagonalizing a real symmetric matrix, a major step in evaluating eigenvalues of the matrix, is modified into a parallel algorithm for a concurrent machine of message passing type. Each processor of the concurrent machine has its own CPU, communications control and local memory. Messages are passed through connections between processors. Although the basic algorithm is inherently serial, the computations can be spread over all processors by scattering different rows of the matrix into processors, hence the term 'Scattered Row Decomposition'. The steps in the serial and the parallel algorithms are identified. Expressions for efficiency and speedup are given in terms of problem and machine parameters. For a concurrent machine of ring type interconnection, a selected representative problem of large order exhibits efficiency approaching 66 per cent.

Chang, H. Y.↗

DOE OSTI2020

An adaptive discontinuous Petrov-Galerkin method for the Grad-Shafranov equation

In this work, we propose and develop an arbitrary-order adaptive discontinuous Petrov--Galerkin (DPG) method for the nonlinear Grad--Shafranov equation. An ultraweak formulation of the DPG scheme for the equation is given based on a minimal residual method. The DPG scheme has the advantage of providing more accurate gradients compared to conventional finite element methods, which is desired for numerical solutions to the Grad--Shafranov equation. The numerical scheme is augmented with an adaptive mesh refinement approach, and a criterion based on the residual norm in the minimal residual method is developed to achieve dynamic refinement. Nonlinear solvers for the resulting system are explored and a Picard iteration with Anderson acceleration is found to be efficient to solve the system. Finally, the proposed algorithm is implemented in parallel on MFEM using a domain-decomposition approach, and our implementation is general, supporting arbitrary order of accuracy and general meshes. Furthermore, numerical results are presented to demonstrate the efficiency and accuracy of the proposed algorithm.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2022

Weak Simulation v.1.0

SAND2022-3281 O Weak Simulation sparsifies the stabilizer decomposition of a qubit t-tensored T gate magic state to some additive error. It can accomplish this either by independent L1 sampling like in the popular SPARSIFY algorithm or with correlated L1 sampling, which offers a more efficient decomposition. Sandia National Laboratories is a multimission laboratory managed and operated by National Technology & Engineering Solutions of Sandia, LLC, a wholly owned subsidiary of Honeywell International Inc., for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-NA0003525.

SciDAC↗

DOE OSTI2020

Spatiotemporal parallelization of an analytical heat conduction model for additive manufacturing via a hybrid OpenMP + MPI approach

The ability to do thermal simulations for entire additive manufacturing builds is a key computational problem facing the additive manufacturing community; however, complex numerical models considering multiple physical phenomena currently do not have the capacity for simulations at this scale. To this end, conduction only analytic models offer a viable approach due to the massive drop in computational expense. In this work, we extend an existing implementation which uses a governing equation which can be evaluated at any point in space and time. This implementation already utilizes OpenMP with a spatial decompositions scheme stemming from a melt pool tracking algorithm. Furthermore, we then combine this with a parallel in time (PinT) approach to make the problem highly parallelizable. The new scheme, which uses MPI for internode communication and OpenMP for intranode communication, is shown to scale very well across multiple computational nodes. This approach results in the ability to simulate the 3D solidification conditions for entire layers of additively manufactured parts in minutes making part scale thermal simulations more practical.

36 MATERIALS SCIENCE↗

DOE OSTI2024

nuclear-score-maximization v1.0

This software library presents efficient and multithreaded implementations of matrix low rank approximation via column selection in C++17 code. The algorithms are described in Fornace, Mark, and Michael Lindsey. "Column and row subset selection using nuclear scores: algorithms and theory for Nystro m approximation, CUR decomposition, and graph Laplacian reduction." arXiv preprint arXiv:2407.01698 (2024). The presented methods are by-and-large ver novel, have provable approximation guarantees, multiple use-cases, and exhibit higher quality approximations on a variety of studied examples.

Fornace, Mark↗

DOE OSTI2024

Cold Plasma Measurements

We have continued the simulation campaign in support of our ongoing magnetospheric cold plasma research project. This project aims to develop the next-generation particle instruments to measure the properties of the cold particle populations in the Earth’s magnetosphere. For this purpose, simulations have been performed with a Particle-In-Cell (PIC) code called the Curvilinear PIC (CPIC). The code is formulated in curvilinear geometry and couples the standard PIC algorithm with algorithms for the generation and adaptation of the underlaying computational mesh. It conforms to complex objects like spacecraft and it can place more grid points in regions where higher resolution is needed. The code also features a scalable solver based on the multigrid algorithm and it is fully parallelized via domain decomposition and MPI.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

DOE OSTI2024

Bringing randomized algorithms to mainstream numerical linear algebra

Numerical linear algebra (NLA) underpins huge swaths of computational science and engineering. For scientists and engineers to make the most of the DOE’s computing resources, it is essential that they have access to high-performance implementations of algorithms with best-in-class scalability and reliability. Despite this, prevailing NLA libraries have little to no support for breakthrough algorithms from the field of randomized numerical linear algebra (RandNLA) that have been developed over the past twenty years. The goal of this LDRD was to break a log-jam that had prevented broad adoption of RandNLA. Our work had two thrusts. The first was to develop RandBLAS: a trustworthy and high-performance C++ library for randomized dimension reduction (an operation widely known as sketching). The second was the development of a novel randomized algorithm for computing a challenging type of matrix decomposition known as Householder QR with column pivoting (Householder QRCP). In this one-year late-start LDRD we successfully delivered RandBLAS 1.0 and new CPU and GPU codes for Householder QRCP. RandBLAS has extensive documentation at https://randblas.readthedocs.io/en/stable/. Papers on RandBLAS and and our high-performance QRCP codes are forthcoming.

97 MATHEMATICS AND COMPUTING↗

NASA NTRS1990

A collision-selection rule for a particle simulation method suited to vector computers

A theory is developed for a selection rule governing collisions in a particle simulation of rarefied gas-dynamic flows. The selection rule leads to an algorithmic form highly compatible with fine grain parallel decomposition, allowing for efficient utilization of supercomputers having vector or massively parallel single instruction multiple data architectures. A comparison of shock-wave profiles obtained using both the selection rule and Bird's direct simulation Monte Carlo (DSMC) method show excellent agreement. The equation on which the selection rule is based is shown to be directly related to the time-counter procedure in the DSMC method. The results of several example simulations of representative rarefied flows are presented, for which the number of particles used ranged from 10 to the 6th to 10 to the 7th demonstrating the greatly improved computational efficiency of the method.

Baganoff, D.↗

NASA NTRS1990

SIAM Conference on Parallel Processing for Scientific Computing, 4th, Chicago, IL, Dec. 11-13, 1989, Proceedings

Attention is given to such topics as an evaluation of block algorithm variants in LAPACK and presents a large-grain parallel sparse system solver, a multiprocessor method for the solution of the generalized Eigenvalue problem on an interval, and a parallel QR algorithm for iterative subspace methods on the CM2. A discussion of numerical methods includes the topics of asynchronous numerical solutions of PDEs on parallel computers, parallel homotopy curve tracking on a hypercube, and solving Navier-Stokes equations on the Cedar Multi-Cluster system. A section on differential equations includes a discussion of a six-color procedure for the parallel solution of elliptic systems using the finite quadtree structure, data parallel algorithms for the finite element method, and domain decomposition methods in aerodynamics. Topics dealing with massively parallel computing include hypercube vs. 2-dimensional meshes and massively parallel computation of conservation laws. Performance and tools are also discussed.

Dongarra, Jack↗