Evaluación polinómica

En matemáticas e informática , la evaluación de polinomios se refiere al cálculo del valor de un polinomio cuando sus indeterminadas se sustituyen por algunos valores. En otras palabras, evaluar el polinomio $P(x_{1},x_{2})=2x_{1}x_{2}+x_{1}^{3}+4$ en $x_{1}=2,x_{2}=3$ consiste en computación $P(2,3)=2\cdot 2\cdot 3+2^{3}+4=24.$ Véase también Anillo de polinomios § Evaluación de polinomios

Para evaluar el polinomio univariado $a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{0},$ El método más ingenuo sería utilizar $n$ multiplicaciones para calcular $a_{n}x^{n}$ , usar $n-1$ multiplicaciones para calcular $a_{n-1}x^{n-1}$ y así sucesivamente para un total de ${\tfrac {n(n+1)}{2}}$ multiplicaciones y $n$ adiciones. Utilizando mejores métodos, como la regla de Horner , esto se puede reducir a $n$ multiplicaciones y $n$ Adiciones. Si se permite algún preprocesamiento, es posible obtener aún más ahorros.

Fondo

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

En el primer caso, los polinomios se evalúan mediante aritmética de punto flotante , que no es exacta . Por lo tanto, diferentes métodos de evaluación generalmente darán resultados ligeramente distintos. En el segundo caso, los polinomios se evalúan habitualmente en un cuerpo finito , en cuyo caso los resultados son siempre exactos.

Métodos generales

La regla de Horner

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

El método de Horner es tan común que la " operación de multiplicación y acumulación " está incluida en el conjunto de instrucciones de muchos procesadores informáticos, lo que permite realizar las operaciones de suma y multiplicación en un solo paso combinado.

Multivariado

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

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

se puede escribir como

