Огромные объёмы данных и работа с ними

← →
bodomizer © (2004-11-29 10:57) [0]

Столкнулся вот с необходимостью решать СЛАУ порядка от 10^4 и выше, до бесконечности :)
Простой расчёт показал, что для хранения этой СЛАУ мне понадобится 32*N*N байт - из них 16*N*N, в принципе, можно удалить, но только после формирования конечной матрицы. Вдобавок используется ещё около 10*N байт в оперативе, но это уже мелочи, при необходимости перекинуть их в файлы не составит труда и не вызовет таких проблем, как основной объём.

Собственно, вопрос - что делать при N от 10^6? У меня таких винтов нету :)
Дайте плз советы и ссылки либо по оптимизации объёма самой СЛАУ, либо по каким-то методам архивации, что ли... Я что-то в тупик встал уже, гуглевание не помогает пока...
Кстати, если кто-то ткнёт меня в сайт, посвящённый такой вот математике и её реализации в Дельфях - тоже большое спасибо скажу.

← →
Alexander Panov © (2004-11-29 11:10) [1]

А СЛАУ - это что такое?

← →
KSergey © (2004-11-29 11:18) [2]

система линейных алгебраических уравнений

К стати, поиск в яндексе по этому слову дает в основном тексты вроде "Алгоритм компактного хранения и решения СЛАУ высокого порядка." Хотя, конечно, не факт, что это полностью устраивающее автора... Но факт, что это есть - обнадеживает, верно? ;)

← →
MBo © (2004-11-29 11:41) [3]

Если матрица разреженная, то существуют специальные методы работы с ними. Если нет - кое что можно сделать, деля матрицу на подматрицы.
http://www.library.cornell.edu/nr/cbookcpdf.html
также поиск по LINPACK

← →
bodomizer © (2004-11-29 13:34) [4]

KSergey ©:
К сожалению, как обычно случается с рефератами, все ссылки на эту тему ведут на разные сайты с одним и тем же рефератом. В реферате матрица оптимизируется удалением из неё нулей. У меня матрица комплексных чисел, нулей там не предвидится ввиду специфики задачи (это отражения волны от всех точек трассы), так что в сухом остатке только обзор методов решения СЛАУ :)

MBo ©:
Большое спасибо за книгу, погляжу, почитаю.
А про деление на подматрицы: имеется ввиду LU-деление или какое-то другое? если другое, опять же, хочется (хотеть не вредно :) ) найти модулёк для образца... Насколько я понял, оба деления (LU и QR) выигрыша с местом не дадут. Даже наоборот, удвоят затраты места, т.к. нули в них, опять же, будут занимать место. Хотя, опять же, ещё не читал эти методы подробно.

А про LINPACK, честно говоря, не понял. Тот же Яндекс говорит, что это какой-то тест-тул...

← →
MBo © (2004-11-29 13:57) [5]

>А про деление на подматрицы: имеется ввиду LU-деление или какое-то другое?
нет. Я встречался с этим при рассмотрении обратных матриц - исходная матрица делится на 4 части (две квадратных и две прямоугльных или все квадратные n/2), каждая по отдельности обращается, затем обратная матрица с помощью опред. соотношений синтезируется из кусков. Это выгодно при некоторых специальных видах исходной матрицы. Сам я дела с гигантскими матрицами не имел, практических советов дать не могу.
LINPACK упоминается в указанной книге - это много лет разрабатывающаяся фортрановская библиотека, возможно, есть порт на С. В прошлые времена проблемы с памятью были еще острее, так что в ней должны быть средства для работы с матрицами по кускам.

← →
bodomizer © (2004-11-29 14:53) [6]

Понятно, спасибо, нашёл какой-то "перевод" на С, не похоже, правда, что там есть какая-то оптимизация работыв с памятью, т.к. матрица всего 200*200.
Буду разбираться. По крайней мере для начала попробую его переписать в дельфю и в лоб порешать. Хотя на это ой-сколько времени уйдёт...

← →
bodomizer © (2004-11-30 09:36) [7]

Мда, с переписыванием в дельфю я поторопился, недооценил объём работ :)

← →
Algol (2004-11-30 13:35) [8]

Мне вот интересно, а как автор собирается решать эту СЛАУ ?
При таком числе уравнений оно вырожденно - 100%

← →
Думкин © (2004-11-30 13:44) [9]

> [8] Algol (30.11.04 13:35)

А обосновать?

← →
bodomizer © (2004-11-30 13:59) [10]

Да, пообоснованней хотелось бы.
Я сам в теоретизировании не особо силён, для этого у меня руководитель есть, который по мере надобности объясняет, но: как можно априорно утверждать о вырожденности СЛАУ только на основании её порядка?

А "как" решать - в принципе, тоже хороший вопрос, ответ на который я пока не выбрал. Точнее, не нашёл :) Неохота с нуля писать.

>При таком числе уравнений оно вырожденно - 100%
Насчет вырожденности - не факт, однако при решении систем с большим N происходит потеря точности. Считается, что обычные методы решения с использованием Single применимы для N<100,
с Double - для N<3-10 тысяч (верхняя граница достигается при использовании SVD - видимо, наиболее точного из общих методов, для гауссообразных алгоритмов - в несколько раз меньше).
Возможно, существуют специальные методы для гигантских систем - но это отдельная наука.

Зависит от обусловленности системы.

← →
Algol (2004-11-30 15:06) [14]

Точно обосновать конечно невозможно, поскольку можно показать что существуют такие невырожденные системы (взять например единичную матрицу).
Но эмпирически можно основываться на следующем:
1)Для того что бы система была вырожденна - достаточно что бы строка/столбец был линейной комбинацией любых других строк/столбцов. А вероятность что такая комбинация найдется - растет с N.
2)Поскольку неопределенность СЛАУ зависит от разности макс и минимального собственных чисел матрицы, то при увеличении N (и соответственно увеличении числа СЧ) - эта разность с большей вероятностью будет увеличиваться. И соответственно, определенность системы будет падать.
3)Я просто по работе сталкиваюсь часто с решением СЛАУ, и знаю что решить систему 1000*1000 очень сложно, из-за плохоопределнности.(правда, возможно, это специфика моей прикладной области - статистики)

//правда, возможно, это специфика моей прикладной области - статистики

Угу, в моём случае все элементы матрицы, кроме диагональных, меньше единицы. Диагональные же искусственно выделены прибавлением к ним единицы. Похоже, это поможет её определить получше :)

Огромные объёмы данных и работа с ними Найти похожие ветки