Итерационный решатель

Реализует метод сопряженных градиентов с предобуславливанием неполного разложения Холецкого B = H∙H^T, где H – нижняя треугольная матрица. В программном комплексе SCAD разработан метод неполной факторизации Холецкого, основанный на технологии разреженных матриц, позволяющий существенно ускорить сходимость при умеренном увеличении размера неполного фактора Холецкого H [12-13]. Упорядочение производится алгоритмом минимальной степени [14].

Параметры отбрасывания и пост-отбрасывания ψ, ψ₁ (0 < ψ < ψ₁ < 1) управляют способностью предобуславливания ускорять сходимость. При разложении матрицы удерживаются только «малые элементы» – H_ij² ≥ ψ H_iiH_jj. Чем меньше ψ, тем ближе неполный фактор Холецкого H к полному фактору L и тем быстрее сходится решение. Однако при этом тем больший объем оперативной памяти необходим для хранения H и тем больше времени требуется для выполнения неполного разложения Холецкого и для выполнения итераций. Для слишком малых значений ψ может не хватить объема оперативной памяти. Тогда решатель увеличивает ψ в 10 раз и пробует снова выполнить неполное разложение Холецкого. И так до тех пор, пока неполный фактор Холецкого H удастся сохранить в оперативной памяти. Поэтому при повторных расчетах на этом же компьютере целесообразно воспользоваться опытом первого расчета и принять значение параметра ψ таким, при котором удалось завершить неполную факторизацию. Это позволит избежать лишних попыток разложения.

С другой стороны, на компьютерах с большим объемом оперативной памяти может оказаться, что слишком малое значение ψ приводит к значительному возрастанию времени неполной факторизации. Вообще способов определения оптимального значения параметра ψ не существует. Это зависит от обусловленности системы линейных алгебраических уравнений, объема оперативной памяти, размерности задачи, количества правых частей и необходимости выполнять модальный/сейсмический анализ. Поэтому дадим следующие рекомендации. На 32-разрядной платформе значение параметра ψ по умолчанию принимается 10^-9. С него и следует начинать. На 64-разрядной платформе большинство компьютеров на сегодняшний день располагают большим объемом доступной для операционной системы оперативной памяти. Поэтому мы рекомендуем принять значение ψ в пределах 10^-12 – 10^-14. Если для данной задачи окажется, что размер H превышает возможности оперативной памяти, то решатель Вас «поправит» и уменьшит ψ. Если неполное разложение Холецкого длится неоправданно долго, следует прервать вычисления и увеличить ψ.

После окончания факторизации производится вторичное отбрасывание – удерживаются только те элементы, для которых H_ij² ≥ ψ₁ H_iiH_jj. Это позволяет ускорить процедуру прямых/обратных подстановок в процессе итераций и уменьшить объем требуемой оперативной памяти. Обычно значение ψ₁ принимается на три порядка больше, чем значение ψ.

Процедура неполной факторизации распараллелена. Распараллеливание процедуры итераций осуществляется за счет того, что каждая правая часть итерируется независимо от остальных в отдельном потоке. Поэтому время решения задачи, содержащей большое количество загружений, существенно зависит от количества ядер (процессоров) на Вашем компьютере.

Итерационный процесс продолжается до тех пор, пока ε_i > ε_t, где ε_i = ||b_i – Kx_i||₂/||b_i||₂, i ∈ [1, N_r], ε_t – требуемая точность.

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

Итерационный решатель доступен для следующих видов анализа: линейная и нелинейная статика, модальный и сейсмический анализ (спектральный метод).