2014 dxdy logo

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

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





Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Обратная по модулю матрица - конкурс
Сообщение04.04.2012, 16:04 


26/01/10
958
Предлагаю принять участие в очередном любительском конкурсе по программированию. На этот раз нужно написать программу, которая как можно быстрее вычисляет обратную по модулю $P=2^{31}-1Ъ$ матрицу. Время конкурса - 2 недели, начиная от 4-го апреля 2012 г..

Целочисленная матрица $C$ называется обратной к целочисленной матрице $A$ по модулю $P$, если
$$
A\cdot C \equiv C\cdot A \equiv I\quad (\mathrm{mod}\ P)
$$

Максимальный порядок матрицы $n=5000$.

Участие только под Win-32.

Подробности как обычно на этой странице моего сайта.

Реализация метода Гаусса "в лоб" работает на максимальном тесте 40 минут. Разумеется, все это значительно ускоряется. В этом и состоит задача участников.

Причина, по которой я начал этот конкурс, заключается в том, что для точного решения целочисленной системы уравнений нужно обращать исходную матрицу по модулю, чтобы потом отыскать p-адическую аппроксимацию решения. Вот это самое обращение матрицы нужно научиться выполнять быстро. Интересно посмотреть, что по этому поводу могут показать участники.

Модераторам: dxdy указан в качестве информационного спонсора.

 Профиль  
                  
 
 Re: Обратная по модулю матрица - конкурс
Сообщение10.04.2012, 13:20 
Аватара пользователя


27/05/07
115
А какие есть методы именно для целочисленных матриц?

 Профиль  
                  
 
 Re: Обратная по модулю матрица - конкурс
Сообщение19.04.2012, 15:27 


26/01/10
958
Конкурс завершился. Победителем объявляется участник alexBlack. Ниже приводится рейтинг участников: ник, компилятор и время работы программы на максимальном тесте (матрица 5000x5000).

  1. alexBlack :: Delphi :: 267,8 с.
  2. зщл :: g++ 4.6.2 :: 836,0 с.
  3. Sher :: Visual C++ / Asm :: 1001,5 с.
  4. Student :: Visual C++ :: 1691,8 с.

Здесь можно посмотреть итоги и мои идеи решения. По мотивам конкурса через некоторое время будут написаны посты, посвященные блочному методу Гаусса и битовым трюкам, позволяющим находить остаток от деления на числа вида $2^s-1$ (когда $s>1$).

-- Чт апр 19, 2012 15:28:17 --

ArtemKim в сообщении #558615 писал(а):
А какие есть методы именно для целочисленных матриц?

Даже не представляю.

 Профиль  
                  
 
 Re: Обратная по модулю матрица - конкурс
Сообщение20.04.2012, 09:23 


26/01/10
958
Тов. venco прислал сегодня свою версию программы для участия "вне конкурса". Время её работы на максимальном тесте составило 161,9 секунды.

 Профиль  
                  
 
 Re: Обратная по модулю матрица - конкурс
Сообщение21.04.2012, 18:29 
Аватара пользователя


27/05/07
115
а можно посмотреть на программу venco?

 Профиль  
                  
 
 Re: Обратная по модулю матрица - конкурс
Сообщение21.04.2012, 22:11 


26/01/10
958
ArtemKim в сообщении #562456 писал(а):
а можно посмотреть на программу venco?

Напишите лучше ему личное письмо, вдруг он не заметит вопроса...

 Профиль  
                  
 
 Re: Обратная по модулю матрица - конкурс
Сообщение24.02.2013, 12:00 


26/01/10
958
Zealint в сообщении #562041 писал(а):
Тов. venco прислал сегодня свою версию программы для участия "вне конкурса". Время её работы на максимальном тесте составило 161,9 секунды.

Удалось значительно ускорить мою версию программы: 111 секунд (было 231).

