LEAN ALGEBRAIC MULTIGRID (LAMG): FAST GRAPH LAPLACIAN LINEAR SOLVER
LEAN ALGEBRAIC MULTIGRID (LAMG): FAST GRAPH LAPLACIAN LINEAR SOLVER
复制标题
DOI：
10.1137/110843563
复制
发表时间：
2012-01-01
影响因子：
3.1
通讯作者：
Brandt, Achi
中科院分区：
文献类型：
--
作者：
Livne, Oren E.;Brandt, Achi
图的拉普拉斯矩阵出现在大规模计算应用中，如半监督机器学习；图像、遗传数据和网页的光谱聚类；交通网络流量；电阻电路；椭圆型偏微分方程在非结构有限元网格上离散化。给出了对称线性系统Ax = b的一个精简代数多网格（lam）求解器，其中A是一个图拉普拉斯算子。经验证明，ram的运行时间和存储与边的数量呈线性增长。LAMG包括一个建立阶段和一个使用多网格循环的迭代求解阶段。在这个阶段，构建一系列越来越粗糙的拉普拉斯系统。在传统的多网格应用中，一般的图会带来算法上的挑战。LAMG结合了精益的分段常数插值、基于新的节点接近度量（亲和度）的明智节点聚合和粗级系统的能量校正。这将导致快速收敛、大量设置和内存节省。串行LAMG实现可以线性缩放3774个具有4700万条边的实际图，无需参数调优。LAMG比UMFPACK直接求解器和组合多重网格（CMG）更健壮，尽管CMG的平均速度比LAMG快。我们的方法可扩展到特征问题和其他图计算。
Laplacian matrices of graphs arise in large-scale computational applications such as semisupervised machine learning; spectral clustering of images, genetic data, and web pages; transportation network flows; electrical resistor circuits; and elliptic partial differential equations discretized on unstructured grids with finite elements. A lean algebraic multigrid (LAMG) solver of the symmetric linear system Ax = b is presented, where A is a graph Laplacian. LAMG's run time and storage are empirically demonstrated to scale linearly with the number of edges. LAMG consists of a setup phase, during which a sequence of increasingly coarser Laplacian systems is constructed, and an iterative solve phase using multigrid cycles. General graphs pose algorithmic challenges not encountered in traditional multigrid applications. LAMG combines a lean piecewise-constant interpolation, judicious node aggregation based on a new node proximity measure (the affinity), and an energy correction of coarse-level systems. This results in fast convergence and substantial setup and memory savings. A serial LAMG implementation scaled linearly for a diverse set of 3774 realworld graphs with up to 47 million edges, with no parameter tuning. LAMG was more robust than the UMFPACK direct solver and combinatorial multigrid (CMG), although CMG was faster than LAMG on average. Our methodology is extensible to eigenproblems and other graph computations.