フーリエ変換関数

フーリエ変換関数#

定義#

\(z\) を長さ \(n_1 \times n_2 \times \dots \times n_d\) (\(d \in \mathbb{Z}_{>0}\)、\(M \in \mathbb{Z}_{>0}\)、\(n_j \in \mathbb{Z}_{>0}\ \forall j \in \lbrace 1, 2, \ldots, d \rbrace\)、および \(m \in \lbrace 0, 1, \ldots, M-1\rbrace\)) の \(M\)) 個の有限 \(d\) 次元離散列 \(z^{m}\) の集合とします。\(m\) 番目のシーケンスのエントリーは \(z^{m}_{k_{1}, k_{2}, \ldots, k_{d}}\) で表され、整数インデックス \(k_j\) は \(0 \leq k_{j} < n_{j},\ \forall j \in \lbrace 1, 2, \ldots, d \rbrace\) のようになります。

\(z^{m}\) の離散フーリエ変換 (DFT) は、次の要素を持つ有限 \(d\) 次元 \(n_1 \times n_2 \times \dots \times n_d\) 離散列 \(\hat{z}^{m}\) です。

\[\hat{z}^{m}_{k_{1}, k_{2}, \ldots, k_{d}} = \sigma_{\delta} \displaystyle\sum_{j_{d}=0}^{n_{d}-1}\dots\displaystyle\sum_{j_{2}=0}^{n_{2}-1}\displaystyle\sum_{j_{1}=0}^{n_{1}-1} z^{m}_{j_{1}, j_{2}, \dots, j_{d}} \exp \left[ \delta 2\pi \imath \left( \sum_{\ell=1}^{d} \frac{j_{\ell}k_{\ell}}{n_{\ell}} \right) \right], \forall m \in \lbrace 0, 1, \ldots, M-1\rbrace\]

ここで、\(\imath^2 = -1\) です。上記の式では、\(\delta = \pm 1\) は DFT の 2 つの「方向」のうちの 1 つを決定し、\(\sigma_{\delta} \in \mathbb{R}\) はその方向に関連付けられたスケーリング係数を表します。\(\delta=-1\) は「順方向 DFT」 (順方向スケーリング係数 \(\sigma_{-1}\) を使用) を定義し、\(\delta=+1\) は「逆方向 DFT」 (逆方向スケーリング係数 \(\sigma_{+1}\) を使用) を定義します。

複数のデータセットに対して \(M\) 個の同一定義の DFT を計算することを「バッチ DFT」と呼び、\(M\) を「バッチサイズ」と呼びます。

順方向ドメインのタイプ#

順方向 (逆方向) DFT の入力 (出力) 離散シーケンスの領域は、「順方向領域」と呼ばれます。逆に、順方向 (逆方向) DFT の出力 (入力) 離散シーケンスの領域は「逆方向領域」と呼ばれます。2 種類の順方向ドメインが考えられます。

  • 複素数 \(d\) 次元シーケンスの集合は、「複素順方向ドメイン」と呼ばれます。

  • 実数 \(d\) 次元シーケンスの集合は、「実順方向ドメイン」と呼ばれます。

同様に、複素数 (実数) 順方向領域の DFT はそれぞれ「複素数 DFT」 (実数 DFT) と呼ばれます。順方向ドメインのタイプに関係なく、逆方向ドメインのデータシーケンスは常に複素数ですが、実変換には制約があります (以下で説明)。

冗長でないエントリーの基本範囲#

