Evaluación de polinomios

Algoritmos para la evaluación de polinomios

En matemáticas y ciencias de la computación , la evaluación de polinomios se refiere al cálculo del valor de un polinomio cuando sus indeterminados se sustituyen por algunos valores. En otras palabras, evaluar el polinomio en consiste en calcular Véase también Anillo polinomial § Evaluación polinomial ${\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.}$

Para evaluar el polinomio univariado, el método más ingenuo utilizaría multiplicaciones para calcular , utilizaría multiplicaciones para calcular y así sucesivamente para un total de multiplicaciones y sumas. Si se utilizan métodos mejores, como la regla de Horner , esto se puede reducir a multiplicaciones y sumas. Si se permite algún preprocesamiento, es posible ahorrar aún más. ${\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}$

Fondo

Este problema surge con frecuencia en la práctica. En geometría computacional , se utilizan polinomios para calcular aproximaciones de funciones mediante polinomios de Taylor . En criptografía y tablas hash , se utilizan polinomios para calcular hashes k -independientes .

En el primer caso, los polinomios se evalúan utilizando aritmética de punto flotante , que no es exacta. Por lo tanto, los diferentes esquemas de evaluación darán, en general, respuestas ligeramente diferentes. En el segundo caso, los polinomios suelen evaluarse en un cuerpo finito , en cuyo caso las respuestas son siempre exactas.

Métodos generales

Regla de Horner

El método de Horner evalúa un polinomio usando corchetes repetidos: Este método reduce el número de multiplicaciones y sumas a solo $${\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}$

El método de Horner es tan común que se ha añadido a muchos procesadores una instrucción informática " operación de multiplicación-acumulación ", que permite realizar las operaciones de suma y multiplicación en un paso combinado.

Multivariante

Si el polinomio es multivariado, la regla de Horner se puede aplicar recursivamente sobre algún orden de las variables. Por ejemplo:

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

se puede escribir como

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

Carnicer y Gasca describieron una versión eficiente de este enfoque. ^[1]

El plan de Estrin

Si bien no es posible realizar menos cálculos que con la regla de Horner (sin preprocesamiento), en las computadoras modernas el orden de evaluación puede ser muy importante para la eficiencia computacional. Un método conocido como esquema de Estrin calcula un polinomio (de una sola variable) en un patrón tipo árbol:

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

Combinado con la exponenciación por cuadrado , esto permite paralelizar el cálculo.

Evaluación con preprocesamiento

Los polinomios arbitrarios se pueden evaluar con menos operaciones de las que requiere la regla de Horner si primero "preprocesamos" los coeficientes . ${\displaystyle a_{n},\dots ,a_{0}}$

Un ejemplo lo dio por primera vez Motzkin ^[2], quien señaló que

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

se puede escribir como

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

donde los valores se calculan de forma avanzada, basándose en . El método de Motzkin utiliza solo 3 multiplicaciones en comparación con las 4 de Horner. ${\displaystyle \beta _{0},\dots ,\beta _{3}}$ ${\displaystyle a_{0},\dots ,a_{3}}$

Los valores de cada uno se pueden calcular fácilmente expandiendo e igualando los coeficientes: ${\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}}}$

Ejemplo

Para calcular la expansión de Taylor , podemos aumentar la escala por un factor de 24, aplicar los pasos anteriores y volver a reducirla. Esto nos da el cálculo de tres multiplicaciones ${\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.}$

Mejorando la forma de Horner equivalente (es decir ) por 1 multiplicación. ${\displaystyle P(x)=1+x(1+x(1/2+x(1/6+x/24)))}$

Algunos métodos generales incluyen el algoritmo Knuth-Eve y el algoritmo Rabin-Winograd. ^[3]

Evaluación multipunto

La evaluación de un polinomio de grado n en múltiples puntos se puede realizar con multiplicaciones utilizando el método de Horner . Utilizando el enfoque de preprocesamiento anterior, esto se puede reducir a un factor de dos; es decir, a multiplicaciones. ${\displaystyle P(x)}$ ${\displaystyle x_{1},\dots ,x_{m}}$ ${\displaystyle mn}$ ${\displaystyle m}$ ${\displaystyle mn/2}$

Sin embargo, es posible hacerlo mejor y reducir el requisito de tiempo a solo . ^[4] La idea es definir dos polinomios que sean cero en la primera y segunda mitad de los puntos respectivamente: y . Luego calculamos y usando el teorema del resto polinomial , que se puede hacer en el tiempo usando una transformada rápida de Fourier . Esto significa y por construcción, donde y son polinomios de grado como máximo . Debido a cómo se definieron y , tenemos ${\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}}}$

Por lo tanto, para calcular sobre todos los , basta con calcular los polinomios más pequeños y sobre cada mitad de los puntos. Esto nos da un algoritmo de divide y vencerás con , lo que implica por el teorema maestro . ${\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})}$

