We also analyze a scheme for reducing the memory usage of the algorithm by racalculating parts of the elimination tree. This may be necessary for three or higher-dimensional domains, as the amount of necessary memory grows very fast in those cases. This is done by processing the elimination tree in parts corresponding to slices of the computational domain. The results from the bottom of the elimination tree are erased after some elimination steps, preserving only the topmost matrix. This process is repeated for every part of the tree. The collection of the matrices obtained is solved using the same multi-frontal method.

The solver is implemented on the NVIDIA CUDA architecture and tested on a benchmark heat transfer problem. We present a comparison between the running times and memory usage for different domain dimensionalities between this solver and a state-of-the-art MUMPS solver [3]. We find that the memory usage of this algorithm is about one order of magnitude lower than of the MUMPS solver. The cost of this however is execution time which is an order of magnitude larger than for MUMPS. The current implementation uses home-made matrix operations as opposed to highly optimized BLAS routines in MUMPS, so a better speedup may be achieved by optimizing this implementation.

1

M. Paszynski, R. Schaefer, "Graph grammar-driven parallel partial differential equation solver", Concurrency and Computation, Practise and Experience, 22(9), 1063-1097, 2010. doi:10.1002/cpe.1533

2

P. Obrok, P. Pierzchala, A. Szymczak, M. Paszynski, "The grammar-based multi-thread multi-frontal parallel solver with trace theory-based scheduler", Procedia Computer Science, 1, 1987-1995, 2010. doi:10.1016/j.procs.2010.04.223

3

MUltifrontal Massively Parallel sparse direct Solver, http://graal.ens-lyon.fr/MUMPS/

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £85 +P&P)