Умножение n полиномов степени 1

35

Задача состоит в том, чтобы вычислить многочлен . Предположим, что все коэффициенты вписываются в машинное слово, т. Е. Ими можно манипулировать в единицу времени.(a1Икс+б1)××(aNИкс+бN)

Вы можете сделать раз, применяя БПФ в виде дерева. Ты можешь сделать O ( n log n ) ?О(Nжурнал2N)О(NжурналN)

Михай
источник
Хороший вопрос, кажется, я видел нечто подобное в чьем-то блоге, но не могу вспомнить, где это было.
Григорий Ярославцев
3
Незначительное наблюдение: мы знаем (работая над Q, скажем) n корней , поэтому задача эквивалентна: При заданном α 1 , , α n вычислить полином ( x - α 1 ) ( X - α n ) . (Думаю.)αязнак равно-бя/aяα1,...,αN(Икс-α1)...(Икс-αN)
ШриевацаР
1
Можете ли вы дать ссылку на результат ? О(Nжурнал2N)
Мухаммед Аль-Туркистани
2
Как упомянул @Suresh, это простой подход «разделяй и властвуй». Его можно обобщить так, чтобы n полисов могли иметь разные степени , и в этом случае вы можете делить их по дереву Хаффмана. См. Штрассен: Вычислительная сложность непрерывных дробей. dя
Зейю
1
Можем ли мы вычислить свертку из векторов постоянной размерности 2 за время O ( n log n ) ? NО(NжурналN)
Каве

Ответы:

7

Предупреждение: это еще не полный ответ. Если аргументы правдоподобности делают вас неудобными, прекратите читать.

Я рассмотрю вариант, в котором мы хотим умножить (x - a_1) ... (x - a_n) на комплексные числа.

Задача двойственна оценке полинома в n точках. Мы знаем, что это можно сделать умно за O (n log n), когда точки оказываются n-ю корнями единства. Это существенно использует симметрии правильных многоугольников, которые лежат в основе быстрого преобразования Фурье. Это преобразование существует в двух формах, условно называемых «прореживание во времени» и «прореживание по частоте». В основании два они полагаются на двойную пару симметрий четных правильных многоугольников: симметрия взаимосвязи (правильный шестиугольник состоит из двух взаимно соединяющихся равносторонних треугольников) и симметрия разворачивания веера (разрезаем правильный шестиугольник пополам и разворачиваем части как вееры). в равносторонние треугольники).

С этой точки зрения кажется невероятным, что алгоритм O (n log n) будет существовать для произвольного набора из n точек без особых симметрий. Это означало бы, что в правильных многоугольниках нет ничего исключительного в алгоритме по сравнению со случайными наборами точек на комплексной плоскости.

Пер Вогсен
источник
3
С другой стороны, нижняя граница для такой естественной задачи кажется столь же неправдоподобной! Ω(Nжурнал2N)
Джефф
Правда! Хотел бы я иметь более точный ответ. Это очень интересно.
В Вогсен
Награда присуждается!
Джефф
@PerVognsen: Можете ли вы дать ссылку на эту точку зрения относительно: симметрии полигонов / взаимосвязанной симметрии? Или, если это ваше собственное наблюдение, не могли бы вы расширить его?
Джошуа Грохов