A Factored Sparse Approximate Inverse Preconditioned Conjugate Gradient Solver on Graphics Processing Units
Authors:
- Massimo BernaschiMBMassimo Bernaschi
- Mauro BissonMBMauro Bisson
- Carlo FantozziCarlo Fantozzi
- Carlo JannaCJCarlo Janna
- 1 January 2016
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific Computing
- Vol. 38 (1) , C53-C72
Abstract
Graphics Processing Units (GPUs) exhibit significantly higher peak performance than conventional CPUs. However, in general only highly parallel algorithms can exploit their potential. In this scenario, the iterative solution to sparse linear systems of equations could be carried out quite efficiently on a GPU as it requires only matrix-by-vector products, dot products, and vector updates. However, to be really effective, any iterative solver needs to be properly preconditioned and this represents a major bottleneck for a successful GPU implementation. Due to its inherent parallelism, the factored sparse approximate inverse (FSAI) preconditioner represents an optimal candidate for the conjugate gradient--like solution of sparse linear systems. However, its GPU implementation requires a nontrivial recasting of multiple computational steps. We present our GPU version of the FSAI preconditioner along with a set of results that show how a noticeable speedup with respect to a highly tuned CPU counterpart is obt...Keywords
This publication has 34 references indexed in Scilit:
- CUDA-enabled Sparse Matrix–Vector Multiplication on GPUs using atomic operationsParallel Computing, 2013
- Benchmarking of communication techniques for GPUsJournal of Parallel and Distributed Computing, 2013
- Parallel Sparse Approximate Inverse Preconditioning on Graphic Processing UnitsIEEE Transactions on Parallel and Distributed Systems, 2012
- Parallel preconditioned conjugate gradient algorithm on GPUJournal of Computational and Applied Mathematics, 2012
- Minimizing Communication in Numerical Linear AlgebraSIAM Journal on Matrix Analysis and Applications, 2011
- Sparse matrix solvers on the GPUACM Transactions on Graphics, 2003
- A Priori Sparsity Patterns for Parallel Sparse Approximate Inverse PreconditionersSIAM Journal on Scientific Computing, 2000
- A comparative study of sparse approximate inverse preconditionersApplied Numerical Mathematics, 1999
- Parallel Preconditioning with Sparse Approximate InversesSIAM Journal on Scientific Computing, 1997
- A Sparse Approximate Inverse Preconditioner for the Conjugate Gradient MethodSIAM Journal on Scientific Computing, 1996