Quel est l'algorithme le plus rapide pour calculer le rang d'une matrice rectangulaire?

15

Étant donné une matrice (en supposant ), quel est l'algorithme le plus rapide pour calculer son rang et sa base des colonnes?m×nmn

Je suis conscient qu'il peut être résolu par intersection matroïde linéaire, ce qui implique un algorithme déterministe temporel et un algorithme randomisé temporel . Existe-t-il un algorithme déterministe du temps qui réduit plus directement le problème (ou l'élimination gaussienne) à la multiplication matricielle?O(mn1,62)O(mnω-1)O(mnω-1)

Ho Yee Cheung
la source

Réponses:

9

Vous pouvez mettre une sous forme d'échelon dans le temps pour n'importe quel . Voir le livre "The Algebraic Complexity Theory" de Bürgisser, Clausen, Shokrollahi, Section 16.5.2n×nO(nω+ϵ)ϵ>0

Vous appliquez maintenant cette procédure fois à votre matrice . Cela donne un algorithme avec opérations arithmétiques.m/nm×nO(mnω-1)

Si vous apportez une matrice sous forme d'échelons, elle contient ensuite une matrice nulle de taille . Vous prenez la matrice restante , ajoutez un nouveau bloc de votre matrice d'entrée et apportez cela sous forme d'échelon et ainsi de suite.2n×nn×nn×nn×n

5501
la source
1
Voulez-vous dire de diviser les lignes en groupes ? Comment combinez-vous les résultats pour donner le rang? Considérez deux rangées sous forme d'échelons de groupes différents qui ont tous deux 1 dans la première colonne, ils peuvent avoir le rang 2 non? mm/nm/n
Ho Yee Cheung
Y a-t-il une limite inférieure pour cela? Comme dans le rang a-t-il une force de calcul?
Thomas Ahle
3

On peut calculer le rang d'une matrice A dans temps, où est le nombre des entrées non nuls dans et est le rang de . Cela découle du théorème 1.1 de Cheung et. Al. [CKL'13] et recherche binaire sur . C'est plus rapide que l' algorithme mentionné ci-dessus.m×nO~(nnz(UNE)+rω)nnz(UNE)UNErUNErO(mnω-1)

Ainesh Bakshi
la source
2
Je suppose que vous voulez dire "plus vite que l' algorithme " (je ne peux pas modifier la réponse moi-même car la modification est trop petite)O(mnω-1)
smapers
1
Merci d'avoir fait remarquer cela. La citation ci-dessus est un document du PO, donc ma réponse est surtout pour être complet.
Ainesh Bakshi