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.

翻译：在科学计算、大比例图分割和减少几何间距领域,寻找大图的粗略表示法是一个重要的计算问题。所有这些领域特别感兴趣的是保存与原始图有关的光谱属性。虽然有许多方法可以执行这项任务,但它们通常需要昂贵的线性代数操作和产生很高的工作复杂性。我们调整了从文献中提取的光谱粗化法,以发展一种比以往工作复杂程度大大小于以往工作的粗化算法。我们进一步表明,这种算法很容易平行,并给胶片带来令人印象深刻的缩放效果。