一般に、\(0\leq k_{\ell} < n_{\ell}, \forall \ell \in \lbrace 1, \ldots, d \rbrace\) かつ \(0\leq m < M\) となるデータエントリー \(\left(\cdot\right)^{m}_{k_{1}, k_{2}, \ldots, k_{d}}\) は、\(M\) 個の関連する \(d\) 次元シーケンスのいずれかを明確に決定するのに十分です。実数 DFT の場合、逆方向ドメインのデータシーケンスは、より小さなエントリーセットから決定できます。実際、上の式で \(z\) のすべての要素が実数である場合、\(\hat{z}\) の要素は複素数であり、任意の \(m \in \lbrace 0, 1, \ldots, M-1\rbrace\) に対して、 \(\left(\hat{z}^{m}_{k_{1}, k_{2}, \dots, k_{d}}\right)^{*} = \hat{z}^{m}_{j_{1}, j_{2}, \dots, j_{d}}\) ただし \(j_{\ell} = \left(n_{\ell} - k_{\ell}\right)\pmod{n_{\ell}}, \ \forall \ell \in \lbrace 1, \ldots, d \rbrace\)) であり、\(\lambda^{*}\) は複素数 \(\lambda\) の共役を表します。

この共役対称関係により、データの約半分が後方ドメインで冗長になります。実数 DFT の場合、後方ドメインのデータシーケンスは、\(0\leq m < M\)、\(0\leq k_{\ell} < n_{\ell}, \forall \ell \in \lbrace 1, \ldots, d \rbrace \backslash \lbrace p \rbrace\)、および任意の \(p \in \lbrace 1, \ldots, d \rbrace\) に対して \(0\leq k_{p} \leq \lfloor\frac{n_{p}}{2}\rfloor\) となる任意の非冗長エントリーセット \(\left(\cdot\right)^{m}_{k_{1}, k_{2}, \ldots, k_{d}}\) から決定できます。oneMKL では、実数 DFT の逆方向ドメインに属するデータシーケンスの非冗長エントリーの基本セットをキャプチャーするため、規則 \(p = d\) が使用されます。

言い換えれば、oneMKLは以下となる \(M\) \(d\) 次元の有限データシーケンス \(\left(\cdot \right)^{m}_{k_{1}, k_{2},\ldots, k_{d}}\) の集合を期待し、生成します。

  • \(0 \leq m < M\)。

  • \(0 \leq k_{j} < n_{j},\ \forall j \in \lbrace1, \ldots, d - 1\rbrace\)、\(d > 1\) の場合。

  • \(0 \leq k_{d} < n_{d}\)、ただし実数 DFT の逆方向ドメインのデータシーケンスを除く。

  • \(0 \leq k_{d} \leq \lfloor\frac{n_d}{2}\rfloor\)、実数 DFT の逆方向ドメインのデータシーケンスの場合。

最後に、共役対称関係により、実数 DFT の逆方向領域におけるデータシーケンスのエントリー (またはそのペア) の一部がさらに制約されることに注意してください。具体例:

  • 任意のエントリ \(\left(\cdot\right)^{m}_{k_{1}, k_{2}, \ldots, k_{d}}\) に対して虚数部は\(0\) でなければなりません。この場合、\(k_{\ell} \equiv \left(n_{\ell} - k_{\ell}\right) \pmod {n_{\ell}}, \forall \ell \in \lbrace{1, \ldots, d\rbrace}\) が成立します。例えば、エントリー \(\left(\cdot\right)^{m}_{0, 0, \ldots, 0}\) です。

  • \(\left(\cdot\right)^{m}_{k_{1}, k_{2}, \ldots, k_{d}}\) と \(\left(\cdot\right)^{m}_{j_{1}, j_{2}, \ldots, j_{d}}\) のエントリーのペアで、\(k_{\ell} \equiv \left(n_{\ell} - j_{\ell}\right) \pmod {n_{\ell}}, \forall \ell \in \lbrace{1, \ldots, d\rbrace}\) が互いに複素共役でなければならない、例えば、エントリー \(\left(\cdot\right)^{m}_{1, 0, \ldots, 0}\) と \(\left(\cdot\right)^{m}_{n_{1} - 1, 0, \ldots, 0}\) は複素共役でなければなりません (この例は、\(n_1 = 2\) の場合は後者のカテゴリーに分類されることに注意してください)。

注

入力データがこれらの制約を満たしていない場合、実逆方向 DFT に対する oneMKL の動作は未定義になります。実数の逆方向 DFT の入力データによってこれらの制約が満たされていることを保証するのはユーザーの責任です。

