¿Existen algoritmos de exponenciación de matriz paralela que sean más eficientes que la multiplicación secuencial?

Se requiere uno para encontrar la potencia (número entero positivo) de la matriz de números reales. Existen muchos algoritmos eficientes de multiplicación de matrices (por ejemplo, algunos algoritmos paralelos son Cannon's, DNS ) pero ¿existen algoritmos que estén destinados exactamente a encontrar el poder de la matriz y que sean más eficientes que la ejecución secuencial de la multiplicación de matrices? Estoy particularmente interesado en algoritmos paralelos.

algorithms parallel-computing efficiency matrices numerical-algorithms Al sr
fuente

Que has intentado ¿Dónde te quedaste atascado? ¿Qué investigación has hecho? Además del título, ¿dónde está la pregunta? Para la versión de decisión de su problema (del título), la respuesta es "sí", pero ya lo sabe, ¿verdad?

Mal

@TomR Esta pregunta probablemente sea de su interés

adrianN

Tal vez algo como esto ? ¿O estás buscando algo más? ¿Cuáles son los tamaños y poderes en su aplicación?

Mal

Puede calcular la enésima potencia con menos de n-1 multiplicaciones cuando n ≥ 4. Para matrices grandes, normalmente valdría la pena encontrar la menor cantidad posible de multiplicaciones (por ejemplo, hay un método simple para calcular n ^ 15 con 6 multiplicaciones, pero se puede hacer con 5). Luego puede aplicar el mismo principio para encontrar el número más pequeño de multiplicaciones secuenciales, lo que será más difícil.

gnasher729

También debe considerar la cantidad de paralelismo disponible para usted. El "paralelismo" se trata de explotar recursos que de otro modo no se utilizarían. Si una implementación de la multiplicación de matrices ya puede utilizar todos los recursos disponibles de manera eficiente, entonces no hay nada más que explotar para calcular los poderes de las matrices.

gnasher729

Respuestas:

Si tiene múltiples procesadores que pueden funcionar en paralelo, puede calcular cualquier potencia hasta la potencia (2 ^ k) en k pasos. Por ejemplo: Para calcular , calcula: $M^{15}$

Etapa 1: Calcular $M^2$

Etapa 2: Calcular y $M^3 = M^2 * M$ $M^4 = M^2 * M^2$

Etapa 3: Calcular y $M^7 = M^4 * M^3$ $M^8 = M^4 * M^4$

Etapa 4: Calcular $M^{15} = M^8 * M^7$

Esta es una multiplicación más que calcular en tres multiplicaciones y elevar a la tercera potencia en otras dos multiplicaciones, pero debería ser más rápido si tiene dos procesadores. Para altas potencias arbitrarias, necesitará más procesadores. $M^5$ $M^5$

Si usa un algoritmo de fuerza bruta para la multiplicación, multiplicando fila por columna, puede ahorrar algo de tiempo calculando una fila de un producto, y luego usando esa fila inmediatamente para el siguiente producto. Esto ayudaría en el cálculo de donde podemos comenzar a calcular tan pronto como se haya calculado la primera fila de ; no sería tan útil con ya que necesitamos tanto filas como columnas de . Para grandes potencias, probablemente podría organizar qué potencias calcular. $M^3$ $M^3$ $M^2$ $M^4$ $M^2$

Y después de la publicación de esta se hace evidente que se pueden utilizar varios procesadores muy fácilmente: Se empieza por calcular la primera fila de . Cuando tiene esa fila, tiene toda la información que necesita para calcular la primera fila de , por lo que calcula la segunda fila de y la primera fila de en paralelo. Luego puede calcular la tercera fila de , la segunda fila de y la primera fila de en paralelo y así sucesivamente. $M^2 = M * M$ $M^3 = M^2 * M$ $M^2$ $M^3$ $M^2$ $M^3$ $M^4$

Esto hará muchas más operaciones de las necesarias (por ejemplo, 14 multiplicaciones matriciales para lugar del mínimo 5 o 6 del método de cuatro etapas). Si la potencia no es grande en comparación con la cantidad de procesadores, esto seguirá siendo más rápido. Pero calcular con cuatro procesadores usando este método será ineficiente; hacer esto de manera óptima sería un problema interesante. $M^{15}$ $M^{1000}$

Combinación de enfoques: utilizando cuatro procesadores, por ejemplo, puede calcular AB, ABC, ABCD y ABCDE casi en paralelo calculando cada producto una fila a la vez. Esto permite calcular los cuatro a utilizando cuatro procesadores en aproximadamente el mismo tiempo que un producto con un procesador. $M^2$ $M^5$

Dados estos cuatro resultados y la M original, puede calcular cuatro de las matrices a al mismo tiempo nuevamente, siempre que las matrices tengan como máximo cinco potencias separadas entre sí. Por lo tanto, cada potencia hasta se puede calcular en aproximadamente el doble del tiempo de un solo producto de matriz de procesador. $M^6$ $M^{25}$ $M^{25}$

Con estas matrices calculadas, todas las matrices hasta y algunas más hasta se pueden calcular en tres veces el tiempo de un producto de matriz única si hay cuatro procesadores disponibles. Con los procesadores k esto debería subir al menos a la potencia . $M^{108}$ $M^{125}$ $k (k+1)^2$

gnasher729
fuente

Hay dos niveles que puede analizar aceleraciones paralelas con exponenciación de matrices: el nivel "macro-algorítmico" que decide qué matrices multiplicar, y el nivel "micro-algorítmico" donde puede acelerar las multiplicaciones con paralelismo.

Para este último, Wikipedia sugiere que para multiplicar una matriz por , podemos lograr una complejidad de teóricamente con un número ilimitado de procesadores, u con un algoritmo paralelo más realista . $n$ $n$ $O(\log^2(n))$ $O(n)$

(Nota: la página de wikipedia es para computación matricial general. No estoy seguro de si eso se puede paralelizar aún más usando la información de que estamos cuadrando una matriz).

Para el primero, la pregunta se convierte en cuántas rondas de multiplicación de matrices son necesarias para calcular para alguna matriz ? (Digo rondas, porque todas las multiplicaciones en una ronda dada pueden hacerse en paralelo). $A^m$ $A$

El algoritmo secuencial para vencer, como se señaló en otras respuestas, es la exponenciación por cuadratura . Esto le permite calcular en multiplicaciones. $A^k$ $O(\log(k))$

La pregunta es: ¿podemos vencer esto con paralelismo? Afirmo que la respuesta es no.

La razón simple es que la exponenciación por cuadratura es esencialmente un algoritmo de programación dinámico; le permite omitir todo el trabajo reutilizando subresultados, pero esto a su vez crea una dependencia de datos que no permite el paralelismo. Si nos deshacemos de la dependencia de datos, pero también aumentamos enormemente la cantidad de trabajo que tenemos que hacer.

Para ilustrar mejor esto, veamos cómo paralelizaría la multiplicación de matrices si no estuviéramos haciendo exponenciación. Suponga que busca paralelizar multiplicando matrices cuadradas separadas : $k$

A_{1} A_{2} A_{3} A_{4} A_{5} . . . A_{k}

$A_1 A_2 A_3 A_4 A_5 ... A_k$

La forma natural de paralelizar esto es obvia, debe abusar de la asociatividad para realizar multiplicaciones en la primera ronda: $\frac{k}{2}$

(A_{1} A_{2}) (A_{3} A_{4}) (A_{5} A_{6}) . . . (A_{k - 1} A_{k})

$(A_1 A_2)(A_3 A_4)(A_5 A_6) ... (A_{k-1}A_k)$

A partir de esto, podemos multiplicar claramente nuestras matrices en rondas de multiplicación porque reducimos el tamaño del problema a la mitad en cada ronda. $k$ $O(\log(k))$

Sin embargo, si realizáramos la exponenciación de esta manera, se vería así:

(A A) (A A) (A A) . . . (A A)

$(A A)(A A)(A A)...(A A)$

En otras palabras, todo nuestro paralelismo nos está haciendo volver a calcular el mismo producto matricial para calcular . Por lo tanto, si utilizamos un algoritmo memorizado como Exponenciación por cuadratura, podemos hacer lo mismo que el algoritmo paralelo en cada ronda de multiplicación. $A^2$

En conjunto, si queremos calcular para por matriz , la complejidad paralela es para el algoritmo paralelo optimista u para el realista. $A^k$ $n$ $n$ $A$ $O(\log^2(n)\log(k))$ $O(n\log(k))$

Kurt Mueller
fuente

Si por secuencial quieres decir multiplicar veces, la solución de calcular inicialmente solo las potencias relevantes de (también conocido como Exponenciación por cuadratura ) es claramente mejor para grandes . $m$ $\log m$ $2$ $m$

Mejorar eso puede ser específico para ciertos tipos de matrices. Por ejemplo, si su matriz es diagonalizable, Por lo tanto, el cálculo de la ésima potencia es en .

A = S Λ S^{- 1} \to A^{m} = S Λ^{m} S^{- 1}

$A = S \Lambda S^{-1} \rightarrow A^m = S \Lambda^m S^{-1}$

m

$m$

O (1)

$O(1)$

m

$m$

nbubis
fuente