Jaki jest najszybszy algorytm do obliczania rangi macierzy prostokątnej?

Biorąc pod uwagę macierz $m \times n$ (przy założeniu, że $m \ge n$ ), jaki jest najszybszy algorytm obliczający swoją pozycję i podstawę kolumn?

Wiem, że można to rozwiązać za pomocą liniowego przecięcia macierzy, co implikuje algorytm deterministyczny czasowy i algorytm randomizowany czasowo O ( m n ω - 1 ) . Czy istnieje algorytm deterministyczny czasowy O ( m n ω - 1 ) , który bardziej bezpośrednio redukuje problem (lub eliminację Gaussa) do mnożenia macierzy?$O(mn^{1.62})$$O(mn^{\omega-1})$$O(mn^{\omega-1})$

Możesz wprowadzić macierz do postaci echelonu w czasie O ( n ω + ϵ ) dla dowolnego ϵ > 0 . Zobacz książkę „Teoria złożoności algebraicznej” Bürgissera, Clausena, Shokrollahi, rozdział 16.5.$2n \times n$$O(n^{\omega + \epsilon})$$\epsilon > 0$

Teraz zastosuj tę procedurę razy do swojej macierzy m × n . Daje to algorytm z operacjami arytmetycznymi O ( m n ω - 1 ) .$m/n$$m \times n$$O(mn^{\omega-1})$

Jeśli wprowadzisz macierz do postaci echelon, wówczas zawiera ona macierz zerową o rozmiarze n × n . Bierzesz pozostałą macierz n × n , dodajesz nowy blok n × n swojej matrycy wejściowej i doprowadzasz ją do formy echelon i tak dalej.$2n \times n$$n \times n$$n \times n$$n \times n$

$m \times n$$\tilde{O}(\textrm{nnz}(A) + r^{\omega})$ time, where $\textrm{nnz}(A)$ is the number of non-zero entries in $A$ and $r$ is the rank of $A$. This follows from Theorem 1.1 in Cheung et. al. [CKL'13] and binary searching over $r$. This is faster than the $O(mn^{\omega-1})$ algorithm mentioned above.