2014 dxdy logo

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

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




На страницу 1, 2, 3, 4  След.
 
 хранение в памяти больших матриц
Сообщение23.09.2010, 22:01 
Всем доброго дня.
Столкнулся с проблемой хранения в памяти больших матриц. Т.е. если использовать для хранения матриц обычные массивы,
Код:
double[][] matrix=new double[n][n];

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

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

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

 
 
 
 Re: хранение в памяти больших матриц
Сообщение23.09.2010, 22:33 
EugenePhoenixurl писал(а):
Всем доброго дня.
Столкнулся с проблемой хранения в памяти больших матриц. Т.е. если использовать для хранения матриц обычные массивы,
Код:
double[][] matrix=new double[n][n];

...

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

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

y_nikolaenko писал(а):
Не надо так хранить: храните в виде одномерного массива.

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

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

 
 
 
 Re: хранение в памяти больших матриц
Сообщение23.09.2010, 23:18 
venco писал(а):
Забыл ещё вариант: докупить ОЗУ, при необходимости перейти на 64-битную ОС.

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

 
 
 
 Re: хранение в памяти больших матриц
Сообщение23.09.2010, 23:37 
EugenePhoenix писал(а):
Само по себе хранение в виде одномерного массива не дает никаких преимуществ.

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

 
 
 
 Re: хранение в памяти больших матриц
Сообщение24.09.2010, 01:22 
y_nikolaenko писал(а):
Дает. Со временем поймете.


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

 
 
 
 Re: хранение в памяти больших матриц
Сообщение24.09.2010, 05:18 
EugenePhoenix в сообщении #355682 писал(а):
Но это не решает основной проблемы, изложенной в начале темы.
Потому что проблема, как для хранения $n^2$ чисел использовать меньше, чем $n^2$ ячеек памяти, не имеет решения.
То есть, если нет никакой регулярной структуры и/или повторов. В первом случае надо пользоваться явно этой структурой, во втором -- стандартными алгоритмами сжатия. А если числа "случайные", то как вы в принципе себе это представляете?
Чтобы в памяти хранилась не матрица, а её часть -- вам надо смотреть в сторону параллельных вычислений. Там именно эта проблема активно решается когда матрицу раскидывают по процессорам. Почитайте UG к какому-нибудь PBLAS.

 
 
 
 Re: хранение в памяти больших матриц
Сообщение24.09.2010, 12:06 
EugenePhoenix в сообщении #355682 писал(а):
y_nikolaenko писал(а):
Дает. Со временем поймете.


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

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

 
 
 
 Re: хранение в памяти больших матриц
Сообщение24.09.2010, 13:48 
Подобно тому, что к концу своего поста советует nestoklon, можете
пойти по линку:

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

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

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

 
 
 
 Re: хранение в памяти больших матриц
Сообщение24.09.2010, 15:41 
Все ясно. Всем спасибо за ответы.

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

 
 
 
 Re: хранение в памяти больших матриц
Сообщение24.09.2010, 16:23 
gris в сообщении #355799 писал(а):
Кстати о далёком прошлом. Была такая задача, помнится на М20, периодически умножать длиннющий вектор на соответственно огромные матрицы. Приходящий вектор считывался в память, а места для матрицы, естественно, не было. Умножать надо было то слева, то справа. Так вот каждая матрица, а они были достаточно постоянными, хранилась на двух лентах в двух экземплярах - в записях по строкам и в записях по столбцам.

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

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

 
 
 [ Сообщений: 50 ]  На страницу 1, 2, 3, 4  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group