DPC++ サポート#

インテル® oneMKL は、離散フーリエ変換を計算する DPC++ インターフェイスを提供します。このインターフェイスは oneapi::mkl::dft 名前空間を宣言しており、これには以下が含まれます。

それぞれのタイプ oneapi::mkl::dft::domain と oneapi::mkl::dft::precision (スコープ列挙を参照) の dom と prec (コンパイル時に既知) の値によって表される順方向ドメインと浮動小数点形式の DFT の場合、目的の変換とその一般的な構成は、oneapi::mkl::dft::descriptor<prec, dom> テンプレート・クラスのオブジェクトを介して伝達されます。目的の DFT 構成とユーザー提供の sycl::queue インスタンスに正常にコミットされると、その descriptor オブジェクトは、関連する入力および出力データとともに、適切な計算関数への引数として使用できます。

ユーザーが割り当てたワークスペースが使用されない限り、DPC++ インターフェイスは 4 つのステップで DFT を計算します (簡潔にするために、以下では先頭の名前空間指定子 oneapi::mkl::dft を省略しています)。

  1. 対象となるDFT問題の descriptor オブジェクト desc を、関連するパラメーター化されたコンストラクターを呼び出して作成します。例:

    descriptor<prec, dom> desc(lengths);

    ここで、prec と dom はそれぞれ precision タイプと domain タイプの特殊化値です。desc は、次元 (またはランク)、長さ、変換の数、入力データと出力データのレイアウト (ストライド、距離、およびその他の構成パラメーターによって定義されます)、スケーリング係数などの変換の構成を取得します。この呼び出しでは、すべての構成設定にデフォルト値が割り当てられますが、その後変更が必要になる場合があります。

    デフォルトでは、descriptor オブジェクトは、構築時に設定された精度と長さに基づいて、バッチ処理されていない (\(M = 1\))、スケールされていない (\(\sigma_{\delta} = 1, \ \forall \delta\)) DFT の順方向領域のインプレース計算用に初期化されます。

  2. 必要に応じて、関連する構成設定メンバー関数を必要な回数だけ呼び出して、desc の構成を調整します (例: デフォルトとは異なるデータ・ストレージ・レイアウトを指定する場合)。(ほぼ) すべての構成パラメーターに関連付けられた値は、適切な構成クエリーメンバー関数を使用して取得できます (照会された構成パラメーターが以前に設定されていない限り、デフォルト値が返されます)。

  3. commit メンバー関数を呼び出して desc をコミットします。つまり、オブジェクトが特定のデバイス上で定義された変換を計算できるように準備します。オブジェクトがコミットされると、変換のタイプと数、ストライドと距離、データのタイプとストレージレイアウトなどの構成パラメーターは、計算用途で固定であるとみなされます。つまり、オブジェクトをコミットした後にこれらのいずれかを変更すると、commit メンバー関数が再度呼び出されるまで、計算でそのオブジェクトは事実上無効になります。commit 関数は、関連するすべてのランタイム関連情報 (必要な計算デバイスを含む) を決定する sycl::queue 引数を受け取ります。

  4. 目的の変換を計算するのに必要な回数だけ、(適切な) compute_forward または compute_backward 関数の呼び出しでコミットされた desc を使用します。これらの関数には、コミットされた記述子オブジェクト (必要な操作を完全に定義する) とデバイスがアクセス可能な入力および出力データ以外の引数は必要ありません。

DPC++ での DFT の構成と計算に特化したセクションに、いくつかの使用例が提供されています。

注

複数の同一構成の DFT 計算を実行するアプリケーションで最高のパフォーマンスを得るには、初期化手順など、アプリケーションのホットパスの外部で DFT 記述子を作成、構成、コミットすることを強くお勧めします。パフォーマンスが重要なセクションで呼び出される DFT 関連関数は、compute_forward と compute_backward のみにする必要があります。