|
Добрый день,
есть такие иерархические матрицы - H-матрицы, в которых находятся большие блоки с малым рангом, каждый такой блок можно хорошо аппроксимировать и, в результате, сохранить такую матрицу с меньше, чем квадратичными затратами по памяти, причем матрица сама может быть (и обычно бывает) не вырожденной. Когда-то это придумали А. Еремин с Л. Колотилиной, потом идею подхватили Тыртышников и Хакбуш, и много кто этим занимались (кстати на Еремина забывая ссылаться).
Но для разбиения на такие блоки нужна информация какое интегральное уравнение было дискретизовано.
У меня возникла задача, построить матрицу, зная ее каждый элемент, но при построении - сразу сжать. Каждый элемент матрицы - либо 1, либо 0, сжатие всегда должно быть точным.
Любая небольшого размера подматрица на диагонали либо не вырождена, либо имеет почти максимальный ранг. Ручным перебором на раз находятся огромные 1000х1000 блоки с или 1, или с 0.
Размеры - около 50 миллионов на 50 миллионов, матрица не симметричная. В дальнейшем будет дополняться до больших размеров и также нужна процедура такого апдейта.
Хочется не потратить 300 ТБ памяти, и не более одного раза вычислить каждый матричный элемент, стоимость вычисления которого довольно высока (я ожидаю, что все матричные элементы на небольшом суперкомпьютере будут строиться около года.
У Хакбуша и Тыртышникова читал, все всегда требовало интегральное уравнение, скажите, пожалуйста, есть ли какие-то методы и как они называются, чтобы строить такие иерархические матрицы не зная на перед разбиение?
Спасибо!
|
