Kombinatoryczny algorytm obliczania wyznacznika

Speaker(s)

Anna Urbańska

Affiliation

Uniwersytet Warszawski

Date

Nov. 17, 2005, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

Tematem referatu jest kombinatoryczna charakteryzacja wyznacznika, dająca prosty i całkowicie kombinatoryczny algorytm na jego obliczanie, działający w czasie O(n^4). Algorytm ten nie wymaga dzielenia i pracuje nad dowolnym pierścieniem przemiennym. Postaram się również pokazać, jak wykorzystując algorytm szybkiego mnożenia macierzy poprawić złożoność czasową tego algorytmu. Na koniec opowiem jak w analogiczny sposób można scharakteryzować wszystkie pozostałe współczynniki wielomianu charakterystycznego oraz Pfaffian dowolnej macierzy skośno-symetrycznej oraz podam kombinatoryczne dowody poprawności znanych algorytmów obliczania wyznacznika (Chistova, Csanky'ego oraz Samuelsona).

---