Вычисление суммы разреженных полиномов в квадрате за O (n log n) времени?

18

Предположим , что мы имеем полиномы степени не более n , n > m , так что общее число ненулевых коэффициентов равно n (т. е. многочлены редки). Меня интересует эффективный алгоритм вычисления полинома:p1,...,pmnn>mn

ipi(x)2

Поскольку этот многочлен имеет степень не более , размер входных и выходных данных равен O ( n ) . В случае m = 1 мы можем вычислить результат, используя БПФ за время O ( n log n ) . Можно ли это сделать для любого m < n ? Если это имеет какое-то значение, меня интересует особый случай, когда коэффициенты равны 0 и 1, и вычисление должно выполняться по целым числам.2nO(n)m=1O(nlogn)m<n

Обновить. Я понял, что быстрое решение для вышеупомянутого будет означать достижения в быстром умножении матриц. В частности, если , то можно считывать с я к б K J как коэффициент х я + n j в p k ( x )pk(x)=i=1naikxi+j=1nbkjxnjaikbkjxi+nj . Таким образом, вычисление р К ( х ) 2 соответствует вычислению внешнего произведения двух векторов, и вычислению суммы Е к р К ( х ) 2 соответствует вычислению матрицы продукта. Если есть решениеиспользованием времени п ( п , м ) для вычисления Е к р К ( х ) 2 то мы можем умножить два п матрицаразмерностью N матриц в время F ( п 2 , пpk(x)2pk(x)2kpk(x)2f(n,m)kpk(x)2nn , что означает, что f ( n , m ) = O ( n log n ) для m n потребует серьезного прорыва. Но возможно, что f ( n , m ) = n ω / 2 , где ω - текущий показатель умножения матриц. Идеи, кто-нибудь?f(n2,n)f(n,m)=O(nlogn)mnf(n,m)=nω/2ω

Расмус Паг
источник
1
Привет Расмус. Я думаю, что вы намеревались для этого перейти на основной сайт. Это мета-сайт, для вопросов о сайте.
Суреш Венкат

Ответы:

3

Возведение в квадрат многочлена с ненулевыми коэффициентами требует времени O ( x 2 i ), используя обычное умножение на член, поэтому это должно быть предпочтительнее, чем FFT для тех многочленов, где x i < xiO(xi2) . Еслиixi=n, то число полиномов сxiбольшеxi<nlognixi=nxi являетсяO(nlogn, и это потребуется времяO(N 3 / 2 (логп) 1 / 2 )к площади и объединить (как будет остальные полиномы). Это улучшение по сравнению с очевиднойграницейO(mnlogn),когдаmравноΘ(O(n/logn)O(n3/2(logn)1/2)O(mnlogn)m.Θ(n/logn)

mjqxxxx
источник
1
Что меня интересует, так это метод, который вычисляет сумму, не вычисляя каждый член. Выполнение БПФ или посимвольного умножения для каждого продукта будет слишком медленным для приложения, которое я имею в виду.
Расмус Паг
2

Не полный ответ, но может быть полезным.

Предостережение: это работает только в том случае, если поддержка мала.pi2

Для многочлена пусть S q = { i a i0 } будет его опорой, а s q = | S q | быть размером поддержки. Большая часть р я будет разреженным, то есть, будет иметь небольшую поддержку.q=a0+a1x++anxnSq={iai0}sq=|Sq|pi

Существуют алгоритмы умножения разреженных многочленов и b за квазилинейное время на величину поддержки продукта a b , см., Например, http://arxiv.org/abs/0901.4323abab

Носителем является (содержится в) S a + S b , где сумма двух множеств S и T определяется как S + T : = { s + t s S , t T } . Если опоры всех продуктов малы, скажем, линейны по n , то можно просто вычислить продукты и сложить все одночлены.abSa+SbSTS+T:={s+tsS,tT}n

Однако очень легко найти многочлены и b такие, что размер носителя a b является квадратичным по размерам носителя a и b . В этом конкретном приложении мы возводим в квадрат многочлены. Таким образом, вопрос в том , насколько больше S + S по сравнению с S . Обычной мерой для этого является удвоение числа | S + S | / | S | , Существуют множества с неограниченным удваивающим числом. Но если вы можете исключить множества с большим удваивающим числом в качестве поддержки p iabababS+SS|S+S|/|S|pi, тогда вы можете получить быстрый алгоритм для вашей проблемы.

5501
источник
1
Хотя я не знаком с аддитивной комбинаторикой, я думаю, что обобщенные арифметические прогрессии и теорема Фреймана-Рузса касаются множеств с малым удвоением.
Цуёси Ито
@ Цуйоши: Вы правы, я отредактирую свой ответ. Тем не менее, существуют GAP с большой константой удвоения.
5501
Лично я не считаю такой подход многообещающим. (Довольно неточное) значение теоремы Фреймана-Рузсы заключается в том, что | S + S | / | S | мала только в особых случаях, и поэтому часть «Если вы можете исключить множества с большим числом удвоений в качестве опор p_i» является очень большой, если . Однако, как я уже сказал, я не знаком с аддитивной комбинаторикой, и вы должны принять мои слова об этом с недоверием.
Цуёси Ито
Конечно, это работает только в том случае, если приложение (о котором я не знаю) дает хорошую поддержку.
5501
Тогда было бы легче понять, если вы сделаете это предположение более явным в своем ответе. Текущий способ написания предположения в ответе предполагает, что вы считаете, что предположение о небольшом удваивающем числе не имеет большого значения.
Tsuyoshi Ito
2

Просто хотел отметить алгоритм естественного приближения. Это не использует разреженность хотя.

Вы можете использовать случайную последовательность (σi)i[n] Взяв X=iσipi(x) мы можем вычислить X2 за nlogn раз, используя FFT. Тогда EX2=ipi(x)2=S и VX2=O(S). Таким образом, вы можете получитьприближение1+εво времениO(ε2nlogn).

Томас Але
источник
Хороший подход! Но вам не нужно больше повторений, чтобы получить все коэффициенты правильно с высокой вероятностью?
Расмус Паг
@RasmusPagh Правильно, вы, вероятно, получите термин ( n / δ ), если хотите, чтобы все коэффициенты были сохранены с вероятностью 1 - δ . log(n/δ)1δ
Томас Але