Полиномиальная оценка

Алгоритмы полиномиальной оценки

В математике и информатике полиномиальная оценка относится к вычислению значения многочлена, когда его неопределенные значения заменяются некоторыми значениями. Другими словами, оценка полинома at состоит из вычислений. См. также Кольцо полиномов § Полиномиальная оценка. ${\displaystyle P(x_{1},x_{2})=2x_{1}x_{2}+x_{1}^{3}+4}$ ${\displaystyle x_{1}=2,x_{2}=3}$ ${\displaystyle P(2,3)=2\cdot 2\cdot 3+2^{3}+4=24.}$

Для вычисления одномерного многочлена самый наивный метод будет использовать умножение для вычисления , использовать умножение для вычисления и так далее, чтобы получить общее количество умножений и сложений. Используя более совершенные методы, такие как правило Горнера , это можно свести к умножению и сложению. Если разрешена некоторая предварительная обработка, возможна еще большая экономия. ${\displaystyle a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{0},}$ ${\displaystyle n}$ ${\displaystyle a_{n}x^{n}}$ ${\displaystyle n-1}$ ${\displaystyle a_{n-1}x^{n-1}}$ ${\displaystyle {\tfrac {n(n+1)}{2}}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

Фон

Данная проблема часто возникает на практике. В вычислительной геометрии полиномы используются для вычисления аппроксимации функций с использованием полиномов Тейлора . В криптографии и хеш-таблицах полиномы используются для вычисления k -независимого хеширования .

В первом случае полиномы оцениваются с использованием арифметики с плавающей запятой , что не является точным. Таким образом, разные схемы оценки, как правило, дают несколько разные ответы. В последнем случае полиномы обычно оцениваются в конечном поле , и в этом случае ответы всегда точны.

Общие методы

Правило Горнера

Метод Хорнера оценивает полином, используя повторяющиеся скобки: этот метод сокращает количество умножений и сложений до всего $${\displaystyle {\begin{aligned}a_{0}+&a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n}\\&=a_{0}+x{\bigg (}a_{1}+x{\Big (}a_{2}+x{\big (}a_{3}+\cdots +x(a_{n-1}+x\,a_{n})\cdots {\big )}{\Big )}{\bigg )}.\end{aligned}}}$$ ${\displaystyle n}$

Метод Хорнера настолько распространен, что ко многим компьютерным процессорам была добавлена ​​компьютерная инструкция « операция умножения-накопления », которая позволяет выполнять операции сложения и умножения за один комбинированный шаг.

Многомерный

Если полином многомерный, правило Горнера можно применять рекурсивно к некоторому упорядочению переменных. Например

${\displaystyle P(x,y)=4+x+2xy+2x^{2}y+x^{2}y^{2}}$

можно записать как

${\displaystyle {\begin{aligned}P(x,y)&=4+x(1+y(2)+x(y(2+y)))\quad {\text{or}}\\P(x,y)&=4+x+y(x(2+x(2))+y(x^{2})).\end{aligned}}}$

Эффективную версию этого подхода описали Карнисер и Гаска. ^[1]

Схема Эстрина

Хотя невозможно выполнить меньше вычислений, чем по правилу Горнера (без предварительной обработки), на современных компьютерах порядок вычислений может иметь большое значение для эффективности вычислений. Метод, известный как схема Эстрина, вычисляет полином (с одной переменной) в древовидном шаблоне:

$${\displaystyle {\begin{aligned}P(x)=(a_{0}+a_{1}x)+(a_{2}+a_{3}x)x^{2}+((a_{4}+a_{5}x)+(a_{6}+a_{7}x)x^{2})x^{4}.\end{aligned}}}$$

В сочетании с возведением в степень путем возведения в квадрат это позволяет распараллелить вычисления.

Оценка с предварительной обработкой

Произвольные полиномы можно оценить с меньшим количеством операций, чем требует правило Хорнера, если мы сначала «предварительно обработаем» коэффициенты . ${\displaystyle a_{n},\dots ,a_{0}}$

Впервые пример был приведен Моцкиным ^[2], который заметил, что

${\displaystyle P(x)=x^{4}+a_{3}x^{3}+a_{2}x^{2}+a_{1}x+a_{0}}$

можно записать как

