Quel est l'algorithme connu asymptotiquement le plus rapide pour calculer l'espace nul d'une matrice?

Je sais que l'élimination gaussienne prend des opérations arithmétiques , mais je ne sais pas si de meilleurs algorithmes sont connus. $O(n^3)$

ds.algorithms linear-algebra matrices GMB
la source

Je peux voir une façon de faire l'élimination gaussienne de la matrice M en temps O (n ^ 2 rang (M)). Y a-t-il un moyen de le faire plus rapidement?

Kyle

Réponses:

L'exposant du calcul d'une base du noyau est le même que l'exposant de la multiplication matricielle, voir le livre Algebraic Complexity Theory de Bürgisser, Clausen & Shokrollahi. Cela peut donc se faire dans le temps . $O(n^{2.38})$

Markus Bläser
la source

ou 2.372 maintenant, non?

Suresh Venkat

Je pense que c'est 2.3727.

Markus Bläser