Конкурс - перемножение матриц

[Zealint]

Сообщение от LeBron

5000*5000 - не совсем маленькая матрица. Для Штрассена с более-менее прямой реализацией выиграш уже должен быть заметным, я молчу об Винограде. У Винограда и асимптотика значительно лучше, и константа не такая большая, чтоб можно было говорить, что на 5000*5000 он хуже лобовика.

Друзья, вы начинаете дико тормозить. Во-первых, Штрассен та таких размерах лучше Винограда (самого последнего). Асимптотика Винограда никакого смысла на 5000 не имеет. Хотя, если вы в состоянии доказать обратное - давайте. Пока это еще никому не удавалось. Во-вторых, даже лобовой алгоритм можно реализовать быстро: минуты за 3 чтобы работал точно можно. Я думаю, как имено... Может кто-то раньше сообразит и пришлет... может даже выиграет : )

[LeBron]

Сообщение от akasex

к сожалению Виноград здесь не поможет.....матрица слишком мала для него...а вот Штрассен (для нашей матрицы это будет матрица 2^13) должен обойти лобовой метод по-любому....

Как я помню, класический Штрассен требует дополнения матрицы до степеня двойки :

(для нашей матрицы это будет матрица 2^13)

Следовательно, еще вопрос, уложимся ли в память Подозреваю, что нет.

[akasex]

Сообщение от LeBron

Как я помню, класический Штрассен требует дополнения матрицы до степеня двойки :

Следовательно, еще вопрос, уложимся ли в память Подозреваю, что нет.

да...действительно можно попасть в просак...

Matrix 2500x2500 Multiplication,
Strassen Algorithm (Intel 1.25Ghz)

without SSE : around 130 s
with SSE : around 1 s

(c) Apple Inc.

[Zealint]

Сообщение от LeBron

Как я помню, класический Штрассен требует дополнения матрицы до степеня двойки :

Следовательно, еще вопрос, уложимся ли в память Подозреваю, что нет.

Так я же вроде бы где-то уже написал, что для того, чтобы победить придется подумать. Да, Штрассен, в статье самого Штрассена (1968 г.) требует дополнения до степеней двойки. Но никто не мешает подумать и сделать так, чтобы все влезало как надо... или вообще найти другой алгоритм.

Matrix 2500x2500 Multiplication,
Strassen Algorithm (Intel 1.25Ghz)

without SSE : around 130 s
with SSE : around 1 s

Замечательно. Осталось только прислать мне программу и выиграть. В чем сложность? Кстати, 1 с - не верится... прогон наверное, кто-то пошутил : ) Ввод и вывод тогда придется не пойми на чем писать.

И вообще, народ, хватит языком чесать : ) давать советы все умеют, а программировать, как выясняется, не все. Так?

[akasex]

Сообщение от Zealint

прогон наверное, кто-то пошутил

(c) Apple Inc.

[LeBron]

Сообщение от Zealint

И вообще, народ, хватит языком чесать : ) давать советы все умеют, а программировать, как выясняется, не все. Так?

Хе Мы и программируем паралельно, совмещаем одно с другим.
Поспрашивал у людей, по словам АСМщиков, все решимо в пределах не только минуты (как я сначала сказал), но даже 30 скунд Аж страшно стало, моя первая наработка на моем компе в сумме за 3 попытки показала 35 минут 58 секунд, тоесть почти 12 минут на попытку.
Буду дорабатывать.

[Zealint]

Сообщение от akasex

(c) Apple Inc.

Пусть идут в лес со своими шутками : ) Пока программу не протестирую, мне эти цифры ни о чем не говорят. Совсем. Понимаете, говорить можно все, что угодно, а когда речь идет о конкретных примерах, пасуют все самые продвинутые алгоритмы. Ну что, кто уже Штрассена написал? Мне завтра кто-то обещал первую версию кинуть, посмотрим...

[akasex]

Сообщение от Zealint

Пусть идут в лес со своими шутками : ) Пока программу не протестирую, мне эти цифры ни о чем не говорят. Совсем. Понимаете, говорить можно все, что угодно, а когда речь идет о конкретных примерах, пасуют все самые продвинутые алгоритмы. Ну что, кто уже Штрассена написал? Мне завтра кто-то обещал первую версию кинуть, посмотрим...

The efficiency of Apple’s AltiVec velocity engine results from the fact that it is able to process four multiplications simultaneously by multiplying four-dimensional vectors of numbers instead of individual numbers. This not only speeds up the pace of actual number crunching, but also allows the four sub-matrix references (pointers) to be contained in a single 128-bit header (because each is exactly 32 bits), which practically eliminates the slowdown observed earlier in the non-optimized Strassen’s algorithm.

[Zealint]

Сообщение от akasex

The efficiency of Apple’s AltiVec velocity engine results from the fact that it is able to process four multiplications simultaneously by multiplying four-dimensional vectors of numbers instead of individual numbers. This not only speeds up the pace of actual number crunching, but also allows the four sub-matrix references (pointers) to be contained in a single 128-bit header (because each is exactly 32 bits), which practically eliminates the slowdown observed earlier in the non-optimized Strassen’s algorithm.

И что? Отдать 1000 р. Apple'у? : ) Пока программа не появится в моём ящике говорить не о чем. Я кажется назвал ограничения, которые должны выполнять. Смысл ограничений, конечно может показаться непонятным для вас, но они есть.

[Arigato]

Программа должна работать в консольном режиме, то есть никаких графических интерфейсов писать не нужно. Ваша программа считывает матрицы из входного файла (который будет находится в той же директории), перемножает их и выводит ответ в другой файл (в ту же директорию). Подробнее о формате ввода / вывода см. ниже.

И зачем консольный режим, если ничего выводить в консоль не нужно, а только в файл?

Пока только один участник – я : )

Считается дурным тоном, когда организатор конкурса и жюри сам принимает в нём участие.