Разъяснение по БПФ - PullRequest
Новая
       203

Разъяснение по БПФ

0 голосов
/ 12 ноября 2009

Я знаю, что со следующими рассуждениями что-то не так, но я не уверен, что это такое.

БПФ:

  1. дано два полинома

    A = a_0 + a_1 x + a_2 x^2 + ... + a_n x^n

    и

    B = b_0 + b_1 x + b_2 x^2 + ... + b_n x^n

    Вы можете рассчитать коэффициенты произведения

    AB = \sum _k = 0 ^ 2n ( \sum _ j = 0 ^ k (a_j b_{k-j}))x^k

    в O(n log n ) времени.

  2. Итак, учитывая два вектора (a_0, ..., a_n) и (b_0, ..., b_n), мы можем вычислить вектор v_i = \sum j = 0 ^ k ( a_j b_{k-j}) во O(n log n) времени (путем вложения векторов в нули.)

  3. Учитывая вышеизложенное, мы должны быть в состоянии вычислить скалярное произведение A =(a_0, ..., a_n) и B =(b_0, ..., b_n), что составляет A.B = \sum_j=0 ^ n a_j b_j за O(n log n) времени, предварительно обработав один из векторов, скажем, B будет B' = (b_n, b_{n-1}, ..., b_1, b_0), затем вычисление свертки, как в 2. в O(n log n) времени.

Если приведенные выше рассуждения верны, то это означает, что мы можем реализовать умножение матриц двух nxn матриц за O(n^2 log n ) время, вычисляя скалярное произведение в O(n log n) раз O(n) раз.

Однако лучшее время выполнения для умножения матриц, которое мы знаем, составляет около O(n^2.4), так что это вряд ли может быть правдой, что, вероятно, означает, что шаги 1,2 или 3 неверны.

Ответы [ 2 ]

4 голосов
/ 12 ноября 2009

В продукте есть n^2 записей, а не n, поэтому этот алгоритм будет O(n^2 * n * log n) = O(n^3 log n).

И лучший алгоритм для вычисления точечных продуктов - O(n), а не O(n log n). Поэтому наивный алгоритм умножения матриц - O(n^3). (Это n^2 точечные продукты, которые можно сделать за O(n) время).

2 голосов
/ 12 ноября 2009

Интересно, почему это достижение, когда на шаге 3 вы можете вычислить скалярное произведение за O (n log n), так как хорошо известно, что скалярное произведение можно рассчитать за O (n) время? Также шаг 2 выглядит как линейное время вместо шага O (n log n)?

Также вывод о O (n ^ 2 log n) не следует логически. Вы не можете взять точечное произведение O (n) раз, получая матрицу AB - насколько я знаю, вы должны взять O (n ^ 2) точечных произведений, что приведет (согласно вашему анализу) к O (n ^). 3 log n), который уступает стандартному O (n ^ 3). Это из-за вашего странного результата O (n log n).

...