{\begin{aligned}P(x,y)&=4+x(1+y(2)+x(y(2+y)))\quad {\text{o}}\\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 crucial para la eficiencia computacional. Un método conocido como el esquema de Estrin calcula un polinomio (de una sola variable) siguiendo un patrón de árbol:

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

Combined by exponentiation by squaring, this allows parallelizing the computation. A similar idea^[2] enables to involve fast matrix multiplication algorithms to evaluate a polynomial in a series of points.

Evaluation with preprocessing

Arbitrary polynomials can be evaluated with fewer operations than Horner's rule requires if we first "preprocess" the coefficients $a_{n},\dots ,a_{0}$ .

An example was first given by Motzkin^[3] who noted that

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

can be written as

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

where the values $\beta _{0},\dots ,\beta _{3}$ are computed in advance, based on $a_{0},\dots ,a_{3}$ . Motzkin's method uses just 3 multiplications compared to Horner's 4.

The values for each $\beta _{i}$ can be easily computed by expanding $P(x)$ and equating the coefficients:

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

Example

To compute the Taylor expansion $\exp(x)\approx 1+x+x^{2}/2+x^{3}/6+x^{4}/24$ , we can upscale by a factor 24, apply the above steps, and scale back down. That gives us the three multiplication computation

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

Improving over the equivalent Horner form (that is $P(x)=1+x(1+x(1/2+x(1/6+x/24)))$ ) by 1 multiplication.

Some general methods include the Knuth–Eve algorithm and the Rabin–Winograd algorithm. ^[4]

Multipoint evaluation

Evaluation of a degree-n polynomial $P(x)$ at multiple points $x_{1},\dots ,x_{m}$ can be done with $mn$ multiplications by using Horner's method $m$ times. Using the above preprocessing approach, this can be reduced by a factor of two; that is, to $mn/2$ multiplications.

However, it is possible to do better and reduce the time requirement to just $O{\big (}(n+m)\log ^{2}(n+m){\big )}$ .^[5] The idea is to define two polynomials that are zero in respectively the first and second half of the points: $m_{0}(x)=(x-x_{1})\cdots (x-x_{n/2})$ and $m_{1}(x)=(x-x_{n/2+1})\cdots (x-x_{n})$ . We then compute $R_{0}=P{\bmod {m}}_{0}$ and $R_{1}=P{\bmod {m}}_{1}$ using the Polynomial remainder theorem, which can be done in $O(n\log n)$ time using a fast Fourier transform. This means $P(x)=Q_{0}(x)m_{0}(x)+R_{0}(x)$ and $P(x)=Q_{1}(x)m_{1}(x)+R_{1}(x)$ by construction, where $R_{0}$ and $R_{1}$ are polynomials of degree at most $n/2$ . Because of how $m_{0}$ and $m_{1}$ were defined, we have

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

Thus to compute $P$ on all $n$ of the $x_{i}$ , it suffices to compute the smaller polynomials $R_{0}$ and $R_{1}$ on each half of the points. This gives us a divide-and-conquer algorithm with $T(n)=2T(n/2)+n\log n$ , which implies $T(n)=O(n(\log n)^{2})$ by the master theorem.

In the case where the points in which we wish to evaluate the polynomials have some structure, simpler methods exist. For example, Knuth^[6] section 4.6.4 gives a method for tabulating polynomial values of the type

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

Dynamic evaluation

In the case where $x_{1},\dots ,x_{m}$ are not known in advance, Kedlaya and Umans^[7] gave a data structure for evaluating polynomials over a finite field of size $F_{q}$ in time $(\log n)^{O(1)}(\log _{2}q)^{1+o(1)}$ por evaluación después de un preprocesamiento inicial. Larsen ^{[ 8 ]} demostró que esto era esencialmente óptimo.

La idea es transformar $P(x)$ de grado $n$ en un polinomio multivariado $f(x_{1},x_{2},\dots ,x_{m})$ , de tal manera que $P(x)=f(x,x^{d},x^{d^{2}},\dots ,x^{d^{m}})$ y los grados individuales de $f$ es como máximo $d$ . Dado que esto ha terminado ${\bmod {q}}$ , el mayor valor $f$ puede tomar (más de $\mathbb {Z}$ ) es $M=d^{m}(q-1)^{dm}$ . Utilizando el teorema chino del resto , basta con evaluar $f$ módulo diferentes primos $p_{1},\dots ,p_{\ell }$ con un producto al menos $M$ Cada número primo puede considerarse aproximadamente igual a... $\log M=O(dm\log q)$ y el número de primos necesarios, $\ell$ es aproximadamente lo mismo. Al realizar este proceso recursivamente, podemos obtener primos tan pequeños como $\log \log q$ Eso significa que podemos calcular y almacenar $f$ en todos los valores posibles en $T=(\log \log q)^{m}$ tiempo y espacio. Si tomamos $d=\log q$ , obtenemos $m={\tfrac {\log n}{\log \log q}}$ , por lo que el requisito de tiempo/espacio es $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 mediante la transformada rápida de Fourier. Esto permite obtener algoritmos óptimos para muchos problemas algebraicos importantes, como la composición modular polinomial .

Polinomios específicos

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

Evaluación de poderes

Un tipo de polinomio particularmente interesante son las potencias como $x^{n}$ . Dichos polinomios siempre se pueden calcular en $O(\log n)$ operaciones. Supongamos, por ejemplo, que necesitamos calcular $x^{16}$ ; podríamos simplemente comenzar con $x$ y multiplicar por $x$ Llegar $x^{2}$ . Luego podemos multiplicarlo por sí mismo para obtener $x^{4}$ y así sucesivamente para obtener $x^{8}$ y $x^{16}$ en tan solo cuatro multiplicaciones. Otras potencias como $x^{5}$ De manera similar, se puede calcular de manera eficiente calculando primero $x^{4}$ por 2 multiplicaciones y luego multiplicando por $x$ .

La forma más eficiente de calcular una potencia determinada $x^{n}$ se proporciona mediante la exponenciación en cadena de adición . Sin embargo, esto requiere diseñar un algoritmo específico para cada exponente, y el cálculo necesario para diseñar estos algoritmos es difícil ( NP-completo ^{[ 9 ]} ), por lo que la exponenciación por cuadrado se prefiere generalmente para cálculos efectivos.

Familias de polinomios

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

Polinomios difíciles

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

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

no se puede evaluar con menos de ${\tfrac {1}{2}}n-2$ multiplicaciones y $n-4$ adiciones. Al menos este límite se cumple si solo se permiten operaciones de esos tipos, dando lugar a una llamada "cadena polinómica de longitud $<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 incluso polinomios con coeficientes solo 0 y 1 tales que la evaluación requiere al menos $\Omega (n/\log n)$ multiplicaciones. ^{[ 11 ]}

Para otros polinomios simples, la complejidad es desconocida. El polinomio $(x+1)(x+2)\cdots (x+n)$ Se conjetura que no es computable en el tiempo $(\log n)^{c}$ para cualquier $c$ Esto se ve respaldado por el hecho de que, si se puede calcular rápidamente, la factorización de enteros se puede calcular en tiempo polinomial, rompiendo el criptosistema RSA . ^{[ 12 ]}

Polinomios matriciales

A veces el costo computacional de las multiplicaciones escalares (como $ax$ ) es menor que el costo computacional de las multiplicaciones "no escalares" (como $x^{2}$ ). El ejemplo típico de esto son las matrices. Si $M$ es un $m\times m$ matriz, una multiplicación escalar $aM$ toma aproximadamente $m^{2}$ operaciones aritméticas, mientras se realizan cálculos $M^{2}$ toma aproximadamente $m^{3}$ (o $m^{2.3}$ utilizando la multiplicación rápida de matrices ).

Los polinomios matriciales se utilizan, por ejemplo, para calcular exponenciales matriciales .

Paterson y Stockmeyer ^{[ 13 ]} mostraron cómo calcular un grado $n$ polinomio usando solo $O({\sqrt {n}})$ multiplicaciones no escalares y $O(n)$ multiplicaciones escalares. Por lo tanto, un polinomio matricial de grado $n$ puede evaluarse en $O(m^{\alpha }{\sqrt {n}}+m^{2}n)$ tiempo, donde $m^{\alpha }$ ⁠ es el tiempo necesario para multiplicar dos ⁠ $m\times m$ ⁠ matices. Si $m=n$ esto es $O(n^{\beta }),$ donde $\beta =3.5$ o $\beta =3$ Dependiendo de si se utiliza la multiplicación de matrices usual o rápida. Esto debe compararse con el método de Horner usual , que da $\beta =4$ o $\beta =3.3$ respectivamente .

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

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

Sea $k$ el menor entero no menor que ${\sqrt {n}}.$ Los poderes $M,M^{2},\dots ,M^{k}$ se calculan con $k$ multiplicaciones de matrices y $M^{2k},M^{3k},\dots ,M^{k^{2}-k}$ luego se calculan mediante multiplicación repetida por $M^{k}.$ Ahora,

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

,

dónde $a_{i}=0$ para $i \geq n$ . Esto requiere simplemente $k$ más multiplicaciones no escalares.

La aplicación directa de este método utiliza $2{\sqrt {n}}$ multiplicaciones no escalares, pero combinándolo con Evaluación con preprocesamiento , Paterson y Stockmeyer muestran que se puede reducir a ${\sqrt {2n}}$ .

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

Véase también

El plan de Estrin para facilitar la paralelización en arquitecturas informáticas modernas.
La teoría de la complejidad de los circuitos aritméticos estudia la complejidad computacional de evaluar diferentes polinomios.

Referencias

↑ 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 .
↑ Borodin, A.; Munro, I (1971). "Evaluación de polinomios en muchos puntos". Information Processing Letters . 1 (2): 66– 68. doi : 10.1016/0020-0190(71)90009-3 .
↑ Motzkin, TS (1955). "Evaluación de polinomios y evaluación de funciones racionales". Boletín de la Sociedad Matemática Americana . 61 (163): 10.
↑ 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 .
↑ Von Zur Gathen, Joaquín ; Jürgen, Gerhard (2013). Álgebra informática moderna . Prensa de la Universidad de Cambridge . Capítulo 10. ISBN 9781139856065.
↑ Knuth, Donald (2005). El arte de la programación informática . Vol. 2: Algoritmos seminuméricos. Addison-Wesley . ISBN 9780201853926.
↑ Kedlaya, Kiran S. ; Umans, Christopher (2011). "Fast Polynomial Factorization and Modular Composition" . SIAM Journal on Computing . 40 (6): 1767– 1802. doi : 10.1137/08073408x . hdl : 1721.1/71792 . S2CID 412751 .
↑ 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 .
↑ Downey, Peter; Leong, Benton; Sethi, Ravi (1981). "Cálculo de secuencias con cadenas de adición" . SIAM Journal on Computing . 10 (3): 638– 646. doi : 10.1137/0210047 . Consultado el 27 de enero de 2024 .
↑ Strassen, Volker (1974). "Polinomios con coeficientes racionales difíciles de calcular". SIAM Journal on Computing . 3 (2): 128– 149. doi : 10.1137/0203010 .
↑ Schnorr, CP (1979), "Sobre la complejidad aditiva de los polinomios y algunas nuevas cotas inferiores", Theoretical Computer Science , Lecture Notes in Computer Science, vol. 67, Springer , pp. 286–297 , doi : 10.1007/3-540-09118-1_30 , ISBN 978-3-540-09118-9{{citation}}: CS1 mantenimiento: parámetro de trabajo con ISBN ( enlace )
↑ Chen, Xi, Neeraj Kayal y Avi Wigderson. Derivadas parciales en complejidad aritmética y más allá. Now Publishers Inc, 2011.
↑ Paterson, Michael S. ; Stockmeyer, Larry J. (1973). "Sobre el número de multiplicaciones no escalares necesarias para evaluar polinomios". SIAM Journal on Computing . 2 (1): 60– 66. doi : 10.1137/0202007 .
↑ 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 .

[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] Borodin, A.; Munro, I (1971). "Evaluación de polinomios en muchos puntos". Information Processing Letters . 1 (2): 66– 68. doi : 10.1016/0020-0190(71)90009-3 .

[3] Motzkin, TS (1955). "Evaluación de polinomios y evaluación de funciones racionales". Boletín de la Sociedad Matemática Americana . 61 (163): 10.

[4] 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 .

[5] Von Zur Gathen, Joaquín ; Jürgen, Gerhard (2013). Álgebra informática moderna . Prensa de la Universidad de Cambridge . Capítulo 10. ISBN 9781139856065.

[6] Knuth, Donald (2005). El arte de la programación informática . Vol. 2: Algoritmos seminuméricos. Addison-Wesley . ISBN 9780201853926.

[7] Kedlaya, Kiran S. ; Umans, Christopher (2011). "Fast Polynomial Factorization and Modular Composition" . SIAM Journal on Computing . 40 (6): 1767– 1802. doi : 10.1137/08073408x . hdl : 1721.1/71792 . S2CID 412751 .

[8] 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 .

[9] Downey, Peter; Leong, Benton; Sethi, Ravi (1981). "Cálculo de secuencias con cadenas de adición" . SIAM Journal on Computing . 10 (3): 638– 646. doi : 10.1137/0210047 . Consultado el 27 de enero de 2024 .

[10] Strassen, Volker (1974). "Polinomios con coeficientes racionales difíciles de calcular". SIAM Journal on Computing . 3 (2): 128– 149. doi : 10.1137/0203010 .

[11] Schnorr, CP (1979), "Sobre la complejidad aditiva de los polinomios y algunas nuevas cotas inferiores", Theoretical Computer Science , Lecture Notes in Computer Science, vol. 67, Springer , pp. 286–297 , doi : 10.1007/3-540-09118-1_30 , ISBN 978-3-540-09118-9{{citation}}: CS1 mantenimiento: parámetro de trabajo con ISBN ( enlace )

[12] Chen, Xi, Neeraj Kayal y Avi Wigderson. Derivadas parciales en complejidad aritmética y más allá. Now Publishers Inc, 2011.

[13] Paterson, Michael S. ; Stockmeyer, Larry J. (1973). "Sobre el número de multiplicaciones no escalares necesarias para evaluar polinomios". SIAM Journal on Computing . 2 (1): 60– 66. doi : 10.1137/0202007 .

[14] 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 .

[ 1 ]

[2]

[3]

[4]

[5]

[6]

[7]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]