2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Перемножение матриц
Сообщение12.07.2016, 11:11 
Заслуженный участник
Аватара пользователя


11/03/08
9496
Москва
Хотя мы уже выходим за пределы чисто математической тематики, и может быть пороты за оффтопик, но замечу, что это не столько математический (и даже не чисто алгоритмический) вопрос, сколько вопрос организации ЭВМ. Есть последовательный доступ к памяти, есть произвольный. Если "полностью произвольный", то есть доступ к любому элементу за одинаковое время, то транспонирование сводится к переобозначению индексов. А при "полностью последовательном", наподобие магнитных лент, требуется сложная схема перестановки, нечто подобное ленточной сортировке (ну и в порядке побаловаться экзотикой - были ещё магнитные барабаны, там шло непрерывное вращение, и для максимально быстрого доступа надо было следующий требуемый элемент, или команду программы, размещать не сразу за предыдущим, а так, чтобы за время обработки предыдущего барабан провернулся к требуемому месту). И для перемножения двух матриц было выгодно потратить время на их реорганизацию, получая нечто вроде "краковского умножения", а потом читать строки (или столбцы, как организовано, скорее столбцы, учитывая, что в ту эпоху был особо популярен Фортран) последовательно, поскольку даже для тех ЭВМ вычислительные операции требовали меньшего времени, чем механическое позиционирование носителя. С появлением дисков проблема ушла, но вернулась с возникновением конвейерной обработки и кэшей памяти. При правильной организации одна из строк находилась в кэше, а вычисления шли с максимальной скоростью. И несмотря на то, что приходится тратить время на транспонирование, в целом получается быстрее. Особенно актуально становится при многопроцессорной обработке, скажем, CUDA. Для квадратной алгоритм тривиален, $a_{i,j}\Leftrightarrow a_{j,i}$ Для прямоугольной либо переписыванием в дополнительную память, либо, при нехватке, вспоминаем, что в памяти всё равно одномерный массив, перебираем его индексы, начиная с произвольного, находим в какое место транспонированной переставится данный элемент исходной матрицы, потом, запомнив, что было на этом месте, помещаем исходный элемент на него и ищем, куда надо поместить запомненный и так, пока не замкнётся цикл; затем берём следующий элемент, не участвовавший в перестановках (проще всего использовать битовый массив; но есть и схемы без дополнительной памяти, но с усложнением алгоритма) и опять переставляем по кругу, пока не исчерпаются не участвовавшие в перестановках элементы.

 Профиль  
                  
 
 Re: Перемножение матриц
Сообщение12.07.2016, 11:25 
Аватара пользователя


27/01/09
814
Уфа
Извиняюсь, с целью уменьшения времени (а не скорости) выполнения. Да еще есть алгоритмы увеличения скорости выполнения (уменьшения общего количества операций (времени выполнения)) умножения матриц или вручную с использованием свойств матриц.

 Профиль  
                  
 
 Re: Перемножение матриц
Сообщение02.11.2017, 09:43 
Заслуженный участник
Аватара пользователя


11/03/08
9496
Москва
Евгений Машеров в сообщении #1136683 писал(а):
Но в Сети не нашёл (а платить сто с лишним баксов за удовлетворение случайного любопытства амфибиогенная асфиксия не даёт), так что оценить, историко-математическая ли, или с практическим выходом, не могу.


Вот тут оглавление
http://www.gbv.de/dms/goettingen/393561089.pdf
Полного текста не нашёл.

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

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

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