Algorithm 980: Sparse QR Factorization on the GPU Academic Article uri icon

abstract

  • Sparse matrix factorization involves a mix of regular and irregular computation, which is a particular challenge when trying to obtain high-performance on the highly parallel general-purpose computing cores available on graphics processing units (GPUs). We present a sparse multifrontal QR factorization method that meets this challenge and is significantly faster than a highly optimized method on a multicore CPU. Our method factorizes many frontal matrices in parallel and keeps all the data transmitted between frontal matrices on the GPU. A novel bucket scheduler algorithm extends the communication-avoiding QR factorization for dense matrices by exploiting more parallelism and by exploiting the staircase form present in the frontal matrices of a sparse multifrontal method.

published proceedings

  • ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE

author list (cited authors)

  • Yeralan, S. N., Davis, T. A., Sid-Lakhdar, W. M., & Ranka, S.

complete list of authors

  • Yeralan, Sencer Nuri||Davis, Timothy A||Sid-Lakhdar, Wissam M||Ranka, Sanjay

publication date

  • January 1, 2017 11:11 AM