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

川崎　康博  伊野　文彦  萩原　兼一  

誌名
電子情報通信学会論文誌 D   Vol.J90-D    No.10    pp.2691-2703
発行日: 2007/10/01
Online ISSN: 1881-0225
DOI: 
Print ISSN: 1880-4535
論文種別: 論文
専門分野: アルゴリズム理論
キーワード: 
適応格子細分化法,  計算量解析,  実行時間予測,  フラクタル幾何学,  

本文: PDF(1MB)>>
論文を購入


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