スケール不変な格子を生成する適応格子細分化法アプリケーションのための計算量予測手法

摘要

適応格子細分化（AMR：Adaptive Mesh Refinement）法は，多次元空間を計算対象とするアルゴリズムの計算量を削減するための技術である．そのアプリケーションは，問題のインスタンスごとに実行時問 が異なるという性質がある.本論文では，AMR法アプリケーションの実行時間を見積もるために，計算量を具体的数値として予測する手法を提案する．AMR法は，空間を離散化するために，階層構造の格子を適応的に生成するという特徴がある.アプリケーションの計算量は,この格子が含むセルの数に比例する.提案手法は，階層構造の格子をフラクタルとみなすことによを）,セルの数を推定する．計算量予測の人力には，AMR法が初期階層において生成したセルの数を用いる.2種類のAMR法アプリケーションに提案手法を適用した結果，アプリケーションの進捗10％未満の時点において,計算量を誤差12％未満で予測できた