Complexidade dos poderes da matriz de computação

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\times n$ $A$ $\mathcal{O}(M(n))$ $A^n$ $\mathcal{O}(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 tempo daria um algoritmo para exponenciação. Porém, vários problemas interessantes se reduzem ao caso especial de exponenciação de matriz em que m = , e não pude provar o mesmo sobre esse problema mais simples. $A^m$ $o(M(n)\log(m))$ $o(\log m)$ $\mathcal O(n)$

algorithms complexity-theory time-complexity computer-algebra Shitikanth
fonte

quais são as entradas da matriz? Inteiros?

Kaveh

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 \pm B)^{2}

$(A\pm B)^2$ ). No entanto, o uso de

{(\begin{array}{cc} 0 & A \\ B & 0 \end{array})}^{2}

$\left( \begin{array}{cc} 0 & A \\ B & 0 \end{array} \right)^2$ funciona. No entanto, isso fornece apenas

Ω (M (n))

$\Omega(M(n))$ na computação de

A^{n}

$A^n$ .

Shitikanth 13/04

Respostas:

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

O (D (n) + n \log n)

$O(D(n)+ n\log n)$ onde

D (n)

$D(n)$ é o tempo para diagonalizar

A

$A$ .

Apenas para completar os detalhes, se $A=P^{-1}DP$ com uma diagonal $D$ , então

A^{n} = (P^{- 1} D P)^{n} = P^{- 1} D^{n} P

$A^n = (P^{-1}DP)^n = P^{-1}D^nP$

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

Tocou.
fonte

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^{3})

$O(n^3)$

O (n^{2.3727} \log (m))

$O(n^{2.3727}\log(m))$

A^{m}

$A^m$

Shitikanth 09/04

(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

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 . $n\times n$ $A$ $A=U\Sigma U^T$ $\Sigma$ $O(n^3)$ $A^m = U \Sigma^m U^T$ $O(n\log m)$ $U \times \Sigma^m \times U^T$ $O(n^{2.3727})$ $O(n^3 + n \log m)$

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(n^{2.3727}+n \log m)$ $o(M(n)\log(m))$ $o(\log n)$

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})

$O(n^{2.3727})$

O (n^{2.3727} \log (m))

$O(n^{2.3727}\log(m))$

A^{m}

$A^m$

m = O (n)

$m=O(n)$

Shitikanth

SVD não dá , em geral, - a matriz lado direito é

A = U Σ U^{⊤}

$A = U \Sigma U^\top$

V \neq U^{⊤}

$V \ne U^\top$

Suresh

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 multiplicadores

n

$n$

m

$m$

n = 1

$n=1$

O (M (1) \log m

$O(M(1)\log m$

A^{m}

$A^m$

PKG

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

\log m

$\log m$

9123 Joe

Isso não ficou claro em sua pergunta, como afirmado.

PKG