Existe um algoritmo O (log n) para exponenciação de matriz?

Existe um algoritmo para criar uma matriz para o º poder em tempo? $n$ $O(\log n)$

Estive pesquisando on-line, mas até agora não obtive êxito.

algorithms matrices Jack H
fonte

Quer dizer que você tem uma matriz de tamanho fixo? de fato, se sua matriz é do tamanho

m

$m$ você não pode esperar encontrar

O (l o g n)

$O(log \ n)$ algoritmo.

As pessoas geralmente se referem a esse problema como alimentação de matriz. Exponenciação de matriz significa encontrar

e^{X}

$e^X$

Shitikanth 10/10

@Shitikanth Ok, obrigado. Eu vou mudar isso agora.

Jack H

Respostas:

Aqui está o pseudocódigo para um $O(\lg n)$ algoritmo de exponenciação de matriz. Observe que o operador * indica multiplicação de matriz comum.

MATHPOWER (M, n)
if n == 1
    then return M
else
    P = MATHPOWER (M, floor(n/2))
    if n mod 2 == 0
        then return P * P
    else
        return P * P * M

Massimo Cafaro
fonte

Para quem vem do futuro, esta é uma resposta terrível. Ele funciona O (n ^ 3 * log (n)) quando existem algoritmos O (n ^ 3). Veja a resposta do Yuval abaixo. Como questão prática, isso normalmente é feito por decomposição SVD, elevando os elementos N da matriz D à potência e multiplicando a matriz novamente.

Michael O

@ Michael O, acho que você realmente perdeu o objetivo. Você entendeu mal o que o OP estava pedindo, ou seja, como elevar uma matriz para o

n

$n$ -ésima potência em

O (\lg n) s t e p s

$O(\lg n) steps$ . A chave é que o OP está exigindo apenas que o número de etapas executadas seja

O (\lg n)

$O(\lg n)$ , não a complexidade geral, pois isso exigiria levar em conta também a ordem da matriz.

Massimo Cafaro

É óbvio que a abordagem proposta de dividir e conquistar tem a pior complexidade possível

O (\lg n)

$O(\lg n)$ somente quando a ordem da matriz é

O (1)

$O(1)$ , pois nesse caso a equação de recorrência correspondente é

T (n) = T (n / 2) + O (1)

$T(n) = T(n/2) + O(1)$ (como um exemplo, para uma matriz 3 x 3, é possível fazer uma multiplicação da matriz usando um número constante de multiplicações e adições escalares). Uma possível aplicação do algoritmo que dei, é calcular o

n

$n$ -th número de Fibonacci, atribuindo tarefas à matriz cujas entradas são

a_{11} = 1, a_{12} = 1, a_{21} = 1, a_{22} = 0

$a_{11} = 1, a_{12} = 1, a_{21} = 1, a_{22} = 0$ ao

n

$n$ -th poder.

Massimo Cafaro

Por fim, observe também que isso já foi resolvido e totalmente compreendido: basta dar uma olhada no comentário da pergunta fornecida por @ user742.

Massimo Cafaro

Existem outros dois algoritmos que podem ou não ser relevantes. O primeiro algoritmo diagonaliza sua matriz (o que geralmente é possível), escrevendo-a como $M = PDP^{-1}$ , Onde $M,D$ em geral, podem ter valores complexos. Você então calcula $M=PD^nP^{-1}$ . Observe que é muito fácil elevar uma matriz diagonal para o $n$ poder th. E se $M$ não é diagonalizável, você encontra sua forma Jordan e continua como antes (agora você também precisa calcular alguns coeficientes binomiais). Esse algoritmo provavelmente não é numericamente estável.

Outro algoritmo usa o fato de que $M$ satisfaz seu polinômio característico (ou mesmo seu polinômio mínimo). Suponha $P(M) = 0$ para alguns $P$ , digamos o polinômio característico. Então podemos calcular $M^n$ sobre $\mathbb{R}[M]/(P(M))$ e substitua $M$ . Isso significa que calculamos $M^n$ como um polinômio, usando o fato de que $P(M) = 0$ e apenas no final substitua os valores de $M$ . Poderíamos até pré-calcular todos os poderes necessários para $M$ e todos os valores de $M^k \pmod{P(M)}$ para $k < 2\deg P-1$ , e esse algoritmo pode ser mais rápido que a resposta de Massimo Cafaro. Pode ser mais numericamente estável que o algoritmo anterior.

Yuval Filmus
fonte