Интересуют подробные описания алгоритмов перемножения матриц.
Все, кроме классического правила (строка-столбец), алгоритма Штрассена, алгоритма Копперсмита-Винограда, если таковые еще существуют.

Не так давно проф. Грановский изобрёл алгоритм, который работает ещё быстрее Штрассена и Винограда. Сам алгоритм не знаю, видел его упоминание на форуме Intel. Интеловцы вроде его уже реализовали в своей Intel MKL.
В общем сейчас разработка новых алгоритмов идёт в основном в направлении распараллеливания. Алгоритм Грановского вроде тоже хорош для распараллеливания.

Ещё посмотри книги Воеводина. Он хорошо разбирает матрицы с т.зр. алгоритмов. Например, Воеводин, Кузнецов "Матрицы и вычисления".

Описания алгоритма Грановского я не нашел, как впрочем и книгу... Она 1984 года, так что достать её весьма сложно.

Ну значит надо в библиотеку идти. Впрочем, как и за Воеводиным.
А я что-то думал, что алгоритм Грановского поновее будет, 90-х или даже 2000-х годов...

Ладно, лови плюс, но тема все равно остается актуальной. 
Если кто подскажет серьезные ресурсы по данной тематике, буду очень благодарен.

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

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

Очень интересное наблюдение:

Обычный код для умножения двух квадратных матриц:



А теперь перед тем как умножить транспонируем матрицу B и изменим индексы:



Это умножение будет в несколько раз (в 2-3 раза) быстрее чем стандартное!

Это сообщение отредактировал(а) Vitaly333 - 16.10.2008, 10:29

1) Как замеряли время? (опишите эксперимент)
2) И почему там i большое и i маленькое?

Замерял стандартными средствами языка!
Здесь всё дело в оптипальном расположении данных в кэше!



Очепятка вышла. Уже исправил!

Ну это уже будет зависеть от размера матриц. 

К тому же мне кажется, что вы умножаете одним способом, а потом, в этой же программе, умножаете эти же матрицы. Т.е. ко второму умножению, обе матрицы оказываются в кэше! Понятно дело будет быстрее.  Даже если оба умножения в разных прогах. То всё равно после транспонирования матрица В будет в кэше. Попробуйте замерить вместе с транспонированием.

Если ваша матрица B намного меньше кэша по размеру, то можно её без проблем поместить в кэш и без транспонирования. Хотя конечно последовательное чтение ячеек из области памяти, где находится матрица В, тоже играет свою роль.

может кто знает или знает где искать как реализовать умножение 2 матриц на 3D структуре... Зарание спасибо!

а ответ будет равен в обеих "умножениях" ?
а то как-то A(i,k)*B(j,k)  похоже на скалярное умножение двух строк, а не строка*столбик, как по определению...
поэкспериментируй с матрицами:
А=[1,2;3,4]; и B=[5,6;7,8]

Чем больше размер матриц тем больше будет видна разница в скорости. Оба умножения были запущены отдельно друг от друга и замеры времени я брал вместе с трансонированием. Дело в том, что матрица в современных системах программирования представляется как массив массивов. (Массив - столбец , каждый элемент которого, есть массив - строка). А массив данных - это какой то участок близко расположенных значений в  памяти. Так вот процессору в матрице всегда "легче" пройтись по строчке, чем по столбцу, потому что, чтобы проходить по столбцу процессор каждый раз должен переключится на другой массив (другой участок в памяти) (как говорят обновить кэш)  - а это дополнительное время.  Поэтому в эффективных алгоритмах на матрицах нужно минимизировать такие переключения процессора. 


Конечно будет равен. Перед умножением матрица B - транспонируется.

Да, я тоже такой приём использовал и у меня прирост на матрицах с количеством элементов большим 1 млн. составил ~1000%. На маленьких матрицах (< 256х256) на современных процессорах смысла в транспонировании нет, они целиком умещаются в кеш. Ещё при использовании такого приёма умножение можно векторизировать (т.е. заюзать SIMD и SSE), выполняя 2-4 умножения за такт. 

А матрицу лучше хранить не строками, а линейно и адресовать как x[i * col + j]