Fälle von nahezu linear zeitlösbaren linearen Systemen

Sei ein Quadrat reelle Matrix A und zwei Vektoren x und b der Länge n , so dass A x = b . Das Auflösen nach x durch Standard-Gauß-Eliminierung ergibt eine Gesamtkomplexität von fast O ( n 3 ) . Es gibt jedoch Fälle, in denen das Lösen (oder ϵ- ungefähres Lösen) nach x O ( n log ρ n ) kostet , wie zum Beispiel Systeme, in denen $n\times n$${\bf A}$${\bf x}$${\bf b}$$n$

$${\bf A}{\bf x}={\bf b}.$$ ${\bf x}$$O(n^3)$$\epsilon$${\bf x}$$O(n\log^\rho n)$${\bf A}$ ist eine symmetrische und diagonal dominante Matrix (zB ein Laplace) [1].

Welche anderen Familien linearer Systeme (dh Matrizen) lassen lineare (oder nichttriviale Poly (n)) Zeitlösungen zu? Wenn wir endliche Felder anstelle von reellen Matrizen betrachten, gibt es dort irgendwelche Matrizenfamilien, die nahezu lineare Zeitlösungen zulassen?

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

Lineare Systeme mit zirkulierenden Matrizen können in gelöst werden$O(n \log n)$$a_{i,j} = a_{1,i+j-1 \bmod n}$

Entschuldigung, wenn dies zu trivial ist, um hier erwähnt zu werden.