En el caso en que los puntos en los que deseamos evaluar los polinomios tengan alguna estructura, existen métodos más simples. Por ejemplo, Knuth ^[5] sección 4.6.4 proporciona un método para tabular valores de polinomios del tipo

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

Evaluación dinámica

En el caso en que no se conocen de antemano, Kedlaya y Umans ^[6] dieron una estructura de datos para evaluar polinomios sobre un campo finito de tamaño en el tiempo por evaluación después de un preprocesamiento inicial. Larsen ^[7] demostró que esto es esencialmente óptimo. ${\displaystyle x_{1},\dots ,x_{m}}$ ${\displaystyle F_{q}}$ ${\displaystyle (\log n)^{O(1)}(\log _{2}q)^{1+o(1)}}$

La idea es transformar de grado en un polinomio multivariado , tal que y los grados individuales de es como máximo . Como esto es sobre , el valor más grande que puede tomar (sobre ) es . Usando el teorema del resto chino , es suficiente evaluar módulo diferentes primos con un producto de al menos . Cada primo puede tomarse como aproximadamente , y el número de primos necesarios, , es aproximadamente el mismo. Haciendo este proceso recursivamente, podemos obtener los primos tan pequeños como . Eso significa que podemos calcular y almacenar en todos los valores posibles en el tiempo y el espacio. Si tomamos , obtenemos , por lo que el requisito de tiempo/espacio es simplemente ${\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}}.}$

Kedlaya y Umans muestran además cómo combinar este preprocesamiento con una evaluación multipunto rápida (FFT). Esto permite algoritmos óptimos para muchos problemas algebraicos importantes, como la composición modular polinómica.

Polinomios específicos

Si bien los polinomios generales requieren operaciones para su evaluación, algunos polinomios se pueden calcular mucho más rápido. Por ejemplo, el polinomio se puede calcular utilizando solo una multiplicación y una suma, ya que ${\displaystyle \Omega (n)}$ ${\displaystyle P(x)=x^{2}+2x+1}$ ${\displaystyle P(x)=(x+1)^{2}}$

Evaluación de competencias

Un tipo de polinomio particularmente interesante son las potencias como . Estos polinomios siempre se pueden calcular en operaciones. Supongamos, por ejemplo, que necesitamos calcular ; simplemente podríamos comenzar con y multiplicar por para obtener . Luego podemos multiplicar eso por sí mismo para obtener y así sucesivamente para obtener y en solo cuatro multiplicaciones. Otras potencias como se pueden calcular de manera similar de manera eficiente calculando primero por 2 multiplicaciones y luego multiplicando por . ${\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}$

La forma más eficiente de calcular una potencia dada es mediante la exponenciación por adición de cadenas . Sin embargo, esto requiere diseñar un algoritmo específico para cada exponente, y los cálculos necesarios para diseñar estos algoritmos son difíciles ( NP-completo ^[8] ), por lo que generalmente se prefiere la exponenciación por cuadrado para cálculos efectivos. ${\displaystyle x^{n}}$

Familias de polinomios

A menudo, los polinomios se presentan en una forma diferente a la conocida . Para polinomios en forma de Chebyshev, podemos utilizar el algoritmo de Clenshaw . Para polinomios en forma de Bézier, podemos utilizar el algoritmo de De Casteljau y, para los B-splines, el algoritmo de De Boor . ${\displaystyle a_{n}x^{n}+\dots +a_{1}x+a_{0}}$

Polinomios duros

El hecho de que algunos polinomios puedan calcularse significativamente más rápido que los "polinomios generales" sugiere la pregunta: ¿Podemos dar un ejemplo de un polinomio simple que no pueda calcularse en un tiempo mucho menor que su grado? Volker Strassen ha demostrado ^[9] que el polinomio

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

no se puede evaluar con menos que multiplicaciones y sumas. Al menos este límite se cumple si solo se permiten operaciones de esos tipos, lo que da lugar a una denominada "cadena polinómica de longitud ". ${\displaystyle {\tfrac {1}{2}}n-2}$ ${\displaystyle n-4}$ ${\displaystyle <n^{2}/\log n}$

El polinomio dado por Strassen tiene coeficientes muy grandes, pero mediante métodos probabilísticos se puede demostrar que deben existir polinomios pares con coeficientes sólo 0 y 1 tales que la evaluación requiera al menos multiplicaciones. ^[10] ${\displaystyle \Omega (n/\log n)}$

En el caso de otros polinomios simples, la complejidad es desconocida. Se supone que el polinomio no se puede calcular en tiempo para ningún . Esto se sustenta en el hecho de que, si se puede calcular rápidamente, entonces la factorización de números enteros se puede calcular en tiempo polinomial, rompiendo el criptosistema RSA . ^[11] ${\displaystyle (x+1)(x+2)\cdots (x+n)}$ ${\displaystyle (\log n)^{c}}$ ${\displaystyle c}$

Polinomios matriciales

