Complexidade dos poderes da matriz de computação

14

Estou interessado no cálculo do 'th poder de um matriz . Suponha que tenhamos um algoritmo para multiplicação de matrizes que é executado no tempo . Então, pode-se calcular facilmente em . É possível resolver esse problema em menor complexidade de tempo?n × n A O ( M ( n ) ) A n O ( M ( n ) log ( n ) )nn×nAO(M(n))AnO(M(n)log(n))

As entradas da matriz podem, em geral, ser de um semicondutor, mas você pode assumir uma estrutura adicional, se isso ajudar.

Nota: Entendo que, em computação geral, em o (M (n) \ log (m)) o tempo daria um algoritmo o (\ log m) para exponenciação. Porém, vários problemas interessantes se reduzem ao caso especial de exponenciação de matriz em que m = \ mathcal O (n) , e não pude provar o mesmo sobre esse problema mais simples. o ( M ( n ) log ( m ) ) o ( log m ) O ( n )Amo(M(n)log(m))o(logm)O(n)

Shitikanth
fonte
quais são as entradas da matriz? Inteiros?
Kaveh
1
As entradas podem, em geral, ser de um semicondutor, mas você pode assumir uma estrutura adicional, se isso ajudar.
Shitikanth
Não pude obter uma redução da multiplicação para a quadratura do método proposto acima (ou seja, usando (A±B)2 ). No entanto, o uso de (0AB0)2 funciona. No entanto, isso fornece apenas Ω(M(n)) na computação de An .
Shitikanth 13/04

Respostas:

11

Se a matriz é diagonalizáveis em seguida, tendo o n ° de energia pode ser feita em tempo

O(D(n)+nlogn)
onde D(n) é o tempo para diagonalizar A .

Apenas para completar os detalhes, se A=P1DP com uma diagonal D , então

An=(P1DP)n=P1DnP

e Dn pode ser calculado por apenas tendo cada elemento da diagonal (cada valores próprios de A ) para o n ° de energia.

Tocou.
fonte
6
Mesmo que a matriz seja diagonalizável, os algoritmos mais conhecidos para composição automática levam tempo . Usando o algoritmo Coppersmith-Winograd, já temos um algoritmo para calcular . O ( n 2,3727 log ( m ) ) A mO(n3)O(n2.3727log(m))Am
Shitikanth 09/04
1
(1) O tempo limite que você menciona não é da Coppersmith-Winograd (como você provavelmente sabe). (2) Todos os algoritmos dessa forma funcionam apenas para anéis; eles não funcionam para consultas gerais (como você permite na sua pergunta).
Ryan Williams
5

Uma boa saída é SVD de Decomposição de Valor Singular . Dada uma matriz real real de posição completa , o SVD a divide como onde é uma matriz diagonal, no tempo . Pelas propriedades de SVD, , portanto, apenas a matriz diagonal precisa ser exponenciada, e isso pode ser feito no tempo . Realizando a multiplicação final leva , então temos todas as operações . Uma Um = L Σ L T Σ S ( n 3 ) Um m = L Σ m L T S ( n log m ) L × Σ m × L T S ( n 2,3727 ) O ( n 3 + n log m )n×nAA=UΣUTΣO(n3)Am=UΣmUTO(nlogm)U×Σm×UTO(n2.3727)O(n3+nlogm)

Atualizar após comentário O ponto é que, uma vez que o SVD é encontrado, qualquer energia leva apenas para calcular pelo seu próprio algoritmo CW. Mas essa não é sua pergunta. Se realmente houvesse um algoritmo , ele seria convertido imediatamente em um algoritmo para números inteiros. Suspeito que um desses não exista.o ( M ( n ) log ( m ) ) o ( log n )O(n2.3727+nlogm)o(M(n)log(m))o(logn)

PKG
fonte
Como o algoritmo Coppersmith – Winograd encontra o produto de duas matrizes no tempo , já temos um algoritmo para calcular . Estou interessado em saber se isso pode ser aprimorado sem a necessidade de um algoritmo de multiplicação de matrizes melhor, especialmente para . O ( n 2,3727 log ( m ) ) A m m = O ( n )O(n2.3727)O(n2.3727log(m))Amm=O(n)
Shitikanth
1
SVD não dá , em geral, - a matriz lado direito é V L A=UΣUVU
Suresh
1
Também é um pouco enganador ter para o poder, então usarei . Se , deve levar de tempo para encontrar , que é equivalente a números inteiros multiplicadoresm n = 1 O ( M ( 1 ) log m A mnmn=1O(M(1)logmAm
PKG
2
@Shitikanth, consulte ccrwest.org/gordon/jalg.pdf para obter uma pesquisa sobre algoritmos de exponenciação rápida. Em geral, não é possível usar menos que multiplicações. logm
9123 Joe
1
Isso não ficou claro em sua pergunta, como afirmado.
PKG