Методы решения СЛАУ над конечным полем

[AndreyXYZ]

Пусть $A$ --- матрица размерности $n \times n$ над полем $GF(q),$ $b$ --- вектор длины $n$ над полем $GF(q),$ $b \ne 0$. Требуется решить систему

$$Ax=b.$$

Какие существуют методы решения таких уравнений, и каковы их асимптотические оценки трудоёмкостей?
Я знаком с методами Гаусса и Крамера и методе, основанном на нахождении обратной матрицы $A^{-1}.$ Но все эти методы, насколько я знаю, имеют оценку $O(n^3).$

[PAV]

Переношу из Дискуссионного раздела (М) в Computer Science.

[sceptic]

В книге Василенко О.Н. Теоретико-числовые алгоритмы в криптографии теме посвящена гл. 11. Обратите внимание на алгоритм Видемана.

[Schraube]

sceptic
Валерий!
А какая такая специфика конечного поля позволяет "нажиться" и синтезировать алгоритмы с ИНОЙ структурой, чем известные (оценка сложности в терминах арифметических операций которых инвариантна относительно выбора поля)
Конечно, можно как-то быстро умножать элементы непростого конечного поля и оценивать число модулярных операций. Но это влияет только на константу в символе "О" (ср. комплексное поле - вещественное поле - оценка сложности комплексного алгоритма в терминах вещественных операций)
Основную идею на пальцАх не затруднит?
Книги у меня все равно нет
Михалыч

[sceptic]

У Василенко лишь описание алгоритма, за оценкой сложности он отсылает к Видеману. До первоисточника я не добрался - доступа нет. Попробуйте погуглить: Wiedemann D.H. Solving large sparse systems over finite fields.
Выловите много любопытного (я, в частности, выловил обзор B.A. LaMacchia and A.M. Odlyzko по теме).

[Schraube]

sceptic писал(а):

: Wiedemann D.H. Solving large sparse systems over finite fields.

Да, я так и думал, что как-то нажиться можно, если
а) порядок системы много больше количества элементов поля
или
б) степень расширения много больше порядка системы (тогда нужно/можно поиграться с автоморфизмом Фробениуса)

Вроде бы никаких иных идейных резервов не просматривается.

PS. to sceptic о приватных вопросах
1. мне не удалось зарегистрироваться под "родным" ником, поэтому такой как есть
2. в столице буду гарантировано 14.05 (оппонирование). Появится ясность о времени - напишу в привате.

[AndreyXYZ]

На протяжении последних недель я занимаюсь исследованием и реализацией упомянутого Вами алгоритма Видемана. (см Теоретико-числовые алгоритмы в криптографии). Если кого-то заинтересует, буду рад сотрудничать с совместном разборе и анализе данного алгоритма. Он хорошо работает для разреженных матриц и имеет временную сложность $O\big(n(\omega+n\log n\log\log n)\big),$ где $\omega$ --- количество ненулевых элементов матрицы. Этот алгоритм является самым быстрым, но и самым трудным в реализации алгоритмом решения разреженных СЛАУ.
Алгоритм Видемана использует такие базовые алгоритмы, как алгоритм Берлекэмпа-Месси нахождения минимального многочлена, линейная свертка, быстрое преобразование Фурье и др. Моя задача заключается в определении максимально возможного ускорения при распараллеливании данного алгоритма.

[Schraube]

AndreyXYZ писал(а):

Алгоритм Видемана использует такие базовые алгоритмы, как .... быстрое преобразование Фурье и др. Моя задача заключается в определении максимально возможного ускорения при распараллеливании данного алгоритма.

У Вас обычное ДПФ или его модулярная версия?
Во втором случае реальная скорость и возможность распараллеливания сильно зависит от модуля. Для специально синтезированных модулей можно серьезно выиграть по скорости.

[lonelyass]

Простите за наглость, но не могли бы вы дать мне описание, ссылку или хотя бы конкретное название алгоритма, которым бы я смогу решить задачу Ax=0 в поле GF(2)? Интересует не оптимальный, но самый простой, понятный и легкореализуемый алгоритм. Пишу курсовую по методу Диксона, сроки поджимают, а на этой ерундовой задаче застопорился...

[Someone]

А метод Гаусса не подойдёт?

[AndreyXYZ]

Schraube в сообщении #207939 писал(а):

У Вас обычное ДПФ или его модулярная версия?

С этим я пока не определился. Для вычисления свёртки необходимо использовать БПФ. Но будет ли он работать над конечным полем? Чем отличается обычное ДПФ от его модулярной версии?
Если говорить о распараллеливании, то я надеюсь, что можно просто запустить параллельный алгоритм на нескольких компьютерах и получить некоторое ускорение за счет недетерминированности алгоритма.

[Schraube]

AndreyXYZ писал(а):

Schraube в сообщении #207939 писал(а):

У Вас обычное ДПФ или его модулярная версия?

С этим я пока не определился. Для вычисления свёртки необходимо использовать БПФ. Но будет ли он работать над конечным полем? Чем отличается обычное ДПФ от его модулярной версии?

Мда... Похоже, что Вы не в курсе. "Модулярные ДПФ" = "теоретико-числовые преобразования"(ТЧП) имеют почтенную, более чем 30-летнюю историю. Думаю, что счет количества публикаций идет на сотни.
Кое-что есть у Кнута.
Рекомендую для первого чтения
http://lib.mexmat.ru/books/783
http://lib.mexmat.ru/books/5222

и др

[sceptic]

lonelyass писал(а):

Простите за наглость, но не могли бы вы дать мне описание, ссылку или хотя бы конкретное название алгоритма, которым бы я смогу решить задачу Ax=0 в поле GF(2)? Интересует не оптимальный, но самый простой, понятный и легкореализуемый алгоритм. Пишу курсовую по методу Диксона, сроки поджимают, а на этой ерундовой задаче застопорился...

$Ax=0$? Может быть, $Ax=b$?

Someone писал(а):

А метод Гаусса не подойдёт?

Полагаю, очень даже подойдет. Для $GF(2)$ оценка сложности для метода Гаусса падает до $O(n^2)$. См. A Parallel Hardware Architecture for fast Gaussian Elimination over GF(2).

Что касается распараллеливания, lonelyass, взгляните на презентацию Oseledets I.V. Parallel solution of linear systems and optimal multiplication (саму статью можно попросить у автора на его страничке) - весьма полезно.

[lonelyass]

В методе Диксона нужно решить вообще xA=0 (mod 2), причем A размера (N+1)*N. Проблема в том, что до распараллеливания я еще не дошел... В книге Трифонова "Построение и анализ алгоритмов" есть такой момент

Я не понимаю как именно применить Гаусса, чтобы найти в такой задаче нетривиальное (ненулевое) решение. Догадываюсь, что нужно записать вектора alpha(i) в матрице не рядками как в книге, а столбиками; последний из векторов перенести в правую часть, предположив x(n+1)=1. Тогда получится задача A'x=b' (mod 2), где A' уже размера NxN и b' длинны N. Найти обычным Гауссом x размера n, а x(n+1) потом считать единицей. Но почему-то такое решение у меня не всегда работает правильно...видимо, баг в программе. Или может я все-таки ошибся в рассуждениях?