A veces, el costo computacional de las multiplicaciones escalares (como ) es menor que el costo computacional de las multiplicaciones "no escalares" (como ). El ejemplo típico de esto son las matrices. Si es una matriz, una multiplicación escalar requiere aproximadamente operaciones aritméticas, mientras que el cálculo requiere aproximadamente (o utilizando la multiplicación rápida de matrices ). ${\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}}$

Los polinomios matriciales son importantes, por ejemplo, para calcular la matriz exponencial .

Paterson y Stockmeyer ^[12] demostraron cómo calcular un polinomio de grado n utilizando únicamente multiplicaciones no escalares y multiplicaciones escalares. De esta manera, un polinomio matricial de grado n puede evaluarse en tiempo. Si esto es , tan rápido como una multiplicación matricial con el algoritmo estándar. ${\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})}$

Este método funciona de la siguiente manera: Para un polinomio

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

sea ​​k el menor entero no menor que Las potencias se calculan con multiplicaciones de matrices, y luego se calculan mediante multiplicación repetida por Ahora, ${\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}}}$,

donde i ≥ n . Esto requiere simplemente más multiplicaciones no escalares . ${\displaystyle a_{i}=0}$ ${\displaystyle k}$

Podemos escribir esto sucintamente usando el producto Kronecker :

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

La aplicación directa de este método utiliza multiplicaciones no escalares, pero al combinarlo con la evaluación con preprocesamiento, Paterson y Stockmeyer muestran que se puede reducir a . ${\displaystyle 2{\sqrt {n}}}$ ${\displaystyle {\sqrt {2n}}}$

Se han propuesto métodos basados ​​en multiplicaciones y adiciones de polinomios matriciales que permiten ahorrar multiplicaciones de matrices no escalares con respecto al método de Paterson-Stockmeyer. ^[13]

Véase también

• Esquema de Estrin para facilitar la paralelización en arquitecturas informáticas modernas
• La teoría de la complejidad del circuito aritmético estudia la complejidad computacional de evaluar diferentes polinomios.

Referencias

1. Carnicer, J.; Gasca, M. (1990). "Evaluación de polinomios multivariados y sus derivadas". Matemáticas de la computación . 54 (189): 231–243. doi : 10.2307/2008692 . JSTOR  2008692.
2. Motzkin, TS (1955). "Evaluación de polinomios y evaluación de funciones racionales". Boletín de la Sociedad Matemática Americana . 61 (163): 10.
3. Rabin, Michael O.; Winograd, Shmuel (julio de 1972). "Evaluación rápida de polinomios mediante preparación racional". Communications on Pure and Applied Mathematics . 25 (4): 433–458. doi :10.1002/cpa.3160250405.
4. Von Zur Gathen, Joaquín ; Jürgen, Gerhard (2013). Álgebra informática moderna . Prensa de la Universidad de Cambridge . Capítulo 10. ISBN 9781139856065.
5. Knuth, Donald (2005). El arte de la programación informática . Vol. 2: Algoritmos seminuméricos. Addison-Wesley . ISBN 9780201853926.
6. Kedlaya, Kiran S. ; Umans, Christopher (2011). "Factorización polinómica rápida y composición modular". Revista SIAM de informática . 40 (6): 1767–1802. doi :10.1137/08073408x. hdl : 1721.1/71792 . S2CID  412751.
7. Larsen, KG (2012). "Límites inferiores de la sonda de celdas superiores para evaluar polinomios". 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science . Vol. 53. IEEE . págs. 293–301. doi :10.1109/FOCS.2012.21. ISBN 978-0-7695-4874-6.S2CID 7906483  .
8. Downey, Peter; Leong, Benton; Sethi, Ravi (1981). "Computing Sequences with Addition Chains". Revista SIAM de Computación . 10 (3) . Consultado el 27 de enero de 2024 .
9. Strassen, Volker (1974). "Polinomios con coeficientes racionales que son difíciles de calcular". Revista SIAM de Informática . 3 (2): 128–149. doi :10.1137/0203010.
10. Schnorr, CP (1979), "Sobre la complejidad aditiva de polinomios y algunos nuevos límites inferiores", Theoretical Computer Science , Lecture Notes in Computer Science, vol. 67, Springer , págs. 286–297, doi :10.1007/3-540-09118-1_30, ISBN 978-3-540-09118-9
11. Chen, Xi, Neeraj Kayal y Avi Wigderson. Derivadas parciales en la complejidad aritmética y más allá. Now Publishers Inc, 2011.
12. Paterson, Michael S. ; Stockmeyer, Larry J. (1973). "Sobre el número de multiplicaciones no escalares necesarias para evaluar polinomios". Revista SIAM de Computación . 2 (1): 60–66. doi :10.1137/0202007.
13. Fasi, Massimiliano (1 de agosto de 2019). "Optimalidad del método de Paterson-Stockmeyer para evaluar polinomios matriciales y funciones matriciales racionales" (PDF) . Álgebra lineal y sus aplicaciones . 574 : 185. doi : 10.1016/j.laa.2019.04.001 . ISSN  0024-3795.