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

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

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

Предыстория [ править ]

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

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

Общие методы [ править ]

Правило Горнера [ править ]

Метод Хорнера оценивает полином, используя повторяющиеся скобки:

{\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}}

Этот метод сокращает количество умножений и сложений до всего

n

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

Многомерный [ править ]

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

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

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

{\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]

Схема Эстрина [ править ]

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

{\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}}

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

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

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

Пример впервые был приведен Моцкиным. ^[2] кто это заметил

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

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

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

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

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

{\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}}

Пример [ править ]

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

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

Улучшение по эквивалентной форме Горнера (т.е. $P(x)=1+x(1+x(1/2+x(1/6+x/24)))$ ) на 1 умножение.

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

Многоточечная оценка [ править ]

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

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

{\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}}

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

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

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

Динамическая оценка [ править ]

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

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

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

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

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

Оценка полномочий [ править ]

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

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

Полиномиальные семейства [ править ]

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

Жесткие полиномы [ править ]

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

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

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

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

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

Матричные полиномы [ править ]

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

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

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

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

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

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

{\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}}

,

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

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

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}}

.

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

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

См. также [ править ]

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

Ссылки [ править ]

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

[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), «Об аддитивной сложности полиномов и некоторых новых нижних границах», Theoretical Computer Science , Lecture Notes in Computer Science, vol. 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. doi : 10.1016/j.laa.2019.04.001 . ISSN 0024-3795 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]