Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “sparse matrices”

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 55 records · Page 3

A new look at the simultaneous analysis and design of structures

The minimum weight optimization of structural systems, subject to strength and displacement constraints as well as size side constraints, was investigated by the Simultaneous ANalysis and Design (SAND) approach. As an optimizer, the code NPSOL was used which is based on a sequential quadratic programming (SQP) algorithm. The structures were modeled by the finite element method. The finite element related input to NPSOL was automatically generated from the input decks of such standard FEM/optimization codes as NASTRAN or ASTROS, with the stiffness matrices, at present, extracted from the FEM code ANALYZE. In order to avoid ill-conditioned matrices that can be encountered when the global stiffness equations are used as additional nonlinear equality constraints in the SAND approach (with the displacements as additional variables), the matrix displacement method was applied. In this approach, the element stiffness equations are used as constraints instead of the global stiffness equations, in conjunction with the nodal force equilibrium equations. This approach adds the element forces as variables to the system. Since, for complex structures and the associated large and very sparce matrices, the execution times of the optimization code became excessive due to the large number of required constraint gradient evaluations, the Kreisselmeier-Steinhauser function approach was used to decrease the computational effort by reducing the nonlinear equality constraint system to essentially a single combined constraint equation. As the linear equality and inequality constraints require much less computational effort to evaluate, they were kept in their previous form to limit the complexity of the KS function evaluation. To date, the standard three-bar, ten-bar, and 72-bar trusses have been tested. For the standard SAND approach, correct results were obtained for all three trusses although convergence became slower for the 72-bar truss. When the matrix displacement method was used, correct results were still obtained, but the execution times became excessive due to the large number of constraint gradient evaluations required. Using the KS function, the computational effort dropped, but the optimization seemed to become less robust. The investigation of this phenomenon is continuing. As an alternate approach, the code MINOS for the optimization of sparse matrices can be applied to the problem in lieu of the Kreisselmeier-Steinhauser function. This investigation is underway.

Striz, Alfred G.↗

The Kokkos OpenMPTarget Backend: Implementation and Lessons Learned

As the supercomputing landscape diversifies, solutions such as Kokkos to write vendor agnostic applications and libraries have risen in popularity. Kokkos provides a programming model designed for performance portability, which allows developers to write a single source implementation that can run efficiently on various architectures. At its heart, Kokkos maps parallel algorithms to architecture and vendor specific backends written in lower level programming models such as CUDA and HIP. Another approach to writing vendor agnostic parallel code is using OpenMP’s directives based approach, which lets developers annotate code to express parallelism. It is implemented at the compiler level and is supported by all major high performance computing vendors, as well as the primary Open Source toolchains GNU and LLVM. Since its inception, Kokkos has used OpenMP to parallelize on CPU architectures. In this paper, we explore leveraging OpenMP for a GPU backend and discuss the challenges we encountered when mapping the Kokkos APIs and semantics to OpenMP target constructs. As an exemplar workload we chose a simple conjugate gradient solver for sparse matrices. We find that performance on NVIDIA and AMD GPUs varies widely based on details of the implementation strategy and the chosen compiler. Furthermore, the performance of the OpenMP implementations decreases with increasing complexity of the investigated algorithms.

Gayatri, Rahulkumar↗

A higher-order finite-element implementation of the nonlinear Fokker–Planck collision operator for charged particle collisions in a low density plasma

Collisions between particles in a low density plasma are described by the Fokker–Planck collision operator. In applications, this nonlinear integro-differential operator is often approximated by linearised or ad-hoc model operators due to computational cost and complexity. In this work, we present an implementation of the nonlinear Fokker–Planck collision operator written in terms of Rosenbluth potentials in the Rosenbluth–MacDonald–Judd (RMJ) form. The Rosenbluth potentials may be obtained either by direct integration or by solving partial differential equations (PDEs) similar to Poisson's equation: we optimise for performance and scalability by using sparse matrices to solve the relevant PDEs. We represent the distribution function using a tensor-product continuous-Galerkin finite-element representation and we derive and describe the implementation of the weak form of the collision operator. We present tests demonstrating a successful implementation using an explicit time integrator and we comment on the speed and accuracy of the operator. Finally, we speculate on the potential for applications in the current and next generation of kinetic plasma models.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

Non-asymptotic analysis of ensemble Kalman updates: effective dimension and localization

Many modern algorithms for inverse problems and data assimilation rely on ensemble Kalman updates to blend prior predictions with observed data. Ensemble Kalman methods often perform well with a small ensemble size, which is essential in applications where generating each particle is costly. This paper develops a non-asymptotic analysis of ensemble Kalman updates, which rigorously explains why a small ensemble size suffices if the prior covariance has moderate effective dimension due to fast spectrum decay or approximate sparsity. Here, we present our theory in a unified framework, comparing everal implementations of ensemble Kalman updates that use perturbed observations, square root filtering and localization. As part of our analysis, we develop new dimension-free covariance estimation bounds for approximately sparse matrices that may be of independent interest.