${\displaystyle y=(x+\beta _{0})x+\beta _{1},\quad P(x)=(y+x+\beta _{2})y+\beta _{3},}$

где значения вычисляются заранее на основе . Метод Моцкина использует всего 3 умножения по сравнению с 4 умножениями Горнера. ${\displaystyle \beta _{0},\dots ,\beta _{3}}$ ${\displaystyle a_{0},\dots ,a_{3}}$

Значения для каждого можно легко вычислить, разложив и приравняв коэффициенты: ${\displaystyle \beta _{i}}$ ${\displaystyle P(x)}$

${\displaystyle {\begin{aligned}\beta _{0}&={\tfrac {1}{2}}(a_{3}-1),\quad &z&=a_{2}-\beta _{0}(\beta _{0}+1),\quad &\beta _{1}&=a_{1}-\beta _{0}z,\\\beta _{2}&=z-2\beta _{1},\quad &\beta _{3}&=a_{0}-\beta _{1}(\beta _{1}+\beta _{2}).\end{aligned}}}$

Пример

Чтобы вычислить расширение Тейлора , мы можем увеличить масштаб в 24 раза, применить описанные выше шаги и снова уменьшить масштаб. Это дает нам вычисление трех умножения ${\displaystyle \exp(x)\approx 1+x+x^{2}/2+x^{3}/6+x^{4}/24}$

${\displaystyle y=(x+1.5)x+11.625,\quad P(x)=(y+x-15)y/24+2.63477.}$

Улучшение эквивалентной формы Хорнера (то есть ) на 1 умножение. ${\displaystyle P(x)=1+x(1+x(1/2+x(1/6+x/24)))}$

Некоторые общие методы включают алгоритм Кнута – Евы и алгоритм Рабина – Винограда.

Многоточечная оценка

Оценку полинома -степени в нескольких точках можно выполнить с помощью умножения, используя метод Хорнера . Используя описанный выше подход предварительной обработки, это можно уменьшить в два раза, то есть до умножения. Однако можно добиться большего. ${\displaystyle n}$ ${\displaystyle P(x)}$ ${\displaystyle x_{1},\dots ,x_{m}}$ ${\displaystyle mn}$ ${\displaystyle m}$ ${\displaystyle mn/2}$

Можно сократить требуемое время всего до . ^[3] Идея состоит в том, чтобы определить два полинома, которые равны нулю соответственно в первой и второй половине точек: и . Затем мы вычисляем и используем теорему о полиномиальном остатке , что можно сделать вовремя, используя быстрое преобразование Фурье . Это означает и по построению, где и – полиномы степени не выше . Из-за того, как и были определены, мы имеем ${\displaystyle O{\big (}(n+m)\log ^{2}(n+m){\big )}}$ ${\displaystyle m_{0}(x)=(x-x_{1})\cdots (x-x_{n/2})}$ ${\displaystyle m_{1}(x)=(x-x_{n/2+1})\cdots (x-x_{n})}$ ${\displaystyle R_{0}=P{\bmod {m}}_{0}}$ ${\displaystyle R_{1}=P{\bmod {m}}_{1}}$ ${\displaystyle O(n\log n)}$ ${\displaystyle P(x)=Q(x)m_{0}(x)+R_{0}(x)}$ ${\displaystyle P(x)=Q(x)m_{1}(x)+R_{1}(x)}$ ${\displaystyle R_{0}}$ ${\displaystyle R_{1}}$ ${\displaystyle n/2}$ ${\displaystyle m_{0}}$ ${\displaystyle m_{1}}$

${\displaystyle {\begin{aligned}R_{0}(x_{i})&=P(x_{i})\quad {\text{for }}i\leq n/2\quad {\text{and}}\\R_{1}(x_{i})&=P(x_{i})\quad {\text{for }}i>n/2.\end{aligned}}}$

Таким образом, чтобы вычислить все точки , достаточно вычислить меньшие полиномы и каждую половину точек. Это дает нам алгоритм «разделяй и властвуй» с , который следует из основной теоремы . ${\displaystyle P}$ ${\displaystyle n}$ ${\displaystyle x_{i}}$ ${\displaystyle R_{0}}$ ${\displaystyle R_{1}}$ ${\displaystyle T(n)=2T(n/2)+n\log n}$ ${\displaystyle T(n)=O(n(\log n)^{2})}$

