Parallel one-sided Block-Jacobi SVD algorithm

Abstract

A new dynamic ordering is presented for the parallel one-sided block Jacobi SVD algorithm. Similarly to the two-sided variant, which has been analyzed and implemented in last 10 years, the dynamic ordering takes into account the actual status of a matrix—this time of its block columns with respect to their mutual orthogonality. Using p processors, in each parallel iteration step the p mostly inclined pairs of block columns are made orthogonal, whereby their inclination is measured by an estimation of principal angles between subspaces generated by those block columns. It is shown that principal angles can be estimated using a set of parallel Lanczos processes applied to special Wielandt-Jordan matrices. Only a limited number of iteration steps in each Lanczos process is needed for estimating a small number of smallest principal angles. Numerical experiments show that the proposed new parallel dynamic ordering can substantially decrease the number of parallel iteration steps needed for the convergence when compared to a parallel cyclic ordering. However, its more scalable implementation is desirable because currently it occupies a relatively high portion of the total parallel execution time.