3582461386

Analiza algorytmów

Mnożenie macierzy i pokrewne operacje

Kordian A. Smoliński

Uniwersytet Łódzki

2007/2008

Kordian A. Smoliński

(Uniwersytet Łódzki)

2007/2008    1 / 26

Analiza algorytmów

Zbadamy asymptotyczną złożoność obliczeniową mnożenia macierzy

0    elementach z dowolnego pierścienia. „Zwykły” algorytm mnożenia macierzy n x n, o złożoności 0(n³) można asymptotycznie ulepszyć do 0(n^2,81). Pokażemy dalej, że rozkład LUP, odwracanie macierzy

1    obliczanie wyznacznika są redukowalne do mnożenia macierzy, a także, że mnożenie macierzy jest redukowalne do odwracania macierzy, zatem poprawa asymptotycznego czasu dla jednej operacji automatycznie poprawia czas drugiej.

Przedstawione algorytmy trudno uznać za praktyczne dla obecnego sprzętu komputerowego, niedostatecznie znana jest także kwestia kontroli błędów numerycznych dla tych algorytmów. Stanowią one jednak ilustrację faktu, że nie zawsze oczywiste algorytmy są najlepsze.