Hispanopedia Wiki
Articulo de referencia

El plan de Estrin

En análisis numérico , el esquema de Estrin (en honor a Gerald Estrin ), también conocido como método de Estrin , es un algoritmo para la evaluación numérica de polinomios . El ...

Hispanopedia WikiContenido en espanolLectura gratuita

En análisis numérico , el esquema de Estrin (en honor a Gerald Estrin ), también conocido como método de Estrin , es un algoritmo para la evaluación numérica de polinomios .

El método de Horner para la evaluación de polinomios es uno de los algoritmos más utilizados para este fin y, a diferencia del método de Estrin, es óptimo en el sentido de que minimiza el número de multiplicaciones y sumas necesarias para evaluar un polinomio arbitrario. Sin embargo, cada operación depende de la anterior, por lo que no puede aprovechar la capacidad de los procesadores modernos para realizar múltiples operaciones independientes en paralelo. El método de Estrin intenta superar esta serialización, manteniéndose a una distancia razonable de la optimización.

Descripción del algoritmo

El esquema de Estrin opera recursivamente , convirtiendo un polinomio de grado n en x (para n ≥2) en un polinomio de grado ⌊ n /2 ⌋ en x 2 usando ⌈ n /2 ⌉ operaciones independientes (más una para calcular x 2 ).

Dado un polinomio arbitrario P ( x ) = C 0 + C 1 x + C 2 x 2 + C 3 x 3 + ⋯ + C n x n , se pueden agrupar términos adyacentes en subexpresiones de la forma ( A  + Bx ) y reescribirlo como un polinomio en x 2 : P ( x ) = ( C 0 + C 1 x ) + ( C 2 + C 3 x ) x 2 + ( C 4 + C 5 x ) x 4 + ⋯ = Q ( x 2 ). 

Cada una de estas subexpresiones, y x² , pueden calcularse en paralelo. También pueden evaluarse mediante una instrucción nativa de multiplicación y acumulación en algunas arquitecturas, una ventaja que comparte con el método de Horner .

Esta agrupación se puede repetir para obtener un polinomio en x 4 : P ( x ) = Q ( x 2 ) = (( C 0 + C 1 x ) + ( C 2 + C 3 x ) x 2 ) + (( C 4 + C 5 x ) + ( C 6 + C 7 x ) x 2 ) x 4 + ⋯ = R ( x 4 ).

Al repetir esto ⌊ log 2 n ⌋ +1 veces, se llega al esquema de Estrin para la evaluación paralela de un polinomio:

  1. Calcula D i = C 2 i + C 2 i +1 x para todo 0  ≤ i ≤ ⌊ n /2 ⌋ . (Si n es par, entonces C n +1 = 0 y D n /2 = C n .)       
  2. Si n  ≤  1, el cálculo ha finalizado y D 0 es la respuesta final.
  3. De lo contrario, calcule y = x 2 (en paralelo con el cálculo de D i ).
  4. Evalúe Q ( y ) = D 0 + D 1 y + D 2 y 2 + ⋯ + D ⌊ n /2 ⌋ y ⌊ n /2 ⌋ utilizando el esquema de Estrin.

Esto realiza un total de n operaciones de multiplicación y acumulación (igual que el método de Horner) en la línea 1, y ⌊ log 2 n ⌋ elevaciones al cuadrado adicionales en la línea 3. A cambio de esas elevaciones al cuadrado adicionales, todas las operaciones en cada nivel del esquema son independientes y pueden calcularse en paralelo; la ruta de dependencia más larga es de ⌊ log 2 n ⌋ +1 operaciones. Una idea similar [ 1 ] permite que un algoritmo rápido de multiplicación de matrices evalúe un polinomio en una serie de puntos.

Ejemplos

Consideremos P n ( x ) como el polinomio de orden n de la forma: P n ( x ) = C 0 + C 1 x + C 2 x 2 + C 3 x 3 + ⋯ + C n x n 

Escrito con el esquema de Estrin tenemos:

P 3 ( x ) = ( C 0 + C 1 x ) + ( C 2 + C 3 x ) x 2
P 4 ( x ) = ( C 0 + C 1 x ) + ( C 2 + C 3 x ) x 2 + C 4 x 4
P 5 ( x ) = ( C 0 + C 1 x ) + ( C 2 + C 3 x ) x 2 + ( C 4 + C 5 x ) x 4
P 6 ( x ) = ( C 0 + C 1 x ) + ( C 2 + C 3 x ) x 2 + (( C 4 + C 5 x ) + C 6 x 2 ) x 4
P 7 ( x ) = ( C 0 + C 1 x ) + ( C 2 + C 3 x ) x 2 + (( C 4 + C 5 x ) + ( C 6 + C 7 x ) x 2 ) x 4
P 8 ( x ) = ( C 0 + C 1 x ) + ( C 2 + C 3 x ) x 2 + (( C 4 + C 5 x ) + ( C 6 + C 7 x ) x 2 ) x 4 + C 8 x 8
P 9 ( x ) = ( C 0 + C 1 x ) + ( C 2 + C 3 x ) x 2 + (( C 4 + C 5 x ) + ( C 6 + C 7 x ) x 2 ) x 4 + ( C 8 + C 9 x ) x 8
…

