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

[EugenePhoenix]

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

double[][] matrix=new double[n][n];

то при некоторой критичной размерности матрицы n просто не хватает ОЗУ.
Если кто знает, подскажите какой-нибудь альтернативный вариант хранеия матриц. Наверно, чтобы в памяти находилась не вся матрица сразу, а только ее часть.
Заранее спасибо.

[venco]

Варианты:
1. Уменьшить размер элементов - int или float. Не всегда возможно, но зато легко реализуемо.
2. Воспользоваться какой-нибудь закономерностью в элементах, например:
2.1. если матрица содержит в основном нули, хранить только ненулевые значения (или области) вместе с их координатами.
2.2. если матрица обладает какой-нибудь симметрией, хранить только часть элементов, а остальные вычислять из симметрии.
2.3. если матрица раскладывается на небольшое количество произведений векторов, хранить вектора, а элементы матрицы вычислять.
Особые свойства из пункта 2 в дополнение могут позволить использовать более быстрые алгоритмы обработки матриц.

Сохранять же на диск может оказаться слишком неэффективным - дисковая память на несколько порядков медленнее оперативной.

[y_nikolaenko]

EugenePhoenixurl писал(а):

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

double[][] matrix=new double[n][n];

...

Не надо так хранить: храните в виде одномерного массива.
А остальное от алгоритма работы с матрицей зависит.

[EugenePhoenix]

venco, к сожалению, предложенные варианты не очень подходят. Хотелось бы чтобы алгоритм работал с любой(даже случайной) матрицей.

y_nikolaenko писал(а):

Не надо так хранить: храните в виде одномерного массива.

А немного поподробней можно? Само по себе хранение в виде одномерного массива не дает никаких преимуществ.

[venco]

Забыл ещё вариант: докупить ОЗУ, при необходимости перейти на 64-битную ОС.

[EugenePhoenix]

venco писал(а):

Забыл ещё вариант: докупить ОЗУ, при необходимости перейти на 64-битную ОС.

Неподходящий вариант. Мощи, конечно, нужно иногда наращивать, но в данном случае это просто мой личный интерес. Интересен вопрос оптимизации хранения матрицы в памяти или не полного ее хранения, а части.
Другими словами, чтобы алгоритм работал с матрицей любой размерности, даже если она занимает больше ОЗУ, чем доступно.
Ведь численные методы существуют уже давно, не верится, что хотя бы лет 10 назад были доступны такие вычислительные мощности. А большие матрицы уже и тогда были.

[y_nikolaenko]

EugenePhoenix писал(а):

Само по себе хранение в виде одномерного массива не дает никаких преимуществ.

Дает. Со временем поймете.

[EugenePhoenix]

y_nikolaenko писал(а):

Дает. Со временем поймете.

Наверно, лучше хранить в одномерном массиве размера $mXn$ и обращаться к элементу $A(i, j)$, как $a[i*n+j]$, т.к. одно целочисленное умножение и одно обращение к памяти работает быстрее, чем два обращения к памяти.
Но это не решает основной проблемы, изложенной в начале темы.

[nestoklon]

EugenePhoenix в сообщении #355682 писал(а):

Но это не решает основной проблемы, изложенной в начале темы.

Потому что проблема, как для хранения $n^2$ чисел использовать меньше, чем $n^2$ ячеек памяти, не имеет решения.
То есть, если нет никакой регулярной структуры и/или повторов. В первом случае надо пользоваться явно этой структурой, во втором -- стандартными алгоритмами сжатия. А если числа "случайные", то как вы в принципе себе это представляете?
Чтобы в памяти хранилась не матрица, а её часть -- вам надо смотреть в сторону параллельных вычислений. Там именно эта проблема активно решается когда матрицу раскидывают по процессорам. Почитайте UG к какому-нибудь PBLAS.

[y_nikolaenko]

EugenePhoenix в сообщении #355682 писал(а):

y_nikolaenko писал(а):

Дает. Со временем поймете.

Наверно, лучше хранить в одномерном массиве размера $mXn$ и обращаться к элементу $A(i, j)$, как $a[i*n+j]$, т.к. одно целочисленное умножение и одно обращение к памяти работает быстрее, чем два обращения к памяти.

Есть несколько причин, по которым предпочтительней хранить матрицу в одномерном массиве.

[Vassil]

Подобно тому, что к концу своего поста советует nestoklon, можете
пойти по линку:

http://www.srcc.msu.su/num_anal/par_prog/comparp.htm

где описан пакет НИВЦ МГУ под именем

Комплекс программ по линейной алгебре
для вычислений на распределенной памяти

[EugenePhoenix]

Все ясно. Всем спасибо за ответы.

[gris]

Кстати о далёком прошлом. Была такая задача, помнится на М20, периодически умножать длиннющий вектор на соответственно огромные матрицы. Приходящий вектор считывался в память, а места для матрицы, естественно, не было. Умножать надо было то слева, то справа. Так вот каждая матрица, а они были достаточно постоянными, хранилась на двух лентах в двух экземплярах - в записях по строкам и в записях по столбцам.

[y_nikolaenko]

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

Кстати о далёком прошлом. Была такая задача, помнится на М20, периодически умножать длиннющий вектор на соответственно огромные матрицы. Приходящий вектор считывался в память, а места для матрицы, естественно, не было. Умножать надо было то слева, то справа. Так вот каждая матрица, а они были достаточно постоянными, хранилась на двух лентах в двух экземплярах - в записях по строкам и в записях по столбцам.

Интересно, в какой конторе так делали? Если бы я был шефом, то разработчика сего алгоритма выгнал бы в шею.

[gris]

y_nikolaenko, а чем плохо? Двукратный проигрыш в памяти, зато весьма ощутимый выигрыш в скорости. Интересно, какой бы Вы алгоритм предложили?
Матрица вообще редко нужна сразу вся. Чаще всего нужен столбец, строка или некоторый непрерывный квадратный фрагмент.