论文标题
LGRASS：第三ACM-CHINA国际平行计算挑战的最终任务的线性图谱光谱稀疏
LGRASS: Linear Graph Spectral Sparsification for Final Task of the 3rd ACM-China International Parallel Computing Challenge
论文作者
论文摘要
本文介绍了我们的解决方案，以优化第三ACM-CHINA IPCC。通过复杂性分析，我们确定了原始算法的三个耗时的子例程：标记边缘，计算伪逆和排序边缘。由于它们的超线时间复杂性，这些子例程成为主要的性能瓶颈。为了解决这个问题，我们提出了Lgrass，这是一种线性图光谱稀疏算法以在严格的线性时间内运行。 Lgrass利用跨越树的属性和有效算法来优化瓶颈子例程。此外，我们为Lgrass制定了一种并行处理方案，以充分利用多处理器硬件。实验表明，我们提出的方法在官方测试用例上完成了数十个毫秒的任务，并随着图形尺寸在随机测试用例上的扩展而保持线性。
This paper presents our solution for optimization task of the 3rd ACM-China IPCC. By the complexity analysis, we identified three time-consuming subroutines of original algorithm: marking edges, computing pseudo inverse and sorting edges. These subroutines becomes the main performance bottleneck owing to their super-linear time complexity. To address this, we proposed LGRASS, a linear graph spectral sparsification algorithm to run in strictly linear time. LGRASS takes advantage of spanning tree properties and efficient algorithms to optimize bottleneck subroutines. Furthermore, we crafted a parallel processing scheme for LGRASS to make full use of multi-processor hardware. Experiment shows that our proposed method fulfils the task in dozens of milliseconds on official test cases and keep its linearity as graph size scales up on random test cases.