Consideremos con todo detalle la evaluación de P 15 ( x ):

Entradas : x , C0 , C1 , C2 , C3 , C4 , C5 , C6 , C7 , C8 , C9 , C10 , C11 , C12 , C13 , C14 , C15​​​​​​​​​​​​
Paso 1: x 2 , C 0 + C 1 x , C 2 + C 3 x , C 4 + C 5 x , C 6 + C 7 x , C 8 + C 9 x , C 10 + C 11 x , C 12 + C 13 x , C 14 + C 15 x
Paso 2: x 4 , ( C 0 + C 1 x ) + ( C 2 + C 3 x ) x 2 , ( C 4 + C 5 x ) + ( C 6 + C 7 x ) x 2 , ( C 8 + C 9 x ) + ( C 10 + C 11 x ) x 2 , ( C 12 + C 13 x ) + ( C 14 + C 15 x ) x 2
Paso 3: x 8 , (( C 0 + C 1 x ) + ( C 2 + C 3 x ) x 2 ) + (( C 4 + C 5 x ) + ( C 6 + C 7 x ) x 2 ) x 4 , (( C 8 + C 9 x ) + ( C 10 + C 11 x ) x 2 ) + (( C 12 + C 13 x ) + ( C 14 + C 15 x ) x 2 ) x 4
Paso 4: ((( C 0 + C 1 x ) + ( C 2 + C 3 x ) x 2 ) + (( C 4 + C 5 x ) + ( C 6 + C 7 x ) x 2 ) x 4 ) + ((( C 8 + C 9 x ) + ( C 10 + C 11 x ) x 2 ) + (( C 12 + C 13 x ) + ( C 14 + C 15 x ) x 2 ) x 4 ) x 8

En combinación con el método de Horner

El esquema completo de Estrin utiliza un gran número de operaciones de multiplicación y acumulación en el primer paso. Si bien esto resulta útil para aprovechar al máximo los procesadores superescalares modernos , eventualmente excederá los recursos computacionales disponibles, momento en el que podría ser útil utilizar el esquema de Estrin con una profundidad limitada y, posteriormente, el método de Horner sobre el residuo.

Por ejemplo, si una computadora puede realizar cuatro operaciones de multiplicación y acumulación antes de que esté disponible el resultado de la primera operación, entonces dos niveles del esquema de Estrin mantendrán su canalización de instrucciones llena. En cada iteración, puede realizar las siguientes operaciones en paralelo:

Nivel 1: (Estrin) Calcula D 2 i = C 4 i + C 4 i +1 x y D 2 i +1 = C 4 i +2 + C 4 i +3 x
Nivel 2: (Estrin) Calcular E i +1 = D 2 i +2 + D 2 i +3 x 2
Nivel 3: (Horner) Calcula F i +2 = E i +2 + F i +3 x 4

El resultado final es F 0 .

Un procesador más potente podría ser capaz de realizar cuatro operaciones SIMD de 4 operandos simultáneamente, en cuyo caso se podrían utilizar cuatro niveles del esquema de Estrin para evaluar un polinomio de grado suficientemente alto.

Referencias

  1. ↑ Borodin, Allan ; Munro, Ian (1971). "Evaluación de polinomios en muchos puntos" (PDF) . Information Processing Letters . 1 (2): 66– 68. doi : 10.1016/0020-0190(71)90009-3 .
  • Estrin, Gerald (mayo de 1960). "Organización de sistemas informáticos: El ordenador de estructura fija más variable" (PDF) . IRE-AIEE-ACM '60 (Western): Artículos presentados en la conferencia conjunta de informática IRE-AIEE-ACM del oeste, del 3 al 5 de mayo de 1960. San Francisco. pp. 33–40 . doi : 10.1145/1460361.1460365 . S2CID 16384320 .  
  • Muller, Jean-Michel (2005). Funciones elementales: algoritmos e implementación (2.ª  ed.). Birkhäuser. p.  58. ISBN 0-8176-4372-9.

Lecturas adicionales

  • Moroz, Guillaume (julio de 2013). Evaluación y composición rápida de polinomios (Informe técnico). v3. INRIA . arXiv : 1307.5655 . RT-0453. El esquema descrito está implementado para SageMath en el paquete para evaluación rápida de polinomios en Wayback Machine (archivado el 07-02-2023) .