Multi-Gpu Two-Dimensional Block-Cyclic Algorithm for Factorization of Dense Matrix

This article presents an efficient parallel algorithm for LU factorization of large dense matrices based on a two-dimensional block-cyclic data distribution designed for multi-GPU computing environments. The proposed methodology addresses key challenges of large-scale linear algebra computations, including load balancing, minimizing communication overhead, and maximizing computational locality. By distributing matrix blocks cyclically across a GPU process grid, the algorithm ensures uniform workload distribution even for very large problem sizes, thereby avoiding idle time and reducing synchronization delays. The implementation leverages state-of-the-art GPU computing technologies, including CUDA streams, cuBLAS and cuSolver libraries for local numerical kernels, and NCCL for high-performance collective communications using NVLink interconnects. A look-ahead scheduling strategy and overlapping of communication with computation further increase the degree of parallelism, enabling sustained high utilization of GPU resources throughout the factorization pipeline. A detailed theoretical performance model is developed to analyze speedup, scalability, communication costs, and the impact of block size on total execution time. Numerical experiments conducted on an 8-GPU node with NVIDIA RTX 2080 Ti GPUs demonstrate excellent strong scaling, achieving up to 95 % parallel efficiency for matrices of size up to N = 20,000. The results confirm that the proposed multi-GPU LU factorization approach closely approaches the theoretical performance limits and significantly outperforms traditional CPU-based and hybrid CPU–GPU schemes. The method is highly suitable for large-scale scientific and engineering applications requiring fast and robust solution of linear systems, including computational fluid dynamics, structural mechanics, numerical simulation of physical processes, and machine learning workloads. Future research directions include extensions to sparse matrices with adaptive load balancing, mixed-precision acceleration with error correction, and generalization to other matrix factorizations such as Cholesky, QR, and LDL?. Keywords: LU factorization, multi-GPU systems, block-cyclic data distribution, parallel computing, CUDA, cuBLAS, cuSolver, NCCL, high-performance computing, scalability.