New Dynamic Orderings for the Parallel One-Sided Block-Jacobi SVD Algorithm
New Dynamic Orderings for the Parallel One-Sided Block-Jacobi SVD Algorithm
复制标题
DOI：
10.1142/s0129626415500036
复制
发表时间：
2015-06-01
影响因子：
0.4
通讯作者：
Vajtersic, Marian
中科院分区：
文献类型：
--
作者：
Becka, Martin;Oksa, Gabriel;Vajtersic, Marian
针对平行的单侧块jacobi SVD算法提供了五个新的动态顺序的变体。与双面算法类似，动态排序考虑了矩阵的实际状态 - 与其相互正交性相对于其块列的时间。变体在计算和通信复杂性以及拟议的全球和局部停止标准方面有所不同。它们的性能在8192阶的正方形随机矩阵上进行了测试，并使用p = 16、32、64、96和128处理器进行单数值的随机分布。将动态排序的所有变体与平行循环排序，具有动态排序的双面块 - 雅各比方法以及Scalapack例程PDGESVD相对于收敛和总并行执行时间所需的并行迭代步骤的数量。此外，还讨论了计算的左单数矢量的正交性以及从计算单数三联体组装的矩阵中的相对误差。事实证明，在某些精确定义的意义上可以证明局部最优性的变体3是最有效的，它与变体2的结合是最有效的。对于相对较小的阻塞因子L = 2P，它们的表现要优于Scalapack过程PDGESVD，并且快的速度约为2倍。
Five variants of a new dynamic ordering are presented for the parallel one-sided block Jacobi SVD algorithm. Similarly to the two-sided algorithm, the dynamic ordering takes into account the actual status of a matrix-this time of its block columns with respect to their mutual orthogonality. Variants differ in the computational and communication complexities and in proposed global and local stopping criteria. Their performance is tested on a square random matrix of order 8192 with a random distribution of singular values using p = 16, 32, 64, 96 and 128 processors. All variants of dynamic ordering are compared with a parallel cyclic ordering, two-sided block-Jacobi method with dynamic ordering and the ScaLAPACK routine PDGESVD with respect to the number of parallel iteration steps needed for the convergence and total parallel execution time. Moreover, the relative errors in the orthogonality of computed left singular vectors and in the matrix assembled from computed singular triplets are also discussed. It turns out that the variant 3, for which a local optimality in some precisely defined sense can be proved, and its combination with variant 2, are the most efficient ones. For relatively small blocking factors l = 2p, they outperform the ScaLAPACK procedure PDGESVD and are about 2 times faster.