Comments 11
Для разреженных матриц огромная часть алгоритмов реализована в SuiteSparse. В вашем случае - в подразделе для LDL:
https://github.com/DrTimothyAldenDavis/SuiteSparse/tree/dev/LDL и документация https://github.com/DrTimothyAldenDavis/SuiteSparse/blob/dev/LDL/Doc/ldl_userguide.pdf
Стандартный подход: 1) анализ как разрежена матрица 2) символьное разложение LDL (только учитывая что (i,j)-элемент ненулевой 3) численное разложение LDL.
Не очень понимаю мотивацию данной статьи, которая сваливает все в одну кучу, не делит на этапы и мало что рассказывает об алгоритме.
Подскажите, пожалуйста, системы с какими матрицами можно решить методом LDL, которые нельзя решить методом Холецкого (разложение матрицы в виде L*D*L^t, где L нижнетреугольная, D диагональная с +1/-1 на диагонали)?
Ниже уже написали о том, что в методе Холецкого матрица А должна быть положительно определенной. В этом методе используется квадратный корень, и когда для него получаются отрицательные числа, то матрица L получается комплексной, а это уже другая история.
Вообще под методом Холецкого подразумевается разложение L*L^t, а ваш вариант с L*D*L^t я не рассматривал.
Когда я учился в университете нам рассказывали именно такой вариант. Для этого метода матрица не обязательна быть положительно определенной. Когда возникает необходимость извлекать квадратный корень sqrt(x), то извлекается корень из модуля числа sqrt(abs(x)), а диагональный элемент принимает значение знака того числа из модуля которого извлекается корень sign(x). Это существенно расширяет класс "хороших" матриц.
Вы не упомянули о том, что в методе Холецкого матрица А должна быть положительно определена.
Почему выбор пал на точный метод вместо итерационного? Разве не будет расход памяти огромный?
Вначале для своих задач я пробовал метод сопряжённых градиентов. Но он давал неважную точность, а увеличение количества итераций съедало преимущество по времени по сравнению с обычным LDLt. Далее я придумал убирать лидирующие нули. Получилось и быстрее, и точнее. Что касается памяти, то матрица записывается в компактном виде без лидирующих нулей, и в моей практике её размерность редко превосходила нескольких тысяч. В общем с памятью проблем не было.
Решение СЛАУ с симметричной разреженной матрицей