хранение в памяти больших матриц

[y_nikolaenko]

gris,

Я думаю, что Вы и сами в этом быстро разберетесь.

[venco]

y_nikolaenko в сообщении #355812 писал(а):

gris,

Я думаю, что Вы и сами в этом быстро разберетесь.

Ну, хотя бы другим собеседникам скажете? Мне тоже интересно.

[gris]

Я поясню. Компьютерные реалии ранних шестидесятых очень сложны для представления молодым программерам, так же как их внукам будут непонятны (я надеюсь на прогресс) траблы наших дней.
Конечно, имея в памяти место для вектора, для одной строки матрицы и для строки результата можно организовать умножение в один проход с каким угодно способом "подачи" матрицы в память. Хотя время может существенно вырасти при отходе от последовательных процессов (в памяти, даже не на ленте).
Но вот бывало что место есть только для вектора и для части строки или столбца. Вот тут и приходилось держать два рулона на каждую матрицу .

[y_nikolaenko]

gris,

Как я понял, Вы догадались.

[Zealint]

На всякий случай, есть ещё один способ хранения матриц. Всегда есть верхняя граница на числа (скажем $k$ бит), следовательно, храним всё в битовом поле из $kn^2$ бит. Само битовое поле сжимается каким-нибудь алгоритмом архивирования с возможностью извлечения части информации, не распаковывая весь архив. Обращение к элементам матрицы оказывается чрезвычайно сложным, зато это оправдано, когда матрица не умещается в память, а на ЭВМ порядка сотни ядер.

[gris]

Zealint, битовое поле из белого шума при сжатии стандартным алгоритмом пожалуй ещё увеличится в размерах.

y_nikolaenko, я давно уже догадался, да .
Сейчас программер мыслит широко и масштабно, а раньше его работа иногда напоминала изготовление модели парусника в бутылке. Разные трюки и уловки, которые сейчас покажутся смешными. Однако некоторые приёмы программирования срабатывают и поныне.

[venco]

y_nikolaenko в сообщении #355822 писал(а):

gris,

Как я понял, Вы догадались.

Я подозреваю, транспонированные матрицы хранились для умножения на матрицу. А в умножении на вектор они использовались для небольшого ускорения.

[gris]

venco, и Вы скептически поглядываете в мою сторону. Ну представьте, что в памяти едва уместился тысячесловный массив, который нужно умножить на квадратную матрицу. Вектор лежит слева. В памяти места ещё ну слов сто от силы. Матрица на ленте написана построчно. И как?

[venco]

gris в сообщении #355847 писал(а):

venco, и Вы скептически поглядываете в мою сторону.

Разве я дал повод к этому?
Наоборот, я всячески поддерживаю идею хранения матрицы в транспонированном виде. Выгодно везде, кроме памяти. Мне даже кажется, есть такие сценарии, что быстрее будет вычислять оба варианта матриц (прямой и транспонированный) из двух вариантов операндов, чем транспонировать при необходимости.

[y_nikolaenko]

venco
Для перемножения матриц по барабану, в каком виде они хранятся: в транспонированном или нет.

[venco]

y_nikolaenko в сообщении #355852 писал(а):

venco
Для перемножения матриц по барабану, в каком виде они хранятся: в транспонированном или нет.

А если одна - в прямом, а другая - в транспонированном?

[gris]

Я бы не сказал, что совсем по барабану. Левая по строкам, правая по столбцам - самое оно. А если наоборот?

[y_nikolaenko]

gris,

Я Вас не обманываю.

[gris]

y_nikolaenko, Вы только и говорите: я не обманываю, самому можно догадаться, всех в шею, это очевидно.
А конкретно ни-че-го не сказали.
Даже такой простой вопрос умножение вектора на матрицу. Вектор загнан в память. Первый вариант - матрица записана на ленте по строкам, второй - по столбцам. Результат надо на ленту записать. Неужели нет большой разницы во времени?

[y_nikolaenko]

gris,

не обижайтесь: здесь не место для лекций, а современные технологии перемножения матриц довольно сложны. А про шею: это Вы зря.