Szukam dobrej ankiety na temat algorytmów i złożoności algebry liniowej (operacje takie jak rank, inverse, wartości własne, ... dla Boolean, oraz liczby całkowite / racjonalne) z naciskiem na równoległość ( hierarchia ) i algorytmy politime. Nie mogłem znaleźć ostatniego. NC
Czy znasz dobrą ostatnią ankietę lub książkę na temat złożoności algebry liniowej?
Odpowiedzi:
Pomocne mogą być dwie referencje:
D. Bini i V. Pan. Obliczenia wielomianowe i macierzowe, Tom 1: Algorytmy podstawowe. Postęp w informatyce teoretycznej, Birkhauser, 1994.
J. von zur Gathen. Równoległa algebra liniowa. W J. Reif, redaktor, Synthesis of Parallel Algorytm, rozdział 13. Morgan Kaufmann Publishers, Inc., 1993.
Nie zawsze są aktualne, ale są dobrym punktem wyjścia.
Co powiesz na dolne granice złożoności za pomocą algebry liniowej ? Książka nie jest dokładnie to, co chcesz, ponieważ bada to dolne granice za pomocą algebry liniowej, a nie złożoność z liniowych problemów algebry. Jednak myślę, że i tak jest to pomocne, ponieważ najpierw trzeba uchwycić złożoność problemów z algebrą liniową, a następnie użyć jej do udowodnienia niższych granic innych problemów.
Oto opis książki:
Chociaż poczyniono szybkie postępy w zakresie górnych granic (algorytmów), postępy w dolnych granicach w zakresie złożoności wyraźnych problemów pozostawały powolne pomimo intensywnych wysiłków przez kilka dziesięcioleci. Jak to naturalnie przy typowych wynikach niemożliwości, dolne granice są trudnymi problemami matematycznymi, a zatem jest mało prawdopodobne, że zostaną rozwiązane przez ataki ad hoc. Zamiast tego konieczne są techniki oparte na pojęciach matematycznych, które wychwytują złożoność obliczeniową. Złożoność dolnych granic za pomocą algebry liniowej bada kilka technik dowodzenia dolnych granic w logice boolowskiej, algebraicznej i złożoności komunikacji w oparciu o pewne liniowe podejścia algebraiczne. Wspólnym tematem tych podejść jest badanie miar niezawodności rang macierzyktóre oddają złożoność w danym modelu. Odpowiednio silne dolne granice takich niezawodnych funkcji wyraźnych macierzy prowadzą do ważnych konsekwencji w odpowiednich modelach obwodów lub komunikacji. Zrozumienie nieodłącznej złożoności obliczeniowej problemów ma fundamentalne znaczenie w matematyce i informatyce teoretycznej. Złożoność dolnych granic za pomocą algebry liniowej jest nieocenionym odniesieniem dla każdego, kto pracuje w terenie.
PS: Prosiłeś o książkę, ale uważam, że ten artykuł: Obliczeniowa złożoność niektórych problemów algebry liniowej jest również przydatny (ale pochodzi z 1999 roku).
Ta książka nie wspomina wprost o algorytmach równoległych, ale książka Yap „Fundamental Problems Algebra Algorytmiczna” jest bardzo dobrym odniesieniem i omawia złożoność wielu pytań dotyczących algebry liniowej. W rozdziale poświęconym układom liniowym znajduje się rozdział omawiający między innymi złożoność czasowo-bitową obliczeń wyznaczników, odwrócenie macierzy, algorytmy postaci normalnej Hermite'a.
Książka zajmuje się również złożonością mnożenia, baz Grobnera i technikami redukcji krat (np. LLL). Nie mogę tego wystarczająco polecić i założę się, że znajdziesz w tym coś wartościowego.