論文の概要: On the Additive FFT Techniques over Binary Extension Fields

• arxiv url: http://arxiv.org/abs/2608.20855v1
• Date: Fri, 21 Aug 2026 08:20:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-24 14:49:32.474513
• Title: On the Additive FFT Techniques over Binary Extension Fields
• Title（参考訳）: 二元拡大場上の付加FFT法について
• Abstract要約: 任意の順序基底および任意の次元分割に適用可能な一般基底 AFFT を提案する。 次に、フレームワークをCantorの特殊ベースに特殊化し、2つのAFFTアルゴリズムを得る。 実装結果から,テスト対象の42構成のうち37項目において,Cantorの特別なベースよりもアルゴリズムがLCH AFFTよりも高速であることが示された。
• 参考スコア（独自算出の注目度）: 3.0969191504482243
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Motivated by Bailey's four-step FFT algorithm (1989), we develop additive FFT techniques for polynomial evaluation over affine subspaces of binary extension fields. Our key insight is that the Taylor expansion with respect to vanishing polynomials of subspaces provides a structural counterpart to Bailey's matrix formulation. It decomposes an additive FFT (AFFT) into independent sub-AFFTs associated with the columns and rows of a matrix. We first present a general-basis AFFT that applies to any ordered basis and any split of the dimension, providing a unified baseline for measuring the gains from specialization. We then specialize the framework to the Cantor special basis and obtain two AFFT algorithms. The first supports an arbitrary decomposition of the AFFT dimension and exploits the Cantor special basis structure to perform the Taylor expansion stage without finite field multiplications. The second uses a decomposition that preserves the binomial form of the relevant subspace polynomials. It requires exactly $\frac{1}{2}n\log_2 n$ multiplications, together with a closed-form addition count determined by the binary representation of $m$. Our implementation results show that this algorithm is faster than the LCH AFFT over a Cantor special basis in 37 of the 42 configurations tested across two hardware platforms. This performance advantage stems from its fully recursive structure, which provides memory locality by design and avoids separate basis-conversion and evaluation stages. Finally, in a separate analysis, we formalize the notion of partial Cantor special bases and identify parameter regimes in which both the von zur Gathen-Gerhard algorithm and our general-basis AFFT require fewer additions and multiplications than the first Gao-Mateer algorithm.
• Abstract（参考訳）: ベイリーの4ステップ FFT アルゴリズム (1989) に動機付け, 2進拡大場のアフィン部分空間上での多項式評価のための付加的 FFT 手法を開発した。 我々の重要な洞察は、部分空間の消滅多項式に対するテイラー展開はベイリーの行列の定式化と構造的な相反するものであるということである。 加法FFT(AFFT)を行列の列と行に関連付けられた独立サブAFFTに分解する。 まず、任意の順序基底と任意の次元分割に適用可能な一般基底AFFTを示し、特殊化から得られる利得を計測するための統一されたベースラインを提供する。 次に、フレームワークをCantorの特殊ベースに特殊化し、2つのAFFTアルゴリズムを得る。 1つ目は AFFT 次元の任意の分解をサポートし、Cantor の特別な基底構造を利用して、有限体乗法なしでテイラー展開段階を実行する。 2つ目は、関連する部分空間多項式の二項形式を保存する分解である。 正確に$\frac{1}{2}n\log_2 n$乗法と$m$のバイナリ表現によって決定される閉形式加算数が必要である。 実装の結果,このアルゴリズムは2つのハードウェアプラットフォームでテストされた42の構成のうち37のCantorを特別なベースで比較すると,LCH AFFTよりも高速であることがわかった。 この性能上の利点は、設計によるメモリ局所性を提供し、別々の基底変換と評価段階を避けるという、完全に再帰的な構造に由来する。 最後に、別の分析において、部分カントール特殊基底の概念を定式化し、von zur Gathen-Gerhardアルゴリズムと一般基底 AFFT の両方が第1のGao-Mateerアルゴリズムよりも少ない加算と乗算を必要とするパラメータ状態を特定する。

