Was ist der schnellste Algorithmus, um den Rang einer rechteckigen Matrix zu berechnen?

14

Welcher Algorithmus berechnet bei einer Matrix ( m n vorausgesetzt ) am schnellsten den Rang und die Basis der Spalten?m×nmn

Mir ist bewusst, dass es durch eine lineare Überschneidung der Matroiden gelöst werden kann, die einen -Zeit- deterministischen Algorithmus und einen O ( m n ω - 1 ) -Zeit-randomisierten Algorithmus impliziert . Gibt es einen O ( m n ω - 1 ) zeitdeterministischen Algorithmus, der das Problem (oder die Gaußsche Eliminierung) direkter auf die Matrixmultiplikation reduziert?O(mn1.62)O(mnω1)O(mnω-1)

Ho Yee Cheung
quelle

Antworten:

6

Sie können eine Matrix in der Zeit O ( n ω + ϵ ) für jedes ϵ > 0 in die Staffelform bringen . Siehe das Buch "Algebraic Complexity Theory" von Bürgisser, Clausen, Shokrollahi, Abschnitt 16.5.2n×nO(nω+ϵ)ϵ>0

Nun wenden Sie dieses Verfahren mal auf Ihre m × n- Matrix an. Dies gibt einen Algorithmus mit O ( m n ω - 1 ) arithmetischen Operationen.m/nm×nO(mnω1)

Wenn Sie eine Matrix in die Staffelform bringen, dann enthält sie anschließend eine Nullmatrix der Größe n × n . Sie nehmen die verbleibende n × n- Matrix , fügen einen neuen n × n- Block Ihrer Eingabematrix hinzu und bringen diesen in die Staffelform und so weiter.2n×nn×nn×nn×n

5501
quelle
1
mm/nm/n
Gibt es dafür eine Untergrenze? Wie in hat der Rang eine Rechenstärke?
Thomas Ahle