计算Fiedler向量的一种高效准确方法  

An Efficient and Accurate Scheme for Computing the Fiedler Vector

作　　者：吴建平[1] 宋君强[1] 张卫民[1] 赵军[1] 

机构地区：[1]国防科学技术大学计算机学院,长沙410073

出　　处：《计算机学报》2013年第11期2266-2273,共8页Chinese Journal of Computers

基　　金：国家自然科学基金(60803039);国家"九七三"重点基础研究发展规划项目基金(2009CB723803);水利部公益性行业科研专项(201201053)资助~~

摘　　要：图的Fielder向量在许多应用领域扮演着重要角色,包括矩阵重排、图的分割、蛋白质分析、数据挖掘、机器学习与网络搜索等.但一般认为,计算Fiedler向量是很耗时的,因为其牵涉到特征值问题.文中提出了计算Fiedler向量的一种新方法,该方法基于收缩技术与反幂法,将Fiedler向量的计算转化为缩减矩阵最小特征值对应特征向量的计算.其次,引入了一种预条件方案来进一步减少计算量,在该方案中,可以采用任何一种针对线性方程组求解的预条件技术.对从UF稀疏矩阵集下载下来的几个稀疏矩阵对应的图,对新方法进行了实验,并与已知的最新方法进行了比较.实验中,采用了对角预条件,且对算法利用MPI和OpenMP混合编程来实现并行计算.实验结果表明,新方法相对于已有方法,在计算效率与计算精度上都具有优势.对图二分的应用实验也表明,在大多数情况下,文中算法给出的结果更好.The Fiedler vector of a graph plays a vital role in many applications, including matrix reordering, graph partitioning, protein analysis, data mining, machine learning, and web search. But it is usually regarded as very expensive in that it involves the solution of an eigenvalue problem. In this paper, we provide a new scheme to compute the Fiedler vector, based both on the shrink method and on the inverse power method. The computation of the Fiedler vector is reduced to that of the eigenvector related to the minimum eigenvalue of the reduced matrix. Further, a preconditioning method is introduced to reduce the computation cost. Any kind of known precon- ditioning technique for the solution of linear systems can be used in this method. For the graphs related to some of the sparse matrices downloaded from the UF Sparse Matrix Collection, the experiments are compared to the known novel schemes. In the experiments, diagonal scaling is used as the preconditioner and the algorithm is implemented with hybrid programming of MPI and OpenMP for parallel computing. The results show that the new scheme has the advantage both in efficiency and in accuracy. The application to graph bisection also shows that the equality is better than those with the known novel methods in most cases.

关 键 词：Fiedler向量 特征值问题 并行计算 稀疏线性方程组 共轭斜量法 预条件 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]