Existem algoritmos de exponenciação de matriz paralela que são mais eficientes que a multiplicação sequencial?

É necessário encontrar a potência (número inteiro positivo) da matriz de números reais. Existem muitos algoritmos eficientes de multiplicação de matrizes (por exemplo, alguns algoritmos paralelos são Cannon, DNS ), mas existem algoritmos destinados exatamente a encontrar o poder da matriz e que são mais eficientes do que a execução seqüencial da multiplicação de matrizes? Estou particularmente interessado em algoritmos paralelos.

algorithms parallel-computing efficiency matrices numerical-algorithms Ao Sr
fonte

O que você tentou? Onde você ficou preso? Que pesquisa você fez? Além do título, onde está a pergunta? Para a versão de decisão do seu problema (do título), a resposta é "sim", mas você já sabe, certo?

Mal

@TomR Esta questão provavelmente é do seu interesse

Adriann

Talvez algo assim ? Ou você está procurando algo mais? Quais são os tamanhos e potências em seu aplicativo?

Mal

Você pode calcular a enésima potência com menos de n-1 multiplicações quando n ≥ 4. Para matrizes grandes, geralmente valeria a pena encontrar o menor número possível de multiplicações (por exemplo, existe um método simples para calcular n ^ 15 com 6). multiplicações, mas isso pode ser feito com 5). Você pode aplicar o mesmo princípio para encontrar o menor número de multiplicações seqüenciais, o que será mais difícil.

gnasher729

Você também deve considerar a quantidade de paralelismo disponível para você. "Paralelismo" é sobre a exploração de recursos que, de outra forma, não seriam utilizados. Se uma implementação de multiplicação de matrizes já puder usar todos os recursos disponíveis de forma eficiente, não há mais nada a explorar para calcular os poderes das matrizes.

precisa saber é o seguinte

Respostas:

$M^{15}$

$M^2$

$M^3 = M^2 * M$ $M^4 = M^2 * M^2$

$M^7 = M^4 * M^3$ $M^8 = M^4 * M^4$

$M^{15} = M^8 * M^7$

$M^5$ $M^5$

$M^3$ $M^3$ $M^2$ $M^4$ $M^2$

$M^2 = M * M$ $M^3 = M^2 * M$ $M^2$ $M^3$ $M^2$ $M^3$ $M^4$

$M^{15}$ $M^{1000}$

$M^2$ $M^5$

$M^6$ $M^{25}$ $M^{25}$

$M^{108}$ $M^{125}$ $k (k+1)^2$

gnasher729
fonte

Há dois níveis nos quais você pode analisar acelerações paralelas com exponenciação de matriz: o nível "macro-algorítmico" que decide quais matrizes multiplicar e o nível "micro-algorítmico" onde você pode acelerar as multiplicações com paralelismo.

$n$ $n$ $O(\log^2(n))$ $O(n)$

(Nota: a página da wikipedia é para cálculo geral da matriz. Não tenho certeza se isso pode ser paralelizado ainda mais usando as informações que estamos construindo ao quadrado uma matriz.)

$A^m$ $A$

$A^k$ $O(\log(k))$

A questão é: podemos vencer isso com paralelismo? Eu afirmo que a resposta é não.

A razão simples é que a exponenciação ao quadrado é essencialmente um algoritmo de programação dinâmica; permite que você pule todo o trabalho reutilizando sub-resultados, mas isso, por sua vez, cria uma dependência de dados que não permite o paralelismo. Se nos livrarmos da dependência de dados, mas também aumentamos bastante a quantidade de trabalho que temos que fazer.

$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$

$\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)$

$k$ $O(\log(k))$

No entanto, se realizássemos a exponenciação dessa maneira, ficaria assim:

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

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

$A^2$

$A^k$ $n$ $n$ $A$ $O(\log^2(n)\log(k))$ $O(n\log(k))$

Kurt Mueller
fonte

$m$ $\log m$ $2$ $m$

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
fonte