Speaker

Dimitar Lukarski, Karlsruhe Institute of Technology (KIT)

Contents

In this talk we consider parallel preconditioners in block form based on additive matrix splittings like e.g. Gauß-Seidel and SOR, and multiplicative decompositions like incomplete LU (ILU). In both scenarios, typically a large amount of forward and backward sweeps in triangular solvers needs to be performed. In order to harness parallelism within each block of the decomposition we use multi-coloring matrix reordering schemes. For splitting-based methods (Gauß-Seidel, SOR) and ILU(0) without fill-ins the original matrix pattern is preserved and therefore the matrix can be reorganized such that diagonal blocks are diagonal itself. Furthermore, we allow fill-ins in the ILU(p) method for achieving higher level of coupling with increased efficiency. Here, we consider two algorithms for parallelism. The level-scheduling method is used as a postprocessing method following the factorization. However, it produces very small blocks for many problem classes, i.e. the degree of parallelism is low. As a second approach, we propose a new method for anticipating the fill-in pattern of ILU(

) schemes which we call the

. This method computes the multi-coloring permutation

for the matrix |A|

whose occupancy pattern is a superset of our modified ILU(

) applied to

(A). As a result, this decomposition has no fill-ins into its diagonal blocks. This leads to an inherently parallel execution of triangular ILU(

) sweeps. In addition, we describe the integration of the preconditioners in the HiFlow

open-source finite element package that provides a portable software solution across diverse hardware platforms. On this basis, we conduct performance analysis across a variety of test problems on multi-core CPUs and GPU that proves efficiency, scalability and flexibility of our approach.

Time

Tuesday, 21 June 2011, 11:15

Venue

Jülich Supercomputing Centre, Besprechungsraum 1, building 16.3, room 107

Announcement as PDF