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

Алгоритмы для оценки полиномов

В математике и информатике оценка полинома относится к вычислению значения полинома , когда его неопределенные значения заменяются на некоторые значения. Другими словами, оценка полинома в состоит из вычисления См. также Кольцо полиномов § Оценка полинома ${\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)))}$

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

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

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

Однако можно добиться большего и сократить требуемое время до . ^[4] Идея состоит в том, чтобы определить два многочлена, которые равны нулю соответственно в первой и второй половине точек: и . Затем мы вычисляем и с помощью теоремы об остатках многочленов , что можно сделать за время с помощью быстрого преобразования Фурье . Это означает и по построению, где и являются многочленами степени не выше . Из-за того, как и были определены, мы имеем ${\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})}$

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

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

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

В случае, когда заранее неизвестны, Кедлая и Уманс ^[6] дали структуру данных для оценки полиномов над конечным полем размера за время оценки после некоторой начальной предварительной обработки. Ларсен ^[7] показал, что это по существу оптимально. ${\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-полные ^[8] ), поэтому возведение в степень путем возведения в квадрат обычно предпочтительнее для эффективных вычислений. ${\displaystyle x^{n}}$

Многочленные семейства

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

Жесткие многочлены

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

${\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, такие, что для оценки требуется по крайней мере умножение. ^[10] ${\displaystyle \Omega (n/\log n)}$

Для других простых многочленов сложность неизвестна. Предполагается, что многочлен не может быть вычислен за время для любого . Это подтверждается тем фактом, что если его можно вычислить быстро, то целочисленную факторизацию можно вычислить за полиномиальное время, взломав криптосистему RSA . ^[11] ${\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}}$

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

Патерсон и Стокмейер ^[12] показали, как вычислить полином степени, используя только нескалярные и скалярные умножения. Таким образом, матричный полином степени 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 будет наименьшим целым числом, не меньшим, чем Степени вычисляются с помощью умножения матриц, а затем вычисляются путем повторного умножения на Теперь, ${\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}}}$

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

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

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

Ссылки

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