Mathematics↗

Spray: Sparse Reductions of Arrays in OPEN MP

We present SPRAY, an open-source header-only C++ library for sparse reductions of arrays. SPRAY is meant for applications in which a large array is collaboratively updated by multiple threads using an associative and commutative operation such as +=. Especially when each thread accesses only parts of the array, SPRAY can perform significantly better than OPENMP's built-in reduction clause or atomic updates, while also using less memory than the former. SPRAY provides both an easy-to-use interface that can serve as a drop-in replacement for OPENMP reductions and a selection of reducer objects that accumulate the final result in different thread-safe ways. We demonstrate SPRAY through multiple test cases including the LULESH shock hydrodynamics code and a transpose-matrix-vector multiplication for sparse matrices stored in CSR format. SPRAY reductions outperform built-in OPENMP reductions consistently, in some cases improving run time and memory overhead by 20X, and even beating domain-specific approaches such as Intel MKI, by over 2X in some cases. Furthermore, SPRAY reductions have a minimal impact on the code base, requiring only a few lines of source code changes. Once in place, SPRAY reduction schemes can be switched easily, allowing performance portability and tuning opportunities by separating performance-critical implementation details from application code.

OpenMP↗

Parallel String Graph Construction and Transitive Reduction for De Novo Genome Assembly

One of the most computationally intensive tasks in computational biology is de novo genome assembly, the decoding of the sequence of an unknown genome from redundant and erroneous short sequences. A common assembly paradigm identifies overlapping sequences, simplifies their layout, and creates consensus. Despite many algorithms developed in the literature, the efficient assembly of large genomes is still an open problem. In this work, we introduce new distributed-memory parallel algorithms for overlap detection and layout simplification steps of de novo genome assembly, and implement them in the diBELLA 2D pipeline. Our distributed memory algorithms for both overlap detection and layout simplification are based on linear-algebra operations over semirings using 2D distributed sparse matrices. Our layout step consists of performing a transitive reduction from the overlap graph to a string graph. We provide a detailed communication analysis of the main stages of our new algorithms. diBELLA 2D achieves near linear scaling with over 80% parallel efficiency for the human genome, reducing the runtime for overlap detection by 1.2-1.3× for the human genome and 1.5-1.9× for C.elegans compared to the state-of-the-art. Our transitive reduction algorithm outperforms an existing distributed-memory implementation by 10.5-13.3× for the human genome and 18-29× for the C. elegans. Our work paves the way for efficient de novo assembly of large genomes using long reads in distributed memory.

59 BASIC BIOLOGICAL SCIENCES↗

PLANC: Parallel Low-rank Approximation with Nonnegativity Constraints

In this work, we consider the problem of low-rank approximation of massive dense nonnegative tensor data, for example, to discover latent patterns in video and imaging applications. As the size of data sets grows, single workstations are hitting bottlenecks in both computation time and available memory. We propose a distributed-memory parallel computing solution to handle massive data sets, loading the input data across the memories of multiple nodes, and performing efficient and scalable parallel algorithms to compute the low-rank approximation. We present a software package called Parallel Low-rank Approximation with Nonnegativity Constraints, which implements our solution and allows for extension in terms of data (dense or sparse, matrices or tensors of any order), algorithm (e.g., from multiplicative updating techniques to alternating direction method of multipliers), and architecture (we exploit GPUs to accelerate the computation in this work). We describe our parallel distributions and algorithms, which are careful to avoid unnecessary communication and computation, show how to extend the software to include new algorithms and/or constraints, and report efficiency and scalability results for both synthetic and real-world data sets.

97 MATHEMATICS AND COMPUTING↗

A two-level GPU-accelerated incomplete LU preconditioner for general sparse linear systems

This paper presents a parallel preconditioning approach based on incomplete LU (ILU) factorizations in the framework of Domain Decomposition (DD) for general sparse linear systems. We focus on distributed memory parallel architectures, specifically, those that are equipped with graphic processing units (GPUs). In addition to block-Jacobi, we present general purpose two-level ILU Schur complement-based approaches, where different strategies are presented to solve the coarse-level reduced system. These strategies are combined with modified ILU methods in the construction of the coarse-level operator, in order to effectively remove smooth errors by targeting an algebraically smooth vector. We leverage available GPU-based sparse matrix kernels to accelerate the setup and the solve phases of the proposed ILU preconditioner. We evaluate the efficiency of the proposed methods as a smoother for algebraic multigrid (AMG) and as a preconditioner for Krylov subspace methods on challenging anisotropic diffusion problems and a collection of general sparse matrices.

97 MATHEMATICS AND COMPUTING↗

MFiX: Fractional-Step Method Implementation

