CAJ | 학술논문

图的Fielder向量在许多应用领域扮演着重要角色,包括矩阵重排、图的分割、蛋白质分析、数据挖掘、机器学习与网络搜索等.但一般认为,计算Fiedler向量是很耗时的,因为其牵涉到特征值问题.文中提出了计算Fiedler向量的一种新方法,该方法基于收缩技术与反幂法,将Fiedler向量的计算转化为缩减矩阵最小特征值对应特征向量的计算.其次,引入了一种预条件方案来进一步减少计算量,在该方案中,可以采用任何一种针对线性方程组求解的预条件技术.对从UF稀疏矩阵集下载下来的几个稀疏矩阵对应的图,对新方法进行了实验,并与已知的最新方法进行了比较.实验中,采用了对角预条件,且对算法利用MPI和OpenMP混合编程来实现并行计算.实验结果表明,新方法相对于已有方法,在计算效率与计算精度上都具有优势.对图二分的应用实验也表明,在大多数情况下,文中算法给出的结果更好.
도적Fielder향량재허다응용영역분연착중요각색,포괄구진중배、도적분할、단백질분석、수거알굴、궤기학습여망락수색등.단일반인위,계산Fiedler향량시흔모시적,인위기견섭도특정치문제.문중제출료계산Fiedler향량적일충신방법,해방법기우수축기술여반멱법,장Fiedler향량적계산전화위축감구진최소특정치대응특정향량적계산.기차,인입료일충예조건방안래진일보감소계산량,재해방안중,가이채용임하일충침대선성방정조구해적예조건기술.대종UF희소구진집하재하래적궤개희소구진대응적도,대신방법진행료실험,병여이지적최신방법진행료비교.실험중,채용료대각예조건,차대산법이용MPI화OpenMP혼합편정래실현병행계산.실험결과표명,신방법상대우이유방법,재계산효솔여계산정도상도구유우세.대도이분적응용실험야표명,재대다수정황하,문중산법급출적결과경호.