Muszę obliczyć ślad macierzy do potęgi 3 i 4 i musi być tak szybki, jak to możliwe.

Macierz tutaj jest macierzą sąsiedztwa prostego grafu, a więc jest kwadratowa, symetryczna, jej wpisy to zawsze 1 lub 0, a elementy diagonalne to zawsze 0.

Optymalizacja jest banalna dla śladu macierzy do potęgi 2:

  • Potrzebujemy tylko przekątnych wpisów (i,i) do śladu, pomiń wszystkie inne
  • Ponieważ macierz jest symetryczna, te wpisy są tylko wpisami z i-tego rzędu do kwadratu i sumy
  • A ponieważ wpisy mają tylko 1 lub 0, operację kwadratową można pominąć

Innym pomysłem, który znalazłem na wikipedii, było podsumowanie wszystkich elementów produktu Hadamarda, czyli mnożenie przez wejście, ale nie wiem, jak rozszerzyć tę metodę do potęgi 3 i 4.

Zobacz http://en.wikipedia.org/wiki/Trace_(linear_algebra)#Properties< /a>

Może po prostu jestem ślepy, ale nie przychodzi mi do głowy proste rozwiązanie.

Na koniec potrzebuję implementacji C++, ale myślę, że to nie jest ważne dla pytania.

Z góry dziękuję za jakąkolwiek pomoc.

5
Gigo 29 luty 2012, 11:00

2 odpowiedzi

Najlepsza odpowiedź

Ok, sam to wymyśliłem. Ważną rzeczą, której nie wiedziałem, było to:

Jeśli A jest macierzą sąsiedztwa grafu skierowanego lub nieskierowanego G, to macierz An (tj. iloczyn macierzy n kopii A) ma interesującą interpretację: wpis w wierszu i i kolumnie j podaje liczbę (skierowaną lub nieskierowane) spacery o długości n od wierzchołka i do wierzchołka j. Oznacza to na przykład, że liczba trójkątów w grafie nieskierowanym G jest dokładnie śladem A^3 podzielonym przez 6.

(Skopiowano z http://en.wikipedia.org/wiki/Adjacency_matrix#Properties)

Pobieranie liczby ścieżek o danej długości od węzła i do i dla wszystkich n węzłów można zasadniczo wykonać w O(n), gdy mamy do czynienia z rzadkimi grafami i używamy list sąsiedztwa zamiast macierzy.

Niemniej jednak dzięki za odpowiedzi!

1
Gigo 12 marzec 2012, 18:33

Ślad jest sumą wartości własnych, a wartości własne mocy macierzy są tylko wartościami własnymi tej potęgi.

Oznacza to, że jeśli l_1,...,l_n są wartościami własnymi twojej macierzy, to śledź(M^p) = 1_1^p + l_2^p +...+l_n^p.

W zależności od macierzy możesz chcieć przejść z obliczaniem wartości własnych, a następnie sumowaniem. Jeśli twoja macierz ma niską rangę (lub można ją dobrze aproksymować za pomocą macierzy niskiego rzędu), możesz bardzo tanio obliczyć wartości własne (częściowa dekompozycja własnych ma złożoność O(n*k^2), gdzie k jest rządem).

Edytuj: W komentarzach wspominasz, że jest to 1600x1600, w którym to przypadku znalezienie wszystkich wartości własnych nie powinno stanowić problemu. Oto jeden z wielu kodów C++, których możesz użyć w tym http://code.google.com/p/ redsvd/

2
dranxo 1 marzec 2012, 09:00