Casos de sistemas lineares resolvíveis no tempo quase lineares

13

Seja uma matriz real quadrada A e dois vetores x e b de comprimento n , de modo que A x = b . A resolução de x através da Eliminação Gaussiana padrão produz uma complexidade agregada de quase O ( n 3 ) . No entanto, há casos em que a solução (ou ϵ - aproximadamente) de x custos O ( n log ρ n ) , como sistemas em que An×nUMAxbn

UMAx=b.
xO(n3)ϵxO(nregistroρn)UMA é uma matriz simétrica e diagonalmente dominante (por exemplo, um Laplaciano) [1].

Quais outras famílias de sistemas lineares (ou seja, matrizes) admitem soluções de tempo lineares (ou não triviais de poli (n))? Se considerarmos campos finitos em vez de matrizes reais, existem famílias de matrizes que admitem soluções de tempo quase lineares?

[1] http://www.cs.yale.edu/homes/spielman/Research/linsolve.html

Dimitris
fonte

Respostas:

6

Sistemas lineares com matrizes circulantes podem ser resolvidos em usando a transformada rápida de Fourier. Uma matriz circulante tem entradas de um i , j = um 1 , i + j - 1 mod n por isso é completamente especificado pela primeira coluna. As matrizes circulantes são diagonalizadas pela rápida transformação de Fourier (tempo log-linear) e os sistemas lineares com matrizes diagonais podem ser resolvidos em tempo linear. Veja, por exemplo, o artigo da Wikipedia http://en.wikipedia.org/wiki/Circulant_matrix para mais detalhes.O(nregistron)umaEu,j=uma1,Eu+j-1modn

Desculpas se isso for muito trivial para ser mencionado aqui.

Jitse Niesen
fonte