Bilkent University
Department of Computer Engineering


A Parallel Sparse Solver and Its Relation to Graphs and Hypergraphs


Mustafa Gündoğan
MSc Student Student
Computer Engineering Department
Bilkent University

A solver for sparse linear systems is an important kernel in many areas of science and engineering. Typically sparse linear systems of equations arise from the discretization of partial differential equations (PDEs), while some sparse systems are not governed by PDEs. Even in the case that the coefficient matrix is dense, applications still require an effective preconditioner, which is often sparse. For solving large problems, one needs to resort to parallel computing in order to reduce the time to solution. Sparse algorithms are well-known for their poor utilization of the cache due to irregular memory access. In addition, traditional algorithms that are designed for sequential platforms usually have inherited limitations for parallelism. Therefore, there is a need for novel algorithms to work on today’s multicore clusters. Given a system of equations Ax = f, where A is large and sparse, it is known that hybrid solvers that contain both direct and iterative components are promising in terms of robustness and scalability on parallel computing platforms. In this study, we review the generalized parallel sparse DS factorization algorithm and its relationship to sparse graphs and hypergraphs.


DATE: 05 March, 2012, Monday @ 15:40