Лемма Ланцоша – Даниельсона

Ле́мма Ла́нцоша – Дание́льсона, описывает алгоритм сведения классического дискретного преобразования Фурье чётного размера ${\displaystyle n}$ к двум дискретным преобразованиям Фурье половинного размера ${\displaystyle n/2}$ и последующему выполнению не более ${\displaystyle 2n}$ арифметических операций над комплексными числами, опубликована в 1942 г. в работе Г. Ч. Даниельсона и К. Ланцоша. В случае когда ${\displaystyle n}$ имеет вид ${\displaystyle 2^{k},}$ где ${\displaystyle k}$ – натуральное число, лемма может быть применена рекурсивно, что даёт наиболее распространённый вариант т. н. алгоритма Кули – Тьюки быстрого преобразования Фурье. С алгебраической точки зрения конструкция Ланцоша – Даниельсона состоит в том, что для вычисления многочлена ${\displaystyle P^{n-1}(t)}$ на множестве всех корней из единицы степени ${\displaystyle n}$ нужно сгруппировать в многочлене ${\displaystyle P^{n-1}(t)}$ отдельно члены чётной и нечётной степеней и представить ${\displaystyle P^{n-1}(t)}$ как ${\displaystyle P_{\text{чет}}^{n/2-1}(t^{2})+tP_{\text{нечет}}^{n/2-1}(t^{2}),}$ далее разбить множество корней из ${\displaystyle 1}$ степени ${\displaystyle n}$ на ${\displaystyle n/2}$ пар вида ${\displaystyle (-w,w),}$ вычислить для каждой пары значения ${\displaystyle \alpha =P_{\text{чет}}^{n/2-1}(w^{2}),}$ ${\displaystyle \beta =P_{\text{нечет}}^{n/2-1}(w^{2})}$ двух многочленов степени ${\displaystyle n/2-1}$ в точке ${\displaystyle w^{2}}$ и, наконец, получить искомую пару значений ${\displaystyle (P^{n-1}(w),P^{n-1}(-w)),}$ вычислив однократно бабочку Фурье пары ${\displaystyle (\alpha ,\beta )}$ с множителем ${\displaystyle w}$.