ОЧЕНЬ большие матрицы, алгоритмы для диагонализации

[molkee]

Недавно заинтересовался одной проблемой. Требовалось получить уровнии энергии для одной системы, решив у. Шредингера . При использовании одного из возможных подходов решение сводится к диагонализации разреженной (sparse) симметричной матрицы ( имеется ввиду то, что большинство элементов равны 0), размер которой естественно определяет количество полученных таким образом уровней энергии.

Проблема в том, что для диагонализации очень больших матриц на моем компьютере (4 Gb Ram, Intel Core i5) просто не хватает памяти. Я могу диагонализировать матрицу 10000 х 10000, все что больше - вылазит за пределы оперативки и начинаются тормоза. Моя программа написана на python, для диагонализации использовалась функция из библиотеки numpy . Очень бы хотелось научиться работать с матрицами в 10 раз больше - т.е где-то 100000 на 100000.

Обращаюсь к форумчанам. Может кто-нибудь подскажет какой алгоритм лучше использовать в моем случае? Я не специалист в численных методах, но понимаю, что просто не хватает памяти для хранения элементов матрицы в промежуточных стадиях. Какие алгоритмы наименее требовательны к памяти в этом отношении? Нужно получить все собственные значения (eigenvalues), а не несколько первых или ,скажем, самое большое по величине. Интуитивно понимаю, что решение должно быть - диагонализация матриц такого размера обычное дело при квантовохимических расчетах.

[Droog_Andrey]

С матрицами размером порядка 10⁶ на 10⁶ легко справлялись ещё 10 лет назад на обычных настольных ПК:
http://en.wikipedia.org/wiki/Lanczos_algorithm

А с ОЧЕНЬ большими можно использовать алгоритм, допускающий распределение на много ядер:
http://en.wikipedia.org/wiki/Block_Wiedemann_algorithm

[molkee]

Насколько я знаю, алгоритм Ланцоша полезен когда нужно найти несколько СЗ ( либо наименьших, либо наибольших) .А как насчет ВСЕХ СЗ?

[Yurii]

Для диагонализации в памяти достаточно хранить только немногим более, чем пол матрицы. Для 4 гигов памяти размер максимальной матрицы равен примерно 30000*30000 (при вычислениях с двойной точностью).

[molkee]

С матрицами размером порядка 106 на 106 легко справлялись ещё 10 лет назад на обычных настольных ПК:

что-то мне сейчас в это не верится, есть объективные требования к памяти, с которыми ничего не поделать.

пользую алгоритм Ланцоша, но без успехов пока

[Yurii]

пользую алгоритм Ланцоша, но без успехов пока

Успехов и не будет.

[molkee]

А как же заявление Droog_Andrey про 10^6?

может я просто не понимаю, что он имеет ввиду. в моем случае "справится" - получить ВСЕ собственные значения матрицы 60000 на 60000.

Кстати, как зависит время расчета и затраты памяти от размерности матрицы в различных алгоритмах? Кто подскажет? насколько я понимаю, n**2 в двух случаях.

[Droog_Andrey]

А как же заявление Droog_Andrey про 10^6?

http://krum.rz.uni-mannheim.de/cabench/ ... ecord.html
http://xyyxf.at.tut.by/news.html#0 (новость от 22.10.2002)
http://www.mersenneforum.org/showthread.php?t=13550

Но в алгоритме SNFS, действительно, нужны не все собственные значения.

[Yurii]

Кстати, как зависит время расчета и затраты памяти от размерности матрицы в различных алгоритмах? Кто подскажет? насколько я понимаю, n**2 в двух случаях.

n**2 для памяти и n**3 для времени расчета.

получить ВСЕ собственные значения матрицы 60000 на 60000.

Достаточно 16 гигов оперативной памяти. Она сейчас дешевая, так что это не проблема.