Anatomy of High-Performance Column-Pivoted QR Decomposition
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909670476611584 |
|---|---|
| author | Melnichenko, Maksim Murray, Riley Killian, William Demmel, James Mahoney, Michael W. Luszczek, Piotr Gates, Mark |
| author_facet | Melnichenko, Maksim Murray, Riley Killian, William Demmel, James Mahoney, Michael W. Luszczek, Piotr Gates, Mark |
| contents | We introduce an algorithmic framework for performing QR factorization with column pivoting (QRCP) on general matrices. The framework enables the design of practical QRCP algorithms through user-controlled choices for the core subroutines. We provide a comprehensive overview of how to navigate these choices on modern hardware platforms, offering detailed descriptions of alternative methods for both CPUs and GPUs. The practical QRCP algorithms developed within this framework are implemented as part of the open-source RandLAPACK library. Our empirical evaluation demonstrates that, on a dual AMD EPYC 9734 system, the proposed method achieves performance improvements of up to two orders of magnitude over LAPACK's standard QRCP routine and greatly surpasses the performance of the current state-of-the-art randomized QRCP algorithm. Additionally, on an NVIDIA H100 GPU, our method attains approximately 65 percent of the performance of cuSOLVER's unpivoted QR factorization. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_00976 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Anatomy of High-Performance Column-Pivoted QR Decomposition Melnichenko, Maksim Murray, Riley Killian, William Demmel, James Mahoney, Michael W. Luszczek, Piotr Gates, Mark Mathematical Software Numerical Analysis We introduce an algorithmic framework for performing QR factorization with column pivoting (QRCP) on general matrices. The framework enables the design of practical QRCP algorithms through user-controlled choices for the core subroutines. We provide a comprehensive overview of how to navigate these choices on modern hardware platforms, offering detailed descriptions of alternative methods for both CPUs and GPUs. The practical QRCP algorithms developed within this framework are implemented as part of the open-source RandLAPACK library. Our empirical evaluation demonstrates that, on a dual AMD EPYC 9734 system, the proposed method achieves performance improvements of up to two orders of magnitude over LAPACK's standard QRCP routine and greatly surpasses the performance of the current state-of-the-art randomized QRCP algorithm. Additionally, on an NVIDIA H100 GPU, our method attains approximately 65 percent of the performance of cuSOLVER's unpivoted QR factorization. |
| title | Anatomy of High-Performance Column-Pivoted QR Decomposition |
| topic | Mathematical Software Numerical Analysis |
| url | https://arxiv.org/abs/2507.00976 |