On iterative QR pre-processing in the parallel block-Jacobi SVD algorithm

摘要

An efficient version of the parallel two-sided block-Jacobi algorithm for the singular value decomposition of an m × n matrix A includes the pre-processing step, which consists of the QR factorization of A with column pivoting followed by the optional LQ factorization of the R-factor. Then the iterative two-sided block-Jacobi algorithm is applied in parallel to the R-factor (or L-factor). For the efficient computation of the parallel QR (or LQ) factorization with (or without) column pivoting implemented in the ScaLAPACK, some matrix block cyclic distribution on a process grid r xc with p = r × c, r. c ≥ 1, and block size n_b × n_b is required so that all processors remain busy during the whole parallel QR (or LQ) factorization. Optimal values for parameters r, c and n_b are estimated experimentally using matrices of order n = 4000 and 8000, and the number of processors p = 8 and 16, respectively. It turns out that the optimal values are about n_b = 100 and r ≤ c with both r, c near to p~(1/2). These parameters are then used in numerical experiments for six various distributions of singular values combined with well- (k = 10~1) and ill-conditioned matrices (k = 10~8). It is shown that using optimal parameters in the pre-processing step, the parallel two-sided block-Jacobi SVD algorithm performs better (or equally well) than the ScaLAPACK routine PDGESVD for matrices with a multiple minimal/maximal singular value regardless to the condition number. For other distributions of singular values, our algorithm is slower than the ScaLAPACK. The un-pivoted QRLQ pre-processing step is then re-formulated and extended to the QR iteration, and its connection to the QR algorithm applied to specific symmetric, positive definite matrices is shown. This connection helps to explain observations in another set of experiments with a variable number of QR iteration steps. In general, the best results for all six distributions of singular values are achieved by using about six QR iteration steps in pre-processing.