Сложность решения линейных уравнений

9

Что известно о сложности решения системы линейных уравнений над некоторым конечным полем? Я знаю, что существуетO(n3)алгоритм (Гаусса), который вычисляет решение и что для разреженных систем есть еще лучшие алгоритмы. Однако мне было интересно, была ли какая-то теоретическая характеристика сложности этой проблемы. Например, является ли соответствующее решение проблемы вNC? Это полно для любого класса сложности?

Алан
источник

Ответы:

11

Я не уверен, что это вопрос исследовательского уровня, однако решение линейных систем более Fp это ModpL-полная проблема, следовательно, в частности, это вNC2, В более общем смысле, линейная алгебра надFpk (по крайней мере, для k фиксированный) может быть уменьшен до Fp дело.

Эмиль Йержабек
источник
6

В течение более 30 лет известен результат ликвидации Гуасси F2 может быть сделано с помощью различных разложений, которые принимают O(nω), где ω является константой умножения матриц.

Ссылки:

Ибарра О., Моран С. и Хуэй Р. 1982. Обобщение алгоритма и приложений быстрого разложения матрицы LUP . Журнал Алгоритмы 3, 45 {56.

Жаннерод, С.-П. , Pernet, C. и Storjohann, A. 2011. Профиль ранга, раскрывающий исключение Гауссаина и разложение матрицы CUP .

RB
источник