Research and ACM SRC Posters Archive

QR-Omega: Communication Avoiding 2.5D Householder QR


Poster Type: ACM SRC Posters

Author: Felipe Tomé (UFSCar, Massachusetts Institute of Technology (MIT)), Rabab Alomairy (King Abdullah University of Science and Technology (KAUST), Massachusetts Institute of Technology (MIT)), Alan Edelman (Massachusetts Institute of Technology (MIT)), Hermes Senger (USP, UFSCar)

Abstract: Orthogonalization is a key step in Krylov methods, tensor-network algorithms, least-squares solvers, and emerging machine-learning methods. Householder QR is numerically robust for orthogonalization, but on GPUs its performance is often limited by data movement and synchronization. We present QR-Ω, a hierarchical 2.5D Householder QR formulation that extends hierarchical QR with four execution operations: Split, Replicate, Combine, and Pipeline. These operations control how data is partitioned, replicated, reduced, and overlapped across the GPU memory hierarchy while preserving the Householder elimination order. On an NVIDIA H200, we compare QR-Ω with tuned cuSOLVER, MAGMA, and SLATE implementations in FP64, FP32, TF32, and 3×TF32. Across matrix sizes up to n = 131,072, QR-Ω approaches matrix-multiplication throughput while maintaining small numerical errors in FP64, FP32. Our implementation surpasses the state-of-the-art libraries cited above in performance by up to two times without loss of accuracy, while maintaining advantage in all tested sizes and precisions.

Best Poster Finalist (BP): no
Poster: PDF
Poster Summary: PDF


Back to Poster Archive Listing