@article {,
	title = {Sparse matrix-vector and matrix-multivector products for the truncated SVD on graphics processors},
	journal = {Concurrency and Computation: Practice and Experience},
	year = {2023},
	month = {2023-08},
	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{\textendash}Kahan{\textendash}Lanczos algorithm.},
	keywords = {graphics processing units, Singular value decomposition, sparse matrix-multivector product, sparse matrix-vector product},
	issn = {1532-0626},
	doi = {10.1002/cpe.7871},
	url = {https://onlinelibrary.wiley.com/doi/pdf/10.1002/cpe.7871},
	author = {Jos{\'e} I. Aliaga and Hartwig Anzt and Enrique S. Quintana-Orti and Andres E. Thomas}
}
@article {1466,
	title = {Reducing the Amount of out-of-core Data Access for GPU-Accelerated Randomized SVD},
	journal = {Concurrency and Computation: Practice and Experience},
	year = {2020},
	month = {2020-04},
	keywords = {Divide and conquer, gpu, out-of-core computation, Singular value decomposition},
	doi = { https://doi.org/10.1002/cpe.5754},
	author = {Yuechao Lu and Ichitaro Yamazaki and Fumihiko Ino and Yasuyuki Matsushita and Stanimire Tomov and Jack Dongarra}
}
@article {1161,
	title = {Accelerating the SVD Two Stage Bidiagonal Reduction and Divide and Conquer Using GPUs},
	journal = {Parallel Computing},
	volume = {74},
	year = {2018},
	month = {2018-05},
	pages = {3{\textendash}18},
	abstract = {The increasing gap between memory bandwidth and computation speed motivates the choice of algorithms to take full advantage of today{\textquoteright}s high performance computers. For dense matrices, the classic algorithm for the singular value decomposition (SVD) uses a one stage reduction to bidiagonal form, which is limited in performance by the memory bandwidth. To overcome this limitation, a two stage reduction to bidiagonal has been gaining popularity. It first reduces the matrix to band form using high performance Level 3 BLAS, then reduces the band matrix to bidiagonal form. As accelerators such as GPUs and co-processors are becoming increasingly widespread in high-performance computing, a question of great interest to many SVD users is how much the employment of a two stage reduction, as well as other current best practices in GPU computing, can accelerate this important routine. To fulfill this interest, we have developed an accelerated SVD employing a two stage reduction to bidiagonal and a number of other algorithms that are highly optimized for GPUs. Notably, we also parallelize and accelerate the divide and conquer algorithm used to solve the subsequent bidiagonal SVD. By accelerating all phases of the SVD algorithm, we provide a significant speedup compared to existing multi-core and GPU-based SVD implementations. In particular, using a P100 GPU, we illustrate a performance of up to 804 Gflop/s in double precision arithmetic to compute the full SVD of a 20k {\texttimes} 20k matrix in 90 seconds, which is 8.9 {\texttimes}  faster than MKL on two 10 core Intel Haswell E5-2650 v3 CPUs, 3.7 {\texttimes}  over the multi-core PLASMA two stage version, and 2.6 {\texttimes}  over the previously accelerated one stage MAGMA version.},
	keywords = {2-stage, accelerator, Divide and conquer, gpu, Singular value decomposition, SVD},
	issn = {01678191},
	doi = {10.1016/j.parco.2017.10.004},
	url = {https://www.sciencedirect.com/science/article/pii/S0167819117301758},
	author = {Mark Gates and Stanimire Tomov and Jack Dongarra}
}
@article {1258,
	title = {The Singular Value Decomposition: Anatomy of Optimizing an Algorithm for Extreme Scale},
	journal = {SIAM Review},
	volume = {60},
	year = {2018},
	month = {2018-11},
	pages = {808{\textendash}865},
	abstract = {The computation of the singular value decomposition, or SVD, has a long history with many improvements over the years, both in its implementations and algorithmically. Here, we survey the evolution of SVD algorithms for dense matrices, discussing the motivation and performance impacts of changes. There are two main branches of dense SVD methods: bidiagonalization and Jacobi. Bidiagonalization methods started with the implementation by Golub and Reinsch in Algol60, which was subsequently ported to Fortran in the EISPACK library, and was later more efficiently implemented in the LINPACK library, targeting contemporary vector machines. To address cache-based memory hierarchies, the SVD algorithm was reformulated to use Level 3 BLAS in the LAPACK library. To address new architectures, ScaLAPACK was introduced to take advantage of distributed computing, and MAGMA was developed for accelerators such as GPUs. Algorithmically, the divide and conquer and MRRR algorithms were developed to reduce the number of operations. Still, these methods remained memory bound, so two-stage algorithms were developed to reduce memory operations and increase the computational intensity, with efficient implementations in PLASMA, DPLASMA, and MAGMA. Jacobi methods started with the two-sided method of Kogbetliantz and the one-sided method of Hestenes. They have likewise had many developments, including parallel and block versions and preconditioning to improve convergence. In this paper, we investigate the impact of these changes by testing various historical and current implementations on a common, modern multicore machine and a distributed computing platform. We show that algorithmic and implementation improvements have increased the speed of the SVD by several orders of magnitude, while using up to 40 times less energy.},
	keywords = {bidiagonal matrix, bisection, Divide and conquer, Hestenes method, Jacobi method, Kogbetliantz method, MRRR, QR iteration, Singular value decomposition, SVD},
	issn = {0036-1445},
	doi = {10.1137/17M1117732},
	url = {https://epubs.siam.org/doi/10.1137/17M1117732},
	author = {Jack Dongarra and Mark Gates and Azzam Haidar and Jakub Kurzak and Piotr Luszczek and Stanimire Tomov and Ichitaro Yamazaki}
}
