2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Методы решения СЛАУ над конечным полем
Сообщение21.04.2009, 21:30 
Аватара пользователя


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

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

 Профиль  
                  
 
 
Сообщение21.04.2009, 22:24 
Супермодератор
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение23.04.2009, 17:29 


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

 Профиль  
                  
 
 
Сообщение23.04.2009, 19:37 


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

 Профиль  
                  
 
 На пальцАх не могу
Сообщение23.04.2009, 23:31 


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

 Профиль  
                  
 
 Re: На пальцАх не могу
Сообщение24.04.2009, 05:53 


20/04/09
71
sceptic писал(а):
: Wiedemann D.H. Solving large sparse systems over finite fields.

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

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

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

 Профиль  
                  
 
 
Сообщение24.04.2009, 21:13 
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение24.04.2009, 21:54 


20/04/09
71
AndreyXYZ писал(а):
Алгоритм Видемана использует такие базовые алгоритмы, как .... быстрое преобразование Фурье и др. Моя задача заключается в определении максимально возможного ускорения при распараллеливании данного алгоритма.

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

 Профиль  
                  
 
 
Сообщение25.04.2009, 22:03 


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

 Профиль  
                  
 
 
Сообщение26.04.2009, 10:19 
Заслуженный участник
Аватара пользователя


23/07/05
17989
Москва
А метод Гаусса не подойдёт?

 Профиль  
                  
 
 
Сообщение26.04.2009, 20:42 
Аватара пользователя


27/10/08
222
Schraube в сообщении #207939 писал(а):
У Вас обычное ДПФ или его модулярная версия?


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

 Профиль  
                  
 
 
Сообщение26.04.2009, 22:18 


20/04/09
71
AndreyXYZ писал(а):
Schraube в сообщении #207939 писал(а):
У Вас обычное ДПФ или его модулярная версия?


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


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

и др

 Профиль  
                  
 
 Метод Гаусса тоже годится
Сообщение27.04.2009, 13:15 


24/05/05
278
МО
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 (саму статью можно попросить у автора на его страничке) - весьма полезно.

 Профиль  
                  
 
 
Сообщение29.04.2009, 21:42 


25/04/09
6
В методе Диксона нужно решить вообще 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) потом считать единицей. Но почему-то такое решение у меня не всегда работает правильно...видимо, баг в программе. Или может я все-таки ошибся в рассуждениях?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group