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

A New One-side Jacobi Based on Dynamic Ordering

作　　者：郭强[1] 赵雷[1] 

机构地区：[1]苏州大学计算机科学与技术学院,江苏苏州215006

出　　处：《苏州大学学报（工科版）》2011年第4期16-22,共7页Journal of Soochow University Engineering Science Edition (Bimonthly)

基　　金：国家自然科学基金资助项目(编号61073061)

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

关 键 词：单边Jacobi算法 奇异值分解 谱范数 动态序列 最大权完美匹配 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]