一种基于动态序列的单边Jacobi方法

采用Jacobi方法并行求解矩阵奇异值有多种数据交换序列,在双边Jacobi方法中,采用动态序列要比静态循环序列更加高效,可以将其应用到单边Jacobi方法中。为了在每一次迭代开始时动态生成数据交换序列,首先计算矩阵子块间的谱范数,然后对这些谱范数形成的完全图应用最大权完美匹配算法,最终结果作为各计算节点传递数据的依据。实验表明谱范数可以很好地表示矩阵列对之间的正交程度,将其应用在求解动态序列的过程中,使得单边Jacobi方法计算矩阵奇异值分解更加高效。

A New One-side Jacobi Based on Dynamic Ordering

There are many parallel Jacobi orderings proposed for computing the singular value decomposition of an m×n matrix A.Among them,the proposed dynamic ordering is much more efficient than its counterpart static cyclic orderings in the two-sided block-Jacobi.In this paper,we employ the dynamic ordering for the one-sided block-Jacobi algorithm.At the beginning of each iteration,the spectral norms of sub-blocks are calculated in parallel and constitute a complete edge-weighted graph,and then we apply the maximum-weight perfect matching algorithm to the graph to get the pairs of block columns around processors.The experiments show that spectral norms in the dynamic ordering is an effective tool for the one-sided block-Jacobi and the dynamic ordering is more efficient than the static cyclic ordering in the one-sided block-Jacobi method.