WMO4: Algorytmy macierzowe

[@holyshit922]

No to ja widziałem dwa wzory na współczynniki wielomianu charakterystycznego Jeden wynikał z twierdzenia że Tr(A^{m}) = sum(λ_{k}^{m},k=1..n) oraz z wzorów Newtona-Girarda oraz wzorów Vieta Drugi wynikał z twierdzenia Cayleya-Hamiltona i sprowadzał się do rozwiązania układu równań liniowych Pierwszy z tych wzorów ma złożoność czasową O(nM) , co przy szkolnym sposobie mnożenia macierzy daje O(n^4) Drugi z tych wzorów ma złożoność czasową taką jak rozwiązywanie układu równań liniowych czyli O(n^3) Pierwszy z nich ma większą złożoność czasową ale występują w nim tylko dokładne dzielenia natomiast drugi z tych wzorów ma mniejszą złożoność czasową ale za to wymaga dzielenia

[@foxghost1814]

Szanowny Panie Profesorze, W pseudokod do algorytmy eliminacji Gaussa wkradł się błąd. W punkcie 2, podpunkt 4, podpunkt 2 powinniśmy dzielić przez "c", a nie mnożyć. Pozdrawiam

[@holyshit922]

Co do algorytmu Strassena to nie wiem czy to zmniejszenie złożoności czasowej algorytmu jest aż tak duże że warto dla niego zwiększyć złożoność pamięciową

[@pkoprowski]

To czy warto, czy też nie warto tego algorytmu użyć, zależy od konkretnych zastosowań i konkretnej architektury, na której pracujemy. Na pewno warto ten algorytm (a raczej algorytm Coppersmith-Winograd, o którym na wykładzie wspominam po algorytmie Strassena) znać. Bo tylko znając go możemy podjąć racjonalną decyzję, czy w naszej konkretnej sytuacji użycie danego algorytmu jest opłacalne.