Как программисты работают с большими массивами? , Решение СЛАУ, не помещающихся в оперативной памяти

Есть еще вариация метода Гаусса - метод Жордана. Приводит матрицу сразу к диагональной единичной матрице. Можно обрабатывать матрицу построчно. Ввел строку, обработал вместе с предыдущими, чтобы левая часть была единичной матрицей (ее и хранить не нужно). Требования по памяти порядка четверти размера всей матрицы, максимум - на середине матрицы.

Не уверен, что это подойдет - ведь предыдущие строки наверняка надо хранить в памяти, на каждой новой строке проходить по ним.

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

Да, это модификация метода исключения Гаусса, точнее метода Жордана-Гаусса, но требования к памяти несколько ниже, чем у классических алгоритмов (есть еще так называемый метод оптимального исключения, у которого требования к памяти, вроде, еще меньше). Кроме того, по-моему, и среди блочно-матричных алгоритмов многие позволяют подобную оптимизацию использования памяти. Увеличивается размер блока, уменьшается число обращений к диску.

И еще, небольшая модификация этого метода позволяет решать системы, даже четверть матрицы которых не помещаетмся в память, проходя файл с матрицей несколько раз.

Еще про память.
Пусть мы имеем m систем n-го порядка с одинаковой матрицей, то есть расширенная матрица имеет размер n*(n+m)
При решении системы получается последовательность матриц размеров:
1*(n+m-1), 2*(n+m-2), 3*(n+m-3), ..., (n-1)*(m+1), n*(m), которые могут быть размещены по одному и тому же адресу (при построчном порядке, как в C). Последняя матрица будет содержать решения.

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

Цитата experimenter @ 06.11.07, 08:25

Да, теперь понимаю. Ну, тогда давайте предложим человеку купить майнфрейм.

Гм... Ну зачем же покупать? можно арендовать.
Мне стало интересно - порылся по теме в инете и нашол некоторые цифры:

Цитата с какого то форума

... на западе, там стоимость одного гигагерца маширнного времени за час: 1 доллар, у нас (в России) 0,15 - 0,20, то есть в 5-7 раз меньше...

Сообщение отредактировано: Alexus - 08.11.07, 05:10

Цитата Alexus @ 08.11.07, 05:08

Гм... Ну зачем же покупать? можно арендовать.
Мне стало интересно - порылся по теме в инете и нашол некоторые цифры:

Хорошая идея, кстати. Мне в голову не пришла даже. Только думаю, что нормальный мейнфрейм в России найти не так уж и просто. Тем более, чтоб тебя на него пустили попастись.

В любом случае, прежде необходимо отаработать сам алгоритм на простом ПК.

Цитата Telc @ 08.11.07, 12:45

В любом случае, прежде необходимо отаработать сам алгоритм на простом ПК.

А до этого лучше на бумажке!

Не влезая в дебри теории, личн я бы подошёл к проблеме чисто технически

Преобразовал бы массив в список - т.е. паре (i, j) сопоставляется значение. И есть небольшой классик, который в себе умеет держать набор этих значений. Да, матрицы не разреженные, экономии это не даст
Зато есть возможность контролировать размер занимаемой памяти - (sizeof(i)*2 + sizeof(value))*current_loaded_items
Ну а далее уже можно тупо считывать с диска все записи, пока забьём отведенный размер. А после - считывать по надобности, высвобождая самые "старые" значения. Дешёво и сердито. И время на реализацию - 1-2 часа

Нет я конечно могу понять желание решить в лоб 50000 уравнений, но даже если удастья представить в памяти такой объём данных, то врядли стоит завидовать человеку, которому предстоит дождаться решения данной системы, к тому же хранить только те данные которые могут быть вычеслены это ещё более нагрузка на ЦП, да и где гарант, что система окажется совместна или не будет имет бесконечное множество решении. В жизни не видел ситуации где бы могло понадобится такое количество корней для чего либо. С другой стороны использовать жесткий диск конечно можно, но тогда необходимо минимизировать количество обращений к нему. Например если для решения системы используется всеми горячо любимый метод Гаусса, то можно хранить отдеьные строки (в количестве 2 штук) на прямом и обратном ходе алгоритма, после этого, в случае если система является невырожденной(по сути каждой переменной соотвестует едиснтвенное решение), то необходимо, считать только диагональные элементы, в противном случае лучше сразу бить в барабаны, потомучто даже если можно будет наити аналитическую форму записи для свободных переменных, то анализ такой системы в большинстве случаем сведётся к поиску оптимума, а вот эта задача скорее всего уже приведёт к ожиданию конца вычислении, ну как минимум до пенсии уважаемого Telc. Другого способа просто нет.

Блин. Ну почему постоянно у всех есть желание изобретать велосипед? Блочно-матричные алгоритмы - самое простое и естественное решение проблемы обращений к жесткому диску. Не надо никаких списков (для линейной алгебры вообще смерть - замедление в десятки раз), не надо ничего вообще. Матрица обрабатывается не по строкам, а по блокам. Соотношение между размером задачи и количеством доступной оперативной памяти естественным образом преобразуется в размер обрабатываемого блока. Число считываний элемента матрицы с жесткого диска не N (как в обычном алгоритме), а N/K, где K - размер блока.

Мне кажется, это идеальное решение. Только сложное, и мало кто о нем знает, т.к. в университетском курсе численных методов линейную алгебру читают на уровне чуть ли не 50-ых годов (по крайней мере, мне так читали).