A comprehensive, multiphase computational fluid dynamics (CFD) simulation solves several coupled transport equations including continuity, momentum, species, and energy. Chemical reactions further couple these equations through heats of reaction and rates of formation of products and rates of destruction of reactants. A fractional-step method separates changes attributed to chemical reactions from transport phenomena like convection and diffusion. When the governing equations are split into the transport and reacting components, efficient and independent methodologies can be exploited to solve the different systems. Specifically, discretization of field variable transport equations results in large, sparse matrices which are loosely coupled. These systems are solved in succession using iterative techniques that take advantage of the matrix structure. In contrast, chemical reactions tightly couple field variables locally within the domain (e.g., within a single computational cell) resulting in low dimensional but dense, nonlinear systems that are better solved using direct integration techniques.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Sorting and ordering sparse linear systems

Transformations of sparse linear systems by row-column permutations are considered and various algorithms are constructed to transform arbitrary symmetric positive definite sparse matrices, as well as matrices in band form, doubly bordered band form, and doubly bordered block diagonal form.

Tewarson, R. P.↗

Sparse matrix methods based on orthogonality and conjugacy

A matrix having a high percentage of zero elements is called spares. In the solution of systems of linear equations or linear least squares problems involving large sparse matrices, significant saving of computer cost can be achieved by taking advantage of the sparsity. The conjugate gradient algorithm and a set of related algorithms are described.

Lawson, C. L.↗

Elimination on sparse symmetric systems of a special structure.

Consideration of the problem of finding a permutation of rows and columns and an algorithm for solving ordered systems of linear algebraic equations with sparse matrices having a certain regular structure. Two approaches to the solution of this problem, in which the sparsity is used to some extent, are outlined. One of them is a very general approach where optimal (or nearly optimal) ordering is sought and the algorithm for solving the ordered system treats the matrix element by element to perform only necessary operations. The other approach involves the use of band matrices. After comparing these two approaches, a third approach is then suggested which involves the use of pipe matrices, and a means of ordering the rows and columns to obtain this type of matrix is presented. Examples of matrices reordered by the proposed procedure are cited.

Segethova, J.↗

Out-of-Core Solutions of Complex Sparse Linear Equations

ETCLIB is library of subroutines for obtaining out-of-core solutions of complex sparse linear equations. Routines apply to dense and sparse matrices too large to be stored in core. Useful for solving any set of linear equations, but particularly useful in cases where coefficient matrix has no special properties that guarantee convergence with any of interative processes. The only assumption made is that coefficient matrix is not singular.

Yip, E. L.↗

Multiprocessor sparse L/U decomposition with controlled fill-in

Generation of the maximal compatibles of pivot elements for a class of small sparse matrices is studied. The algorithm involves a binary tree search and has a complexity exponential in the order of the matrix. Different strategies for selection of a set of compatible pivots based on the Markowitz criterion are investigated. The competing issues of parallelism and fill-in generation are studied and results are provided. A technque for obtaining an ordered compatible set directly from the ordered incompatible table is given. This technique generates a set of compatible pivots with the property of generating few fills. A new hueristic algorithm is then proposed that combines the idea of an ordered compatible set with a limited binary tree search to generate several sets of compatible pivots in linear time. Finally, an elimination set to reduce the matrix is selected. Parameters are suggested to obtain a balance between parallelism and fill-ins. Results of applying the proposed algorithms on several large application matrices are presented and analyzed.

Alaghband, G.↗

Elimination sequence optimization for SPAR

SPAR is a large-scale computer program for finite element structural analysis. The program allows user specification of the order in which the joints of a structure are to be eliminated since this order can have significant influence over solution performance, in terms of both storage requirements and computer time. An efficient elimination sequence can improve performance by over 50% for some problems. Obtaining such sequences, however, requires the expertise of an experienced user and can take hours of tedious effort to affect. Thus, an automatic elimination sequence optimizer would enhance productivity by reducing the analysts' problem definition time and by lowering computer costs. Two possible methods for automating the elimination sequence specifications were examined. Several algorithms based on the graph theory representations of sparse matrices were studied with mixed results. Significant improvement in the program performance was achieved, but sequencing by an experienced user still yields substantially better results. The initial results provide encouraging evidence that the potential benefits of such an automatic sequencer would be well worth the effort.

Hogan, Harry A.↗

Numerical solution of large nonsymmetric eigenvalue problems

Several methods are discribed for combinations of Krylov subspace techniques, deflation procedures and preconditionings, for computing a small number of eigenvalues and eigenvectors or Schur vectors of large sparse matrices. The most effective techniques for solving realistic problems from applications are those methods based on some form of preconditioning and one of several Krylov subspace techniques, such as Arnoldi's method or Lanczos procedure. Two forms of preconditioning are considered: shift-and-invert and polynomial acceleration. The latter presents some advantages for parallel/vector processing but may be ineffective if eigenvalues inside the spectrum are sought. Some algorithmic details are provided that improve the reliability and effectiveness of these techniques.

Saad, Youcef↗