Обращение матрицы в GF

[vlad_light]

Пусть у нас дана матрица $A\in Mat _{\mathbb R^{n\times n}}(\mathbb GF(2^m))$, где $n$ -- порядка 1000-10000. Как можно быстро проверить, что $A$ -- невырождена и быстро найти $A^{-1}$?

[patzer2097]

vlad_light в сообщении #821565 писал(а):

$A\in Mat _{\mathbb R^{n\times n}}(\mathbb GF(2^m))$

если Вы имеете в виду матрицу размера $n\times n$ над полем из $2^m$ элементов, то лучше отредактировать Ваше сообщение соответственно.

[Xaositect]

Имелось в виду $GF(2^m)^{n\times n}$, я думаю.

Все так же, как и для действительных - обращать методом Гаусса (возможно, на размерах 10 000 можно несколько раз применить Штрассена), эффективно перемножать элементы и минимизировать деления, ну и много низкоуровневой оптимизации. А $m$ какого порядка?

Есть библиотека M4RI(e), у них на сайте есть бенчмарки: http://m4ri.sagemath.org/performance.html

[vlad_light]

Простите, имел ввиду это: $A\in Mat _{n\times n}(\mathbb GF(2^m))$.
$m$ равно 8, 16, 32.

Цитата:

возможно, на размерах 10 000 можно несколько раз применить Штрассена

К сожалению, не знаком с данным методом. Возможно, это тоже самое, что и http://en.wikipedia.org/wiki/Invertible_matrix#Blockwise_inversion?

[Xaositect]

vlad_light в сообщении #821643 писал(а):

К сожалению, не знаком с данным методом. Возможно, это тоже самое, что и http://en.wikipedia.org/wiki/Invertible ... _inversion
?

Да, оно.