Is Nearly-linear the Same in Theory and Practice? A Case Study with a ... - todo314 @ ウィキ

Is Nearly-linear the Same in Theory and Practice? A Case Study with a Combinatorial Laplacian Solver

• Daniel Hoske, Dimitar Lukarski, Henning Meyerhenke, Michael Wegner
• SEA 2015

概要

• A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Timeを実装してみました！
• ほぼ線形時間の計算量だけど、定数が大きすぎて、全然遅いよ！残念！
• low stretch保証のある手法よりも、単純な全域木のほうが良かったりしたよ！

準備

• 基本的なソルバの戦略
  • 全域木Tをとってくる
  • 「Tだけ非ゼロ AND demandがb」uniqueなフローfを計算
  • 電圧降下が非ゼロな閉路がある限り
    • Tから作れる閉路基底からstretchに比例する確率で閉路を選択
    • fを閉路にそって押し戻す
  • fを返す
• 全域木
  • ほぼ線形時間でほぼ線形なstretchをもつ全域木は計算可能
    • stretchのlog factorはちまちま減らされているけど、実際には効果ない
  • Dijkstraベースの方法
  • Kruskalベースの方法
• 木上のフロー
  • クエリはちょっとだけ頑張る
• 閉路選択
  • 木上に無い辺を一様無作為に選ぶ（で、閉路を構成する）
  • 本当に保証を得るためには、stretchに応じて重み付けする必要ある
  • roulette wheel selection O(log m)

実験結果

• 格子 OR Barabasi-Albertの2種類
• 既存の方法が中々に早い

まとめ

• 実験的にでもいいからちゃんと早くできるだろうか・・・？
• 後でまたちゃんと読む

Laplacian SEA スペクトラルグラフ理論

2018/09/27