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

11

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.

Al sr
fuente
1
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
2
@TomR Esta pregunta probablemente sea de su interés
adrianN
1
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
1
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
1
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:

5

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:M15

Etapa 1: CalcularM2

Etapa 2: Calcular yM 4 = M 2M 2M3=M2MM4=M2M2

Etapa 3: Calcular yM 8 = M 4M 4M7=M4M3M8=M4M4

Etapa 4: CalcularM15=M8M7

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 5M5M5

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 2 M 4 M 2M3M3M2M4M2

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 3 = M 2M M 2 M 3 M 2 M 3 M 4M2=MMM3=M2MM2M3M2M3M4

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 1000M15M1000

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 5M2M5

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 25 M 25M6M25M25

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 125 k ( k + 1 ) 2M108M125k(k+1)2

gnasher729
fuente
4

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 .nnO(log2(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).AmA

El algoritmo secuencial para vencer, como se señaló en otras respuestas, es la exponenciación por cuadratura . Esto le permite calcular en multiplicaciones.AkO(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

A1A2A3A4A5...Ak

La forma natural de paralelizar esto es obvia, debe abusar de la asociatividad para realizar multiplicaciones en la primera ronda:k2

(A1A2)(A3A4)(A5A6)...(Ak1Ak)

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.kO(log(k))

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

(AA)(AA)(AA)...(AA)

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.A2

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

Kurt Mueller
fuente
3

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 .log m 2 mmlogm2m

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 . m O ( 1 ) m

A=SΛS1Am=SΛmS1
mO(1)m
nbubis
fuente