基数2のFFTに基づく任意項数の離散型Fourier変換
スポンサーリンク
概要
- 論文の詳細を見る
任意項数の多項式f(z)=c_0+c_1z+…+c_<N-1>Z^<N-1>の係数を与えて, N=2^n_1+2^n_2+…+2^n_m個の標本 f(exp(2πi(j+1/2)/2^n_l)), 0≤j<2^l, 1≤l≤mを求める. この際, Nの2進表示に対応して項数が2のべき2^n_lの中点公式によるFFTが使われる. この逆変換は, f(z)に対する一つの補間法であるが, 計算量(複素数乗算回数)は, いずれも(N log_2 N)/2である. また, この補間法の収束性および数値的安定性を解析し, 本算法が任意項数の(広義の)離散型Fourier変換の高速算法の名に値することを示す.
- 1984-01-15
著者
関連論文
- Quadrature rule for Abel’s equations: uniformly approximating fractional derivatives
- Quadrature rule for Abel's equations: uniformly approximating fractional derivatives (計算科学の基盤技術としての高速アルゴリズムとその周辺--RIMS研究集会)
- Uniform approximation to fractional derivatives of functions of algebraic singularity
- 多項式剰余列の安定な拡張算法
- 自然な数学インタフェースを持つプログラミング環境(科学技術における数値計算の理論と応用II)
- 数式の意味解釈とその文法及びメタ言語
- Givens 回転による多項式剰余列の拡張算法
- 自然な数学表記のためのユーザインターフェイス
- 多項式剰余列の安定な生成法
- 自然な数式ヒューマンインタフェースに関する研究
- 数値的に安定な一変数多項式剰余列の生成法(数値計算アルゴリズムの現状と展望II)
- 悪条件線形方程式に対する一つの直接解法 : 打ち切り最小2乗最小ノルム解
- 知識ベースによる数式の意味解釈とその応用
- Durand-Kerner型補助関数を用いた非線形方程式の多段反復解法
- 特異に近い関数の積分に対する自動積分(数値計算における精度保証付き算法とその計算量に関する研究)
- グラム・シュミット法による第1種フレドホルム積分方程式の解法(数値計算における精度保証付き算法とその計算量に関する研究)
- 多項式高速アルゴリズムの統一と一般化
- 数式のデータ表現と意味解釈システム
- 孫子定理の一応用 : 代数方程式の数値的因数分解(数値解析とそのアルゴリズム)
- 分割統治法による多項式の数値的因数分解
- べき型特異性をもつ関数の不定積分に対する自動積分法
- 準等間隔標本点上の三角多項式補間
- 準等間隔標本点上の実高速フーリエ変換
- 大規模一般化固有値問題の解法とその並列化 (微分方程式の数値解法と線形計算)
- 代数方程式に対する高次Pomentale法の収束特性(数値計算アルゴリズム)
- 代数方程式に対する高次Nourein法の収束特性(数値計算アルゴリズム)
- 解析関数の多項式因子を求める精度保証付き解法
- Pade近似を用いた数値等角写像の計算法
- 解析関数の多項式因子を求める方法 (微分方程式の離散化手法と数値計算アルゴリズム)
- 扇形領域におけるPoisson方程式に対するCosine-Chebyshev-Galerkin法
- 扇形領域におけるPoisson方程式に対するLegendre-Galerkin法
- 解析関数の因子を求める方法とその精度保証 (精度保証付き数値計算法とその周辺)
- 角をもつ有界領域におけるPoisson方程式に対する無限要素解法の実装
- 線型連立系に対する積型反復解法の加速多項式の評価
- Mathematical Notation Understanding Methodology
- 3項漸化式の最小解に対する安定な算法
- 等差数列的に標本数を増す補間的自動積分法
- Legendre-Galerkin Method for Poisson Equation on a Fan-Shaped Domain (Numerical Solution of Partial Differential Equations and Related Topics)
- 交代級数に対する最適線形加速法
- y"(x)=f(x), y(-1)=y(1)=0の最適な数値積分公式について(数値計算の基本アルゴリズムの研究)
- 数値等角写像におけるTheodorsen方程式の解法
- ニ次元フーリエ展開におけるN $\log_2$ N個の係数の選択的計算法 (数値計算のアルゴリズムの研究)
- 静電場的解釈に基づく代数方程式の反復解法
- 数値計算のつぼ(7)行きはよいよい?
- 数値計算のつぼ(3)この精度でご満足?
- 第27回数値解析シンポジウム(学術会合報告)
- 計算環境の改善を
- A Series of Collocation Runge-Kutta Methods
- 基数2のFFTに基づく任意項数の離散型Fourier変換
- √倍的に標本数を増す複素関数入力のFFT
- Wegmann 法に基づく数値等角写像の自動化について
- 3, 4, 5, 6次元GLPの探索について
- 等角写像に関する Wegmann の方法の不安定性の解析とその安定化
- 高次収束する代数方程式の全根同時反復解法
- Pade近似による代数方程式の反復解法
- 高次収束する代数方程式の全根同時反復解法(数値解析と科学計算)
- 静電場的解釈による実係数代数方程式の反復解法
- 静電場的解釈に基く代数方程式の解法とその応用(数値計算基本アルゴリズムとそのソフトウェアの研究)
- 標本数を漸増する補間型積分則の重みの正値性について(数値計算基本アルゴリズムとそのソフトウェアの研究)
- 静電場的解釈による代数方程式の解法
- 実係数代数方程式の連立型解法とその静電場的解釈(並列数値計算アルゴリズムとその周辺)
- 第1種不完全複素楕円積分の全域かつ一様近似(II)
- 第1種不完全複素楕円積分の全域かつ一様近似
- 第1種複素楕円積分の全域近似 : 母数が小さい場合(並列数値計算アルゴリズムとその周辺)
- 積型積分の自動積分法べき型特異点の場合
- 対数特異性をもつ関数の不定積分に対する自動積分法
- 対数核を含む不定積分の自動積分法(スーパーコンピュータのための数値計算アルゴリズムの研究)
- 一般化チェビシェフ補間に基づく多重積分(並列数値計算アルゴリズムとその周辺)
- チェビシェフ級数展開と加速法による半無限振動積分
- 1階微分方程式に対するChebyshew-Galerkin法による特異積分(数値計算の基本アルゴリズムの研究)
- コーシーの主値積分に対する自動積分法
- 激しい振動積分の自動積分法
- Quadrature rule for indefinite integral of algebraic-logarithmic singular integrands
- 高橋,森の数値積分理論のFFTによる実現
- 標本点数を低倍率で漸増させる実関数のFFT
- Van der Corput列に基づく補間法の数値的安定性 (線型計算の標準算法と実現)
- 激しい振動積分$\int_{-1}^{1}e^{i{\omega}t}f(t)dt$の求積法 (数値計算のアルゴリズムの研究)
- $\sqrt{2}$倍的に標本数を増す関数入カのFFT (数値計算のアルゴリズムの研究)
- フーリエ変換サブルーチン・パッケージの作成 (数学的ソフトウェアの評価)
- 一様分布に基づ
- Numerical Evaluation of Goursat's Infinite Integral with an Unbounded Function
- Quadrature rule for indefinite integral of algebraic-logarithmic singular integrands
- FFTとその数値解析における応用