Переписал код под IA-32e, там вдвое больше xmm регистров, что позволяет более широко размахнуться. Кроме того, операции промежуточного умножения быстрее работают в 64 битовых регистрах, которых тоже вдвое больше.
При этом на ассемблере написан только кусок, отвечающий за перемножение маленьких блоков матрицы друг на друга. Так что еще секунд 10-20 сбросить можно, переписав все остальные функции.

Ну это я так, мало ли кому-то интересно...

 Профиль  
                  
 
 Re: Обратная по модулю матрица - конкурс
Сообщение24.02.2013, 17:55 
Аватара пользователя


27/05/07
115
код покажете ?

 Профиль  
                  
 
 Re: Обратная по модулю матрица - конкурс
Сообщение24.02.2013, 18:07 


26/01/10
958
ArtemKim в сообщении #687665 писал(а):
код покажете ?

Честно говоря, не хотелось бы. Не потому, что жалко, а потому, что уже завтра даже я ничего там не пойму. Как обычно, первые версии программ всегда пишу "на коленках", чтобы оценить. Потом всегда переписываю. Обычно по несколько раз. Думаю, лучше сделать так: в течении 2-3 ближайших недель я перепишу его более человеческим образом, добавлю комментариев и выложу посмотреть.

 Профиль  
                  
 
 Re: Обратная по модулю матрица - конкурс
Сообщение18.03.2013, 14:06 


26/01/10
958
Zealint в сообщении #687668 писал(а):
Думаю, лучше сделать так: в течении 2-3 ближайших недель я перепишу его более человеческим образом, добавлю комментариев и выложу посмотреть.

Я передумал. Вместо выкладывания исходника я добавил эту задачу на FastComputing (задача 0004). Уверен, что быстро найдутся более эффективные решения, вот у их авторов и попросите исходник. Чуть позже я сам туда зашлю своё самое быстрое решение, пока послал медленное, чтобы указать другим участникам на существование допустимого решения в принципе.

 Профиль  
                  
 
 Re: Обратная по модулю матрица - конкурс
Сообщение18.03.2013, 14:56 


10/04/12
429
Zealint в сообщении #687557 писал(а):
Переписал код под IA-32e, там вдвое больше xmm регистров, что позволяет более широко размахнуться.


Хм... почему бы тогда не использовать OpenCL? Есть брать AMD Radeon 7970, то там более 2000 вычислителей на частоте 1.5 GHz... Тоже аппаратная оптимизация :)

 Профиль  
                  
 
 Re: Обратная по модулю матрица - конкурс
Сообщение18.03.2013, 14:59 


26/01/10
958
Потому что цель пока в том, чтобы написать максимально быструю скалярную версию.

 Профиль  
                  
 
 Re: Обратная по модулю матрица - конкурс
Сообщение18.03.2013, 15:10 


10/04/12
429
Zealint в сообщении #697595 писал(а):
Потому что цель пока в том, чтобы написать максимально быструю скалярную версию.


В WinAPI есть функции для работы с многопоточностью. Ну и вообще, как-то, зависит сильно от архитектуры. Windows 8 работает и на ARM-ах... Опять же, что делать участникам, у которых AMD-процессор? Тот же Intell c GPU? Как-то условия размазаны.

 Профиль  
                  
 
 Re: Обратная по модулю матрица - конкурс
Сообщение18.03.2013, 15:14 


26/01/10
958
Уже ничего не делать. Конкурс-то уже год как закончился.

Кроме того, нет (или я не вижу) существенной разницы между AMD и Intel, так как тестируется всё на одной и той же машине - на моей.

А многопоточность сейчас не нужна. Когда будет нужна, тогда и обсудим, что там есть в WinAPI.

 Профиль  
                  
 
 Posted automatically
Сообщение04.11.2013, 01:54 
Основатель
Аватара пользователя


11/05/05
4062
London
 i  Тема перемещена из форума «Программирование» в форум «Олимпиадные задачи (CS)»
Причина переноса: не указана.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 16 ]  На страницу 1, 2  След.

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



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

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


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

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