知识卡片

普通读书笔记卡 · 3693.c.1

偶奇系数拆成两个半规模多项式

理解等级:中级

按系数下标奇偶拆成A偶与A奇,可写成A(x)=A偶(x²)+xA奇(x²)。在n次单位根处求值时,平方后的采样点仅有n/2个互异值,于是原DFT转成两个n/2规模DFT再合并。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第30章 多项式与快速傅里叶变换 · 查看原书依据

      The FFT method employs a divide-and-conquer strategy, using the even-indexed and odd-indexed coefficients of A(x) separately to define the two new polynomials Aeven(x) and Aodd(x) of degree-bound n/2: Aeven(x) = a0 + a2x + a4x2 + ⋯ + an−2xn/2−1, Aodd(x) = a1 + a3x + a5x2 + ⋯ + an−1xn/2−1. Note that Aeven contains all the even-indexed coefficients of A (the binary

    参考来源

    - 位置:《算法导论(第4版)》第30章《多项式与快速傅里叶变换》(OEBPS/chapter030.xhtml,文本字符[15000,20000))。 - 结论依据:第30.2节定义偶、奇下标系数多项式;`OEBPS/images/Art_P1074.jpg`(式30.9)给出拆分等式,随后“halving lemma”说明平方后只有 n/2 个互异采样值。 - 公式图核读:A(x)=Aᵉᵛᵉⁿ(x²)+xAᵒᵈᵈ(x²);这里要求 n 为2的幂以使用书中的递归 FFT。 - 原始内容:The FFT method employs a divide-and-conquer strategy, using the even-indexed and odd-indexed coefficients of A ( x ) separately to define the two new polynomials A even ( x ) and A odd ( x ) of degree-bound n /2: A even ( x ) = a 0 + a 2 x + a 4 x 2 + ⋯ + a n −2 x n /2−1 , A odd ( x ) = a 1 + a 3 x + a 5 x 2 + ⋯ + a n −1 x n /2−1 . Note that A even contains all the even-indexed coefficients of A (the binary