QA725 : QR and LU Decomposition on GPUs for High Performance
Thesis > Central Library of Shahrood University > Mathematical Sciences > MSc > 2026
Authors:
Abstarct:
Abstract
Matrix factorizations such as LU and QR are fundamental algorithms in numerical linear algebra and are widely used in solving systems of linear equations, least-squares problems, and large-scale scientific computations. As the size of computational problems increases, reducing execution time and effectively exploiting parallel architectures become increasingly important. This thesis investigates the computational performance of blocked implementations of the LU and QR factorizations on both central processing units (CPUs) and graphics processing units (GPUs), with particular emphasis on execution time and numerical accuracy.
For the LU factorization, a blocked algorithm with partial pivoting was employed, while the QR factorization was implemented using a blocked method baxsed on Householder transformations. The CPU-baxsed implementations were developed in MATLAB and compared with MATLAB’s built-in lu and qr functions. The experiments were performed on random square matrices with normally distributed entries in double precision. To reduce the effect of timing fluctuations, each experiment was repeated several times and the median execution time was used as the primary performance metric. The block sizes were also determined experimentally, with values of 1024 and 64 providing the best observed performance for the LU and QR factorizations, respectively.
The CPU results showed that, although the blocked implementations were slower than MATLAB’s highly optimized built-in routines, they achieved satisfactory numerical accuracy. The relative reconstruction error for the LU factorization remained approximately within the range of 10⁻¹⁵ to 10⁻¹³, while the reconstruction error for the QR factorization was on the order of 10⁻¹⁵ and the orthogonality error of the matrix Q was on the order of 10⁻¹⁷.
For the GPU-baxsed experiments, the performance of LAPACK, OpenMP, cuSOLVER, and a fully GPU-baxsed implementation was compared. The results demonstrated that, for the LU factorization, the advantage of using the GPU became more significant as the matrix size increased. For large matrices, the fully GPU-baxsed implementation achieved competitive performance and, in some cases, outperformed the other approaches. In contrast, for the QR factorization, the high computational cost of explicitly forming the orthogonal matrix Q led to a substantial increase in execution time and limited the efficiency of the fully GPU-baxsed implementation.
Overall, the results indicate that achieving high performance for matrix factorizations on...
Keywords:
#. Keeping place: Central Library of Shahrood University
Visitor:
Visitor: