Обратная по модулю матрица - конкурс

[Zealint]

Предлагаю принять участие в очередном любительском конкурсе по программированию. На этот раз нужно написать программу, которая как можно быстрее вычисляет обратную по модулю $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 указан в качестве информационного спонсора.

[ArtemKim]

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

[Zealint]

Конкурс завершился. Победителем объявляется участник 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 писал(а):

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

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

[Zealint]

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

[ArtemKim]

а можно посмотреть на программу venco?

[Zealint]

ArtemKim в сообщении #562456 писал(а):

а можно посмотреть на программу venco?

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

[Zealint]

Zealint в сообщении #562041 писал(а):

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

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

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

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

[ArtemKim]

код покажете ?

[Zealint]

ArtemKim в сообщении #687665 писал(а):

код покажете ?

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

[Zealint]

Zealint в сообщении #687668 писал(а):

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

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

[mustitz]

Zealint в сообщении #687557 писал(а):

Переписал код под IA-32e, там вдвое больше xmm регистров, что позволяет более широко размахнуться.

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

[Zealint]

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

[mustitz]

Zealint в сообщении #697595 писал(а):

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

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

[Zealint]

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

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

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

[cepesh]

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