関連論文リスト

• Prime Fourier Embeddings: A Principled Basis for Modular Arithmetic [5.341304176259271]
  PFE(Prime Fourier Embeddings)を紹介する。 PFE は整数を Q の調和解析から導かれる素指数 (cos, sin) 対として符号化する。 正方形のない複合変調の場合、中国語のRemainder Theoremはどの素チャネルがタスク関連であるかを予測する。
  論文  参考訳（メタデータ） (2026-06-22T08:50:41Z)
• On the Fast Fourier Transform on SU(2) [45.899400495223375]
  特殊ユニタリ群 SU(2) は量子力学における対称性の記述において基本的な役割を果たす。 我々は古典的なクーリー・テューキー分割次元スキームにインスパイアされた高速フーリエ変換アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2026-04-19T17:38:38Z)
• Multinoulli Extension: A Lossless Continuous Relaxation for Partition-Constrained Subset Selection [60.07018090570548]
  我々はパラメータフリーで、歪んだ局所探索法と同じ近似保証を実現できるMultinoulliSCGという新しいアルゴリズムを導入する。 また、分割制約に関する未探索オンラインサブセット選択問題に対して、Multinoulli-CGとMultinoulli-GAGAという2つの新しいオンラインアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-03-23T02:30:01Z)
• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  周期的な対角構造を持つスパース行列を符号化するための明示的な量子回路を提供する。 本手法の様々な応用は, 微分問題を解く文脈で論じる。
  論文  参考訳（メタデータ） (2026-02-11T07:24:33Z)
• Do It for HER: First-Order Temporal Logic Reward Specification in Reinforcement Learning (Extended Version) [49.462399222747024]
  本研究では,大規模状態空間を持つ決定過程(MDP)における非マルコフ報酬の論理的仕様に関する新しい枠組みを提案する。 我々のアプローチは有限トレース(LTLfMT)上での線形時間論理モデュロ理論を利用する 本稿では,報酬マシンとHER(Hindsight Experience Replay)をベースとした一階述語論理仕様の翻訳手法を提案する。
  論文  参考訳（メタデータ） (2026-02-05T22:11:28Z)
• Higher-order spectral form factors of circular unitary ensemble [1.795521261711957]
  スペクトルフォームファクタは、乱れた量子系の普遍性を探索する重要なツールとして機能する。 円形ユニタリアンサンブル(CUE)における2階および3階SFFの正確な閉形式表現について述べる。 特に、二階 SFF に対して、ポリガンマ関数の項の正確な閉形式式を導出する。
  論文  参考訳（メタデータ） (2025-12-01T06:02:01Z)
• Cartan-Khaneja-Glaser decomposition of $\SU(2^n)$ via involutive automorphisms [0.46664938579243564]
  本稿では, 1次行列のカルタン・カーネジャ・グラーガー分解を$SU(2n)$で行う新しいアルゴリズムを提案する。 我々は、不定義行列対数への依存や、切り詰めたベーカー・カンベル・ハウスドルフ級数(BCH)の収束問題など、それらの方法の重要な制限を克服する。
  論文  参考訳（メタデータ） (2025-09-05T19:46:50Z)
• Unitary Approximate Message Passing for Matrix Factorization [90.84906091118084]
  行列分解 (MF) を一定の制約で考慮し, 様々な分野の応用を見いだす。 我々は,効率の良いメッセージパッシング実装であるUAMPMFを用いて,MFに対するベイズ的アプローチを開発する。 UAMPMFは、回復精度、ロバスト性、計算複雑性の観点から、最先端のアルゴリズムを著しく上回ることを示す。
  論文  参考訳（メタデータ） (2022-07-31T12:09:32Z)
• Finite-Function-Encoding Quantum States [52.77024349608834]
  任意の$d$値論理関数を符号化する有限関数符号化(FFE)を導入する。 それらの構造的特性について検討する。
  論文  参考訳（メタデータ） (2020-12-01T13:53:23Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。