Como calcular potências de matrizes quadradas?

16

Suponha que recebamos uma matriz e deixe . Quão rápido podemos calcular a potência dessa matriz?ARN×NmN0Am

A próxima melhor coisa em comparação com a computação de produtos é utilizar a exponenciação rápida, que requer produtos da matriz .mO(logm)

Para matrizes diagonalizáveis, a decomposição de autovalor pode ser usada. É generalização natural, decomposição na Jordânia, é instável sob pertubação e, portanto, não conta (afaik).

A exponenciação da matriz no caso geral pode ser acelerada?

A rápida exponenciação sugere que uma variação dessa pergunta também é útil:

O quadrado de uma matriz geral ser calculado mais rapidamente do que por algoritmos de multiplicação de matriz conhecidos?A

shuhalo
fonte
Se você se preocupa com a estabilidade sob perturbações, a exponenciação rápida também não parece segura.
MCH
Bem, suponho que não seja menos seguro que a multiplicação repetida, que é tão segura quanto a exponenciação escalar, não é?
shuhalo

Respostas:

20

Como você observa, o cálculo de pode ser feito em vezes o número de operações para multiplicação de matrizes em matrizes. A resposta para sua segunda pergunta é não, pelo menos para a complexidade assintótica - o quadrado da matriz e a multiplicação da matriz têm uma complexidade aritmética / tempo equivalente (até fatores constantes). Reduzir o quadrado à multiplicação de matrizes é óbvio. Para reduzir a multiplicação de quadratura, suponha que desejamos calcular o produto de e . Forme a matriz com a estrutura de bloco: O ( log m ) N × N A B 2 n × 2 n CUMAmO(logm)N×NUMAB2n×2nC

[0 0  UMA]

[B  0 0]

Ou seja, tem uma matriz todos os zeros no quadrante superior esquerdo e no quadrante inferior direito. Observe que contém no quadrante superior esquerdo.n × n C 2 A BCn×nC2UMAB

Ryan Williams
fonte
Recentemente, eu fiz uma pergunta no cs.SE sobre a complexidade da computação no caso especial em que m = . É fácil atribuir um limite superior , mas o melhor limite inferior que posso fornecer é . Você tem algum comentário sobre esse problema? Eu acho que muitos problemas interessantes se reduzem a esse caso especial. O ( n ) O ( M ( n ) log ( n ) ) Ω ( M ( n ) )UMAmO(n)O(M(n)registro(n))Ω(M(n))
Shitikanth