2025/12/04 by Zhen Hu, Hu, Zhen, Dongliang Xiong +7
Computer Science · Engineering · #Distributed #FOS: Computer and information sciences #Interconnection Networks and Systems #Low-power high-performance VLSI design #Parallel #Parallel Computing and Optimization Techniques #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2512.04389
openalex publication_date 2025/12/04 · openalex created_date 2025/12/06 · openalex updated_date 2026/07/28
In sparse LU factorization, nonzero elements after symbolic factorization tend to distribute in diagonal and right-bottom region of sparse matrices. However, regular 2D blocking on this non-uniform distribution structure may lead to workload imbalance across blocks. Besides, existing matrix features fail to guide us effectively in blocking. In this paper, we propose a structure-aware irregular blocking method for numerical factorization. A novel diagonal block-based feature is introduced to effectively characterize the local nonzero distribution of sparse matrices. Based on this, we further propose an irregular blocking method that adjusts block sizes according to the local distribution of nonzeros. The strategy utilizes fine-grained blocks in dense regions and coarse-grained blocks in sparse regions, adequately balancing the nonzeros of blocks both within the same level and across levels in the dependency tree. Experiments demonstrate that, on a single NVIDIA A100 GPU, our proposed irregular blocking method achieves average speedups of 1.50x and 3.32x over PanguLU and the latest SuperLUDIST, respectively. In addition, it achieves speedups of 1.40x and 3.84x over PanguLU and SuperLUDIST on 4 NVIDIA A100 GPUs.