An Improvement on Orszag's Fast Algorithm for Legendre Polynomial Transform

IPSJ Web Site 6 References

Bibliographic Information

Other Title
  • Orszagの高速Legendre多項式変換法の改良
  • Orszag ノ コウソク Legendre タコウシキ ヘンカンホウ ノ カイリョウ

Search this article

Description

1986年にOrszagはLegendre多項式変換を含むStrum-Liouville固有関数変換の評価計算に対する高速算法を提案した. 彼の算法は固有関数のWKB近似を利用して計算の一部をFFTで実行することにより 直接計算でO (N^2)かかるN次N点の評価計算をO (Nlog^2N/loglogN)に改善できるものであるが 実際には計算に無駄が多く 精度も悪く実用的ではない. 我々はLegendre多項式変換についてOrszagの算法の改良を提案する. 我々の改良により 計算量はO (NlogN)に改善され 単精度程度の精度ではN≧256で 倍精度程度の精度ではN≧512で それぞれ直接計算よりも高速になった.

In 1986 Orszag proposed a fast algorithm for Sturm-Liouville eigenfunction transform including the Legendre polynomial tranform. His algorithm, which exploits the speed of FFT through the WKB approximation, runs in time O (Nlog^2N/loglogN) for N-point evaluation of N-th order tranform, while the direct computation requires O (N^2) time. The algorithm is, however, not practical because of its low precision and algorithmic unsophisticatedness. In this note, we improve Orszag's algorithm for the Legendre polynomial transform. Our algorithm has computational complexity O (NlogN), and is faster than the direct computation for N≧256 with relative error ≈ 10^<-8>, and for N≧512 with relative error ≈ 10^<-14>.

Journal

References(6)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top