UC Davis

Cholesky-based linear solvers are widely employed to solve large sparse positive semi-definite linear systems. Within the reordering, analyzing, factorizing, and solving pipeline, the reorder- ing of sparse matrices is a critical step in reducing non-zero fill-ins, thereby decreasing runtime and memory consumption. However, this stage remains the most time-consuming component of the linear solving process. There is currently a lack of GPU implementations specifically designed for matrix reordering in linear solving. This thesis proposes, to our knowledge, the first GPU-based nested dissection reordering algorithm. Our approach aims to achieve signif- icantly faster reordering times compared to traditional CPU-based methods while maintaining comparable quality in terms of non-zero fill-ins. We have implemented the proposed algorithm and conducted comprehensive performance comparisons with established CPU-based Nested Dissection implementations on various triangle mesh inputs. Our results demonstrate that the GPU-based reordering algorithm can achieve more than a 5 times speedup on average when applied to triangle mesh inputs. However, we produce an average of 6 times more non-zero ele- ments after Cholesky factorization compared to METIS, a widely-used graph partitioning soft- ware, based on our tests. Future work focuses on refining our partitioning strategy to achieve better fill-in reduction without sacrificing the significant speed advantages. Finally, we discuss the insights gained from our current implementation and outline future directions for further optimization and analysis.