Multifrontal Sparse Matrix Factorization on Graphics Processing Units
Robert F. Lucas, Gene Wagenbreth, John J. Tran, Dan M. Davis · 2012
For many finite element problems, when represented as sparse matrices, iterative solvers are found to be unreliable because they can impose com-putational bottlenecks. Early pioneering work by Duff et al, explored an alternative strategy called multifrontal sparse matrix factorization. This ap-proach, by representing the sparse problem as a tree of dense systems, maps well to modern memory hierarchies. Furthermore, it promotes the effective use of highly-tuned dense matrix arithmetic kernels, especially on novel and specialized hardware. The graphics processing units (GPUs) are architected differently than general-purpose hosts and offer an order of magnitude more processing power. This paper explores the hypothesis that GPUs can accel-erate the speed of a multifrontal linear solver, even when only processing a small number of the largest frontal matrices. We show that GPUs can more than double the throughput of the sparse matrix factorization. This, in turn, promises to offer a very cost-effective speedup to many science and engineer-