Jaki jest asymptotycznie najszybszy znany algorytm obliczania pustej przestrzeni macierzy?

10

Wiem, że eliminacja Gaussa wymaga operacji arytmetycznych , ale nie jestem pewien, czy znane są lepsze algorytmy.O(n3))

ds.algorithms  linear-algebra  matrices 
— GMB
źródło
Widzę jeden sposób na eliminację macierzy M Gaussa w czasie O (ranga n (2)). Czy istnieje sposób, aby to zrobić szybciej?
— Kyle

Odpowiedzi:

12

Wykładnik obliczania podstawy jądra jest taki sam jak wykładnik mnożenia macierzy, patrz książka Algebraic Complexity Theory autorstwa Bürgissera, Clausena i Shokrollahi. Można to zrobić w czasie .O(n2,38)

— Markus Bläser
źródło
3
lub 2.372 teraz, prawda?
— Suresh Venkat
3
Myślę, że to 2.3727.
— Markus Bläser
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.