Какой асимптотически самый быстрый известный алгоритм для вычисления нулевого пространства матрицы?

Я знаю, что для устранения Гаусса требуется арифметических операций, но я не уверен, известны ли какие-либо лучшие алгоритмы. $O(n^3)$

ds.algorithms linear-algebra matrices GMB
источник

Я могу увидеть один способ сделать гауссовскую ликвидацию матрицы M за O (n ^ 2 rank (M)) времени. Есть ли способ сделать это быстрее?

Кайл

Ответы:

Показатель вычисления базиса ядра совпадает с показателем умножения матриц, см. Книгу «Теория алгебраической сложности» Bürgisser, Clausen & Shokrollahi. Так что это можно сделать за время . $O(n^{2.38})$

Маркус Блезер
источник

или 2,337 сейчас, верно?

Суреш Венкат

Я думаю, что это 2,3727.

Маркус Блезер