Qual é o algoritmo mais rápido para calcular a classificação de uma matriz retangular?

14

Dada uma matriz (assumindo ), qual é o algoritmo mais rápido para calcular sua classificação e base das colunas?m×nmn

Estou ciente de que pode ser resolvido através da interseção matróide linear, que implica um algoritmo determinístico de tempo e um algoritmo aleatório de tempo . Existe um algoritmo determinístico de tempo que reduz mais diretamente o problema (ou eliminação gaussiana) à multiplicação da matriz?O(mn1.62)O(mnω1)O(mnω1)

Ho Yee Cheung
fonte

Respostas:

6

Você pode trazer uma matriz de para a forma de escalão no tempo O ( n ω + ϵ ) para qualquer ϵ > 0 . Veja o livro "Teoria da Complexidade Algébrica" ​​de Bürgisser, Clausen, Shokrollahi, Seção 16.5.2n×nO(nω+ϵ)ϵ>0

Agora você aplica esse procedimento vezes à sua matriz m × n . Isso fornece um algoritmo com operações aritméticas O ( m n ω - 1 ) .m/nm×nO(mnω1)

Se você colocar uma matriz de na forma de escalão, ela conterá uma matriz zero de tamanho n × n posteriormente. Você pega os restantes n × n -matrix, adicionar um novo n × n -bloco de sua matriz de insumo e trazer isso para forma escalonada e assim por diante.2n×nn×nn×nn×n

5501
fonte
1
Você quer dizer dividir as linhas em grupos m / n ? Como você combina os resultados de m / n para obter a classificação? Considere duas linhas em forma de escalão de diferentes grupos que possuem 1 na primeira coluna; podem ter classificação 2, certo? mm/nm/n
Ho Yee Cheung
Existe um limite inferior para isso? Como no ranking, tem alguma força computacional?
Thomas Ahle 26/02