- 著者
-
森 明子
須田 礼仁
杉原 正顯
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 情報処理学会研究報告ハイパフォーマンスコンピューティング(HPC) (ISSN:09196072)
- 巻号頁・発行日
- vol.1999, no.38, pp.49-54, 1999-05-14
- 参考文献数
- 9
1986年にOrszagはLegendre多項式変換を含むSturm?Liouville固有関数変換の評価計算に対する高速算法を提案した。彼の算法は固有関数のWKB近似を用いて計算の一部でFFTを利用することにより、直接計算でO (^) かかる計算量がO ( log^2N/log log) に改善できるというものである。しかし彼の算法は計算の無駄が多く、精度も悪く実用的ではない。我々はLegendre多項式変換の場合についてこのOrszagの算法を改良したので報告する。アルゴリズムの改良により計算量はO ( log ) に改善され、高精度近似公式の採用により、単精度程度の精度でN≥128,倍精度程度の精度でN≥256で直接法よりも高速となることがわかった。In 1986 Orszag proposed a fast algorithm for Sturm-Liouville eigenfunction transform including the Legendre polynomial transform. His algorithm, which exploits the high speed of FFT through the WKB approximation, runs in time O (N log^2 N/log log N), while the direct computation requires O (N^2) time. His algorithm is, however, not practical because of its low precision and algorithmic unsophisticatedness. We improve Orszag's algorithm in the case of the Legendre polynomial transform. The improved algorithm runs in time O (N log N), and the Stieltjes's higher order approximation formula enables high precision. Our scheme is faster than the direct method for N ≥ 128 with the error tolerance ε=10^<-6> and for N ≥ 256 with ε=10^<-12>.