В случае, когда точки, в которых мы хотим оценить полиномы, имеют некоторую структуру, существуют более простые методы. Например, в разделе 4.6.4 Кнута ^[4] описан метод табулирования полиномиальных значений типа

${\displaystyle P(x_{0}+h),P(x_{0}+2h),\dots .}$

Динамическая оценка

В случае, когда заранее неизвестно, Кедлая и Уманс ^[5] предоставили структуру данных для оценки полиномов в конечном поле размера во времени за оценку после некоторой начальной предварительной обработки. Ларсен ^[6] показал, что это по существу оптимально. ${\displaystyle x_{1},\dots ,x_{m}}$ ${\displaystyle F_{q}}$ ${\displaystyle (\log n)^{O(1)}(\log _{2}q)^{1+o(1)}}$

Идея состоит в том, чтобы преобразовать степень в многомерный полином , такой, что и отдельные степени не превышают . Поскольку это закончилось , наибольшее значение, которое может принять (более ), равно . Используя китайскую теорему об остатках , достаточно вычислить по модулю различные простые числа с произведением, по крайней мере . Каждое простое число может быть примерно равно , и необходимое количество простых чисел примерно такое же. Выполняя этот процесс рекурсивно, мы можем получить простые числа размером всего . Это означает, что мы можем вычислять и хранить все возможные значения во времени и пространстве. Если мы возьмем , мы получим , поэтому требование времени/пространства просто ${\displaystyle P(x)}$ ${\displaystyle n}$ ${\displaystyle f(x_{1},x_{2},\dots ,x_{m})}$ ${\displaystyle P(x)=f(x,x^{d},x^{d^{2}},\dots ,x^{d^{m}})}$ ${\displaystyle f}$ ${\displaystyle d}$ ${\displaystyle {\bmod {q}}}$ ${\displaystyle f}$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle M=d^{m}(q-1)^{dm}}$ ${\displaystyle f}$ ${\displaystyle p_{1},\dots ,p_{\ell }}$ ${\displaystyle M}$ ${\displaystyle \log M=O(dm\log q)}$ ${\displaystyle \ell }$ ${\displaystyle \log \log q}$ ${\displaystyle f}$ ${\displaystyle T=(\log \log q)^{m}}$ ${\displaystyle d=\log q}$ ${\displaystyle m={\tfrac {\log n}{\log \log q}}}$ ${\displaystyle n^{\frac {\log \log q}{\log \log \log q}}.}$

Кедлайя и Уманс далее показывают, как объединить эту предварительную обработку с быстрой многоточечной оценкой (БПФ). Это позволяет создавать оптимальные алгоритмы для многих важных алгебраических задач, таких как полиномиальная модульная композиция.

Конкретные полиномы

Хотя общие полиномы требуют операций для оценки, некоторые полиномы можно вычислить гораздо быстрее. Например, полином можно вычислить, используя всего одно умножение и одно сложение, поскольку ${\displaystyle \Omega (n)}$ ${\displaystyle P(x)=x^{2}+2x+1}$ ${\displaystyle P(x)=(x+1)^{2}}$

Оценка полномочий

Особенно интересным типом полинома являются такие степени, как . Такие полиномы всегда можно вычислить в операциях. Предположим, например, что нам нужно вычислить ; мы могли бы просто начать с и умножить на, чтобы получить . Затем мы можем умножить это само на себя, чтобы получить и так далее , всего за четыре умножения. Другие степени, например, можно эффективно вычислить, сначала выполнив 2 умножения, а затем умножив на . ${\displaystyle x^{n}}$ ${\displaystyle O(\log n)}$ ${\displaystyle x^{16}}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x^{2}}$ ${\displaystyle x^{4}}$ ${\displaystyle x^{8}}$ ${\displaystyle x^{16}}$ ${\displaystyle x^{5}}$ ${\displaystyle x^{4}}$ ${\displaystyle x}$

Наиболее эффективный способ вычисления заданной степени — возведение в степень по цепочке сложения . Однако это требует разработки специального алгоритма для каждого показателя степени, а вычисления, необходимые для разработки этих алгоритмов, сложны ( NP-полные ^[7] ), поэтому для эффективных вычислений обычно предпочтительнее возводить в степень путем возведения в степень. ${\displaystyle x^{n}}$

