论文标题
具有光谱保证的图形数据的平行缩放
Parallel coarsening of graph data with spectral guarantees
论文作者
论文摘要
在科学计算，大规模图分区和几何网格的降低的领域，查找大图的粗略表示是一个重要的计算问题。在所有这些领域中特别感兴趣的是关于原始图的光谱特性。尽管存在许多执行此任务的方法，但它们通常需要昂贵的线性代数操作并产生高工作复杂性。我们适应了文献与文献结合的光谱粗糙，以开发出一种具有工作复杂性的变形算法，其复杂性远小于以前的工作。我们进一步表明，该算法很容易平行，并且在网格上呈现出令人印象深刻的缩放结果。
Finding coarse representations of large graphs is an important computational problem in the fields of scientific computing, large scale graph partitioning, and the reduction of geometric meshes. Of particular interest in all of these fields is the preservation of spectral properties with regards to the original graph. While many methods exist to perform this task, they typically require expensive linear algebraic operations and yield high work complexities. We adapt a spectral coarsening bound from the literature in order to develop a coarsening algorithm with a work complexity that is drastically smaller than previous work. We further show that this algorithm is easily parallelizable and presents impressive scaling results on meshes.
