It Pays to Be Lazy: Reusing Force Approximations to Compute Better Graph Layouts Faster

N-body simulations are common in applications ranging from physics simulations to computing graph layouts. The simulations are slow, but tree-based approximation algorithms like Barnes-Hut or the Fast Multipole Method dramatically improve performance. This paper proposes two new update schedules, uniform and dynamic, to make this type of approximation algorithm even faster by updating the approximation less often. An evaluation of these new schedules on computing graph layouts finds that the schedules typically decrease the running time by 9% to 18% for Barnes-Hut and 88% to 92% for the Fast Multipole Method. An experiment using 4 layout quality metrics on 50 graphs shows that the uniform schedule has similar or better graph layout quality compared to the standard Barnes-Hut or Fast Multipole Method algorithms.

在从物理模拟到计算图布局的广泛应用领域中，N体模拟是一种常见的计算方法。此类模拟过程相对缓慢，然而，基于树结构的近似算法，如Barnes-Hut算法或快速多极子方法，显著提升了计算效率。本文提出两种新颖的更新调度方案，即均匀调度和动态调度，旨在通过减少近似更新的频率，进一步加快这类近似算法的速度。对计算图布局进行的新调度方案评估显示，这些调度方案通常将Barnes-Hut算法的运行时间缩短9%至18%，而快速多极子方法的运行时间则缩短88%至92%。在采用4个布局质量指标对50个图进行的一项实验中，均匀调度方案与标准Barnes-Hut或快速多极子方法算法相比，展现出相似或更优的图布局质量。