Parallel Sparse Approximate Inverse Preconditioning on Graphic Processing Units
Authors:
- 4 October 2012
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 24 (9) , 1852-1862
Abstract
Accelerating numerical algorithms for solving sparse linear systems on parallel architectures has attracted the attention of many researchers due to their applicability to many engineering and scientific problems. The solution of sparse systems often dominates the overall execution time of such problems and is mainly solved by iterative methods. Preconditioners are used to accelerate the convergence rate of these solvers and reduce the total execution time. Sparse approximate inverse (SAI) preconditioners are a popular class of preconditioners designed to improve the condition number of large sparse matrices. We propose a GPU accelerated SAI preconditioning technique called GSAI, which parallelizes the computation of this preconditioner on NVIDIA graphic cards. The preconditioner is then used to enhance the convergence rate of the BiConjugate Gradient Stabilized (BiCGStab) iterative solver on the GPU. The SAI preconditioner is generated on average 28 and 23 times faster on the NVIDIA GTX480 and TESLA M2070 graphic cards, respectively, compared to ParaSails (a popular implementation of SAI preconditioners on CPU) single processor/core results. The proposed GSAI technique computes the SAI preconditioner in approximately the same time as ParaSails generates the same preconditioner on 16 AMD Opteron 252 processors.Keywords
This publication has 35 references indexed in Scilit:
- Finite-Element Sparse Matrix Vector Multiplication on Graphic Processing UnitsIEEE Transactions on Magnetics, 2010
- 2. Basic Algorithms2006
- Structural properties of the graph of augmented sparse approximate inverses2002
- A Factored Approximate Inverse Preconditioner with PivotingSIAM Journal on Matrix Analysis and Applications, 2002
- A robust AINV-type method for constructing sparse approximate inverse preconditioners in factored formNumerical Linear Algebra with Applications, 2001
- Sparse Approximate Inverse Smoother for MultigridSIAM Journal on Matrix Analysis and Applications, 2000
- A comparative study of sparse approximate inverse preconditionersApplied Numerical Mathematics, 1999
- Toward an Effective Sparse Approximate Inverse PreconditionerSIAM Journal on Matrix Analysis and Applications, 1999
- A Sparse Approximate Inverse Preconditioner for Nonsymmetric Linear SystemsSIAM Journal on Scientific Computing, 1998
- Sparse approximate inverse preconditioning for dense linear systems arising in computational electromagneticsNumerical Algorithms, 1997