A parallel, blocked, one-sided Hari–Zimmermann algorithm for the generalized singular value decomposition (GSVD) of a real or a complex matrix pair is here proposed, where F and G have the same number of columns, and are both of the full column rank. The algorithm targets either a single graphics processing unit (GPU), or a cluster of those, performs all non-trivial computation exclusively on the GPUs, requires the minimal amount of memory to be reasonably expected, scales acceptably with the increase of the number of GPUs available, and guarantees the reproducible, bitwise identical output of the runs repeated over the same input and with the same number of GPUs.
AlterOBrownPOBotsteinD (2003) Generalized singular value decomposition for comparative analysis of genome-scale expression data sets of two different organisms. Proceedings of the National Academy of Sciences of the United States of America100(6): 3351–3356.
2.
AndersonEBaiZBischofC, et al. (1999) LAPACK Users’ Guide. 3rd edn. Philadelphia, PA: Society for Industrial and Applied Mathematics. ISBN 0-89871-447-8 (paperback).
3.
ArafaYBadawyAAChennupatiG, et al. (2019) Low overhead instruction latency characterization for NVIDIA GPGPUs. In: 2019 IEEE High Performance Extreme Computing Conference (HPEC). Westin Hotel, Waltham, MA, USA, 24–26 September 2019, pp. 1–8. DOI:10.1109/HPEC.2019.8916466.
4.
BaiZ (1994) A parallel algorithm for computing the generalized singular value decomposition. Journal of Parallel and Distributed Computing20(3): 280–288.
5.
BojanczykAW (2003) An implicit Jacobi-like method for computing generalized hyperbolic SVD. Linear Algebra and Its Applications358(1): 293–307.
6.
BoukaramWHTurkiyyahGLtaiefH, et al. (2018) Batched QR and SVD algorithms on GPUs with applications in hierarchical matrix compression. Parallel Computing74: 19–33.
7.
CannonLE (1969) A Cellular Computer to Implement the Kalman Filter Algorithm. PhD Thesis, Montana State University, Bozeman, MT, USA.
8.
CempelC (2009) Generalized singular value decomposition in multidimensional condition monitoring of machines—a proposal of comparative diagnostics. Mechanical Systems and Signal Processing23(3): 701–711.
9.
DrmačZ (1997) Implementation of Jacobi rotations for accurate singular value computation in floating point arithmetic. SIAM Journal on Scientific Computing18(4): 1200–1222.
10.
GraillatSLauterCTangPTP, et al. (2015) Efficient calculations of faithfully rounded l2-norms of n-vectors. ACM Transactions on Mathematical Software41(4): 24.
11.
HammondJRSchäferALathamR (2014) To INT_MAX…and beyond! Exploring large-count support in MPI. In: 2014 Workshop on Exascale MPI at Supercomputing Conference. New Orleans, LA, USA, 17 November 2014, pp. 1–8. DOI:10.1109/ExaMPI.2014.5.
12.
HariV (1984) On Cyclic Jacobi Methods for the Positive Definite Generalized Eigenvalue Problem. PhD Thesis, FernUniversität–Gesamthochschule, Hagen, Germany.
HariV (2019) On the global convergence of the complex HZ method. SIAM Journal on Matrix Analysis and Applications40(4): 1291–1310.
15.
HariVSingerSSingerS (2010) Block-oriented J-Jacobi methods for Hermitian matrices. Linear Algebra and Its Applications433(8–10): 1491–1512.
16.
HariVSingerSSingerS (2014) Full block J-Jacobi method for Hermitian matrices. Linear Algebra and Its Applications444: 1–27.
17.
HowlandPJeonMParkH (2003) Structure preserving dimension reduction for clustered text data based on the generalized singular value decomposition. SIAM Journal on Matrix Analysis and Applications25(1): 165–179.
18.
HowlandPWangJParkH (2006) Solving the small sample size problem in face recognition using generalized discriminant analysis. Pattern Recognition39(2): 277–287.
19.
LukFT (1985) A parallel method for computing the generalized singular value decomposition. Journal of Parallel and Distributed Computing2(3): 250–260.
MaryTYamazakiIKurzakJ, et al. (2015) Performance of random sampling for computing low-rank approximations of a dense matrix on GPUs. In: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC ‘15). Austin, TX, USA, November 2015, pp. 1–11(art. no. 60). DOI:10.1145/2807591.2807613.
22.
Message Passing Interface Forum (2015) MPI: A Message-Passing Interface Standard, Version 3.1. High Performance Computing Center Stuttgart (HLRS).
23.
NovakovićV (2015) A hierarchically blocked Jacobi SVD algorithm for single and multiple graphics processing units. SIAM Journal on Scientific Computing37(1): C1–C30.
24.
NovakovićV (2017) Parallel Jacobi-type algorithms for the singular and the generalized singular value decomposition. PhD Thesis, University of Zagreb, Croatia. Available at: https://urn.nsk.hr/urn:nbn:hr:217:515320(accessed November 2020)
25.
NovakovićVSingerS (2011) A GPU-based hyperbolic SVD algorithm. BIT51(4): 1009–1030.
26.
NovakovićVSingerSSingerS (2015) Blocking and parallelization of the Hari–Zimmermann variant of the Falk–Langemeyer algorithm for the generalized SVD. Parallel Computing49: 136–152.
PaigeCCSaundersMA (1981) Towards a generalized singular value decomposition. SIAM Journal on Numerical Analysis18(3): 398–405.
29.
Quintana-OrtíGSunXBischofC (1998) A BLAS-3 version of the QR factorization with column pivoting. SIAM Journal on Scientific Computing19(5): 1486–1494.
30.
SenaratneDTellamburaC (2013) GSVD beamforming for two-user MIMO downlink channel. IEEE Transactions on Vehicular Technology62(6): 2596–2606.
31.
SingerSDi NapoliENovakovićV, et al. (2020) The LAPW method with eigendecomposition based on the Hari–Zimmermann generalized hyperbolic SVD. SIAM Journal on Scientific Computing42(5): C265–C293.
32.
SingerSSingerSNovakovićV, et al. (2012) Novel modifications of parallel Jacobi algorithms. Numerical Algorithms59: 1–27.
33.
SlapničarI (1998) Componentwise analysis of direct factorization of real symmetric and Hermitian matrices. Linear Algebra and Its Applications272: 227–275.
34.
TomovSDongarraJBaboulinM (2010) Towards dense linear algebra for hybrid GPU accelerated many core systems. Parallel Computing36(5–6): 232–240.
35.
Van LoanCF (1976) Generalizing the singular value decomposition. SIAM Journal on Numerical Analysis13(1): 76–83.
36.
ZhaoQRutkowskiTMZhangL, et al. (2010) Generalized optimal spatial filtering using a kernel approach with application to EEG classification. Cognitive Neurodynamics4(4): 355–358.
37.
ZhouMvan der VeenAJ (2017) Blind separation of partially overlapping data packets. Digital Signal Processing68: 154–166.
38.
ZimmermannK (1969) Zur Konvergenz eines Jacobiverfahren für gewönliche und verallgemeinerte Eigenwertprobleme. Dissertation no. 4305. Zürich, Switzerland: Eidgenössische Technische Hochschule.
Supplementary Material
Please find the following supplemental material available below.
For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.
For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.
