Difference between revisions of "SC²S Colloquium - April 24, 2017"

From Sccswiki
Jump to navigation Jump to search
 
Line 11: Line 11:
  
 
== Severin Reiz: Black Box Hierarchical Approximations for SPD Matrices ==
 
== Severin Reiz: Black Box Hierarchical Approximations for SPD Matrices ==
N-body methods are vastly used in many disciplines: Simulations of gravity
+
We present a novel method that creates a hierarchical low-rank approximation, or compression, of an arbitrary dense symmetric positive definite (SPD) matrix. For many applications, our method enables an approximate matrix-vector multiplication in N log N or even N time, where N is the matrix size. Compression requires N log N storage and work.  In general, our scheme belongs to the family of hierarchical matrix approximation methods. In particular, it generalizes the fast multipole method (FMM) to a purely algebraic setting by only requiring the ability to sample matrix entries. Neither geometric information (i.e., point coordinates) nor knowledge of how the matrix entries have been generated is required,  thus the term black box. Also, we introduce a shared-memory parallel scheme for hierarchical matrix computations that reduces synchronization barriers. We present results on the Intel Knights Landing and Haswell architectures, and on the NVIDIA Pascal architecture for a variety of matrices.
and coulomb-potentials, waves and scattering or fluids and transport; in data
 
analysis the same problem occurs in machine learning, geostatistics and image
 
analysis. A common approach is a far-field approximation by Barnes-Hut and
 
the Fast Multipole Method. In most codes hierarchical domain decomposition is
 
based on geometric distances in the original space. In this project we derived
 
a geometry-oblivious partitioning scheme for SPD matrices from various problem
 
domains. This leads to hierarchical low rank plus sparse matrices - an algebraic
 
generalization from previously mentioned N-body methods. A parallel treecode is
 
developed for a black box fast approximate matrix multiplication.
 
  
 
== Jeeta Ann Chacko: Shallow Water Equation Simulation with Sparse Grid Combination Technique ==
 
== Jeeta Ann Chacko: Shallow Water Equation Simulation with Sparse Grid Combination Technique ==

Latest revision as of 17:58, 19 April 2017

Date: April 24, 2017
Room: 02.07.023
Time: 2:30 pm, s.t.


Severin Reiz: Black Box Hierarchical Approximations for SPD Matrices

We present a novel method that creates a hierarchical low-rank approximation, or compression, of an arbitrary dense symmetric positive definite (SPD) matrix. For many applications, our method enables an approximate matrix-vector multiplication in N log N or even N time, where N is the matrix size. Compression requires N log N storage and work. In general, our scheme belongs to the family of hierarchical matrix approximation methods. In particular, it generalizes the fast multipole method (FMM) to a purely algebraic setting by only requiring the ability to sample matrix entries. Neither geometric information (i.e., point coordinates) nor knowledge of how the matrix entries have been generated is required, thus the term black box. Also, we introduce a shared-memory parallel scheme for hierarchical matrix computations that reduces synchronization barriers. We present results on the Intel Knights Landing and Haswell architectures, and on the NVIDIA Pascal architecture for a variety of matrices.

Jeeta Ann Chacko: Shallow Water Equation Simulation with Sparse Grid Combination Technique

Scientific applications are affected by the curse of dimensionality. Sparse grids can be used to reduce grid points drastically but they are difficult to parallelize. The sparse grid combination technique can be used to combine lower resolution anisotropic Cartesian grids to generate a sparse grid instead of directly using sparse grids. The shallow water equation is a hyperbolic PDE that is used to describe the changes in height and horizontal velocities of a fluid. The shallow water equation simulation is implemented using the sparse grid combination technique as a parallelization scheme in this project. The solution is compared with an existing implementation of shallow water equation simulation to evaluate the accuracy.

Robert Schweizer: Parallel Implementation of a Compact Difference Scheme in a Computational Fluid Dynamics Code

Compact difference schemes have promising numerical properties for turbulent flow simulations compared to explicit finite difference schemes. However, they require the solution of a narrow-banded implicit system. The efficient parallelization of this is difficult, which has generally prevented the application of compact schemes for large-scale simulations. In this work, an efficient solver for regular grids distributed on many MPI processes is implemented. It uses a substructuring scheme combined with a block-Jacobi iterative solver for the resulting reduced system. Together with performance optimizations such as efficient vectorization across multiple RHS vectors, the final implementation is included in a CFD code. Better overall performance of the compact schemes is observed in example DNS simulations.