KIT | KIT-Bibliothek | Impressum | Datenschutz

Sparse matrix‐vector and matrix‐multivector products for the truncated SVD on graphics processors

Aliaga, José I.; Anzt, Hartwig ORCID iD icon 1; Quintana-Ortí, Enrique S.; Tomás, Andrés E.
1 Scientific Computing Center (SCC), Karlsruher Institut für Technologie (KIT)

Abstract:

Many practical algorithms for numerical rank computations implement an iterative procedure that involves repeated multiplications of a vector, or a collection of vectors, with both a sparse matrix $A$ and its transpose. Unfortunately, the realization of these sparse products on current high performance libraries often deliver much lower arithmetic throughput when the matrix involved in the product is transposed. In this work, we propose a hybrid sparse matrix layout, named CSRC, that combines the flexibility of some well-known sparse formats to offer a number of appealing properties: (1) CSRC can be obtained at low cost from the popular CSR (compressed sparse row) format; (2) CSRC has similar storage requirements as CSR; and especially, (3) the implementation of the sparse product kernels delivers high performance for both the direct product and its transposed variant on modern graphics accelerators thanks to a significant reduction of atomic operations compared to a conventional implementation based on CSR. This solution thus renders considerably higher performance when integrated into an iterative algorithm for the truncated singular value decomposition (SVD), such as the randomized SVD or, as demonstrated in the experimental results, the block Golub–Kahan–Lanczos algorithm.


Verlagsausgabe §
DOI: 10.5445/IR/1000161524
Veröffentlicht am 21.08.2023
Originalveröffentlichung
DOI: 10.1002/cpe.7871
Scopus
Zitationen: 1
Web of Science
Zitationen: 1
Dimensions
Zitationen: 1
Cover der Publikation
Zugehörige Institution(en) am KIT Scientific Computing Center (SCC)
Publikationstyp Zeitschriftenaufsatz
Publikationsjahr 2023
Sprache Englisch
Identifikator ISSN: 1532-0626, 1040-3108, 1096-9128, 1532-0634
KITopen-ID: 1000161524
HGF-Programm 46.21.01 (POF IV, LK 01) Domain-Specific Simulation & SDLs and Research Groups
Erschienen in Concurrency and Computation: Practice and Experience
Verlag John Wiley and Sons
Band 35
Heft 28
Seiten Art.-Nr.: e7871
Vorab online veröffentlicht am 04.08.2023
Schlagwörter graphics processing units, singular value decomposition, sparse matrix-multivector product, sparse matrix-vector product
Nachgewiesen in Web of Science
Dimensions
Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page