Полиномиальные семейства

Часто полиномы появляются в другой форме, чем хорошо известная . Для полиномов в форме Чебышева мы можем использовать алгоритм Кленшоу . Для полиномов в форме Безье можно использовать алгоритм Де Кастельжо , а для B-сплайнов — алгоритм Де Бура . ${\displaystyle a_{n}x^{n}+\dots +a_{1}x+a_{0}}$

Жесткие полиномы

Тот факт, что некоторые многочлены могут быть вычислены значительно быстрее, чем «полиномы общего назначения», наводит на вопрос: можем ли мы привести пример простого многочлена, который не может быть вычислен за время, намного меньшее, чем его степень? Фолькер Штрассен показал ^[8] , что полином

${\displaystyle P(x)=\sum _{k=0}^{n}2^{2^{kn^{3}}}x^{k}}$

не может быть вычислено с помощью меньшего, чем умножения и сложения. По крайней мере, эта граница сохраняется, если разрешены только операции этих типов, что приводит к так называемой «полиномиальной цепочке длины ». ${\displaystyle {\tfrac {1}{2}}n-2}$ ${\displaystyle n-4}$ ${\displaystyle <n^{2}/\log n}$

Полином, заданный Штрассеном, имеет очень большие коэффициенты, но с помощью вероятностных методов можно показать, что должны существовать даже полиномы с коэффициентами только 0 и 1, такие, что оценка требует как минимум умножения. ^[9] ${\displaystyle \Omega (n/\log n)}$

Для других простых многочленов сложность неизвестна. Предполагается, что полином не вычислим во времени ни для какого . Это подтверждается тем фактом, что если его можно вычислить быстро, то факторизацию целых чисел можно вычислить за полиномиальное время, нарушая криптосистему RSA . ^[10] ${\displaystyle (x+1)(x+2)\cdots (x+n)}$ ${\displaystyle (\log n)^{c}}$ ${\displaystyle c}$

Матричные полиномы

Иногда вычислительные затраты на скалярные умножения (например, ) меньше, чем вычислительные затраты на «нескалярные» умножения (например , ). Типичным примером этого являются матрицы. Если — матрица, скалярное умножение требует арифметических операций, а вычисления — около (или использования быстрого умножения матриц ). ${\displaystyle ax}$ ${\displaystyle x^{2}}$ ${\displaystyle M}$ ${\displaystyle m\times m}$ ${\displaystyle aM}$ ${\displaystyle m^{2}}$ ${\displaystyle M^{2}}$ ${\displaystyle m^{3}}$ ${\displaystyle m^{2.3}}$

Матричные полиномы важны, например, для вычисления матричной экспоненты .

Патерсон и Стокмейер ^[11] показали, как вычислить полином степени, используя только нескалярные и скалярные умножения. Таким образом, матричный полином степени n можно вычислить во времени. Если это так , то так же быстро, как умножение одной матрицы стандартным алгоритмом. ${\displaystyle n}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O(n)}$ ${\displaystyle O(m^{2.3}{\sqrt {n}}+m^{2}n)}$ ${\displaystyle m=n}$ ${\displaystyle O(m^{3})}$

Этот метод работает следующим образом: для полинома

${\displaystyle P(M)=a_{n-1}M^{n-1}+\dots +a_{1}M+a_{0}I,}$

пусть k будет наименьшим целым числом, не меньшим, чем Степени вычисляются путем матричного умножения, а затем вычисляются путем повторного умножения на Now, ${\displaystyle {\sqrt {n}}.}$ ${\displaystyle M,M^{2},\dots ,M^{k}}$ ${\displaystyle k}$ ${\displaystyle M^{2k},M^{3k},\dots ,M^{k^{2}-k}}$ ${\displaystyle M^{k}.}$

${\displaystyle {\begin{aligned}P(M)=&\,(a_{0}I+a_{1}M+\dots +a_{k-1}M^{k-1})\\+&\,(a_{k}I+a_{k+1}M+\dots +a_{2k-1}M^{k-1})M^{k}\\+&\,\dots \\+&\,(a_{n-k}I+a_{n-k+1}M+\dots +a_{n-1}M^{k-1})M^{k^{2}-k},\end{aligned}}}$,

где для i ≥ n . Для этого требуется просто больше нескалярных умножений. ${\displaystyle a_{i}=0}$ ${\displaystyle k}$

Мы можем кратко записать это, используя произведение Кронекера :

${\displaystyle P(M)={\begin{bmatrix}I\\M\\\vdots \\M^{k-1}\end{bmatrix}}^{T}\left({\begin{bmatrix}a_{0}&a_{1}&a_{2}&\dots \\a_{k}&a_{k+1}&\ddots \\a_{2k}&\ddots \\\vdots \end{bmatrix}}\otimes I\right){\begin{bmatrix}I\\M^{k}\\M^{2k}\\\vdots \end{bmatrix}}}$.

При прямом применении этого метода используются нескалярные умножения, но в сочетании с оценкой и предварительной обработкой, как показывают Патерсон и Стокмейер, это можно уменьшить до . ${\displaystyle 2{\sqrt {n}}}$ ${\displaystyle {\sqrt {2n}}}$

Предложены методы, основанные на умножении и сложении матричных полиномов, позволяющие сэкономить на нескалярных матричных умножениях по отношению к методу Патерсона-Стокмейера. ^[12]

Смотрите также

• Схема Эстрина для облегчения распараллеливания на современных компьютерных архитектурах
• Теория сложности арифметических схем изучает вычислительную сложность вычисления различных полиномов.

Рекомендации

1. Карнисер, Дж.; Гаска, М. (1990). «Оценка многомерных полиномов и их производных». Математика вычислений . 54 (189): 231–243. дои : 10.2307/2008692 . JSTOR  2008692.
2. Моцкин, Т.С. (1955). «Оценка полиномов и оценка рациональных функций». Бюллетень Американского математического общества . 61 (163): 10.
3. Фон Цур Гатен, Иоахим ; Юрген, Герхард (2013). Современная компьютерная алгебра . Издательство Кембриджского университета . Глава 10. ISBN 9781139856065.
4. Кнут, Дональд (2005). Искусство компьютерного программирования . Том. 2: Получисловые алгоритмы. Аддисон-Уэсли . ISBN 9780201853926.
5. Кедлая, Киран С .; Уманс, Кристофер (2011). «Быстрая полиномиальная факторизация и модульная композиция». SIAM Journal по вычислительной технике . 40 (6): 1767–1802. дои : 10.1137/08073408x. hdl : 1721.1/71792 . S2CID  412751.
6. Ларсен, КГ (2012). «Нижние границы зонда высших ячеек для оценки полиномов». 2012 53-й ежегодный симпозиум IEEE по основам информатики . Том. 53. ИИЭР . стр. 293–301. дои : 10.1109/FOCS.2012.21. ISBN 978-0-7695-4874-6. S2CID  7906483.
7. Дауни, Питер; Леонг, Бентон; Сетхи, Рави (1981). «Вычисление последовательностей с помощью цепочек сложения». SIAM Journal по вычислительной технике . 10 (3) . Проверено 27 января 2024 г.
8. Штрассен, Волкер (1974). «Многочлены с рациональными коэффициентами, которые трудно вычислить». SIAM Journal по вычислительной технике . 3 (2): 128–149. дои : 10.1137/0203010.
9. Шнорр, CP (1979), «Об аддитивной сложности полиномов и некоторых новых нижних границах», Теоретическая информатика , Конспекты лекций по информатике, том. 67, Springer , стр. 286–297, номер документа : 10.1007/3-540-09118-1_30, ISBN. 978-3-540-09118-9
10. Чен, Си, Нирадж Каял и Ави Вигдерсон. Частные производные арифметической сложности и не только. Now Publishers Inc, 2011.
11. Патерсон, Майкл С .; Стокмейер, Ларри Дж. (1973). «О количестве нескалярных умножений, необходимых для вычисления многочленов». SIAM Journal по вычислительной технике . 2 (1): 60–66. дои : 10.1137/0202007.
12. Фаси, Массимилиано (1 августа 2019 г.). «Оптимальность метода Патерсона – Стокмейера для оценки матричных полиномов и рациональных матричных функций» (PDF) . Линейная алгебра и ее приложения . 574 : 185. дои : 10.1016/j.laa.2019.04.001 . ISSN  0024-3795.