Использование полиномов Чебышёва и приближенного обратного треугольного разложения для предобусловливания метода сопряженных градиентов

Для предобусловливания симметричной положительно-определенной разреженной матрицы рассматривается ее приближенная обратная, представленная в виде произведения двух взаимно сопряженных разреженных треугольных матриц. Таким образом, решение соответствующей системы линейных алгебраических уравнений (СЛАУ) предобусловленным методом сопряженных градиентов (МСГ) требует лишь выполнения элементарных векторных операций, а также операций умножения разреженной матрицы на вектор. Описан и исследован метод построения указанного предобусловливателя при фиксированной структуре разреженности треугольного множителя, оптимального в смысле минимизации К-числа обусловленности предобусловленной матрицы. При этом существенно уменьшить долю операций скалярного произведения (при незначительном изменении суммарного числа арифметических операций) можно за счет дополнительного использования полиномиального предобусловливания на основе чебышёвских многочленов. Обсуждается возможность эффективной массивно-параллельной реализации полученного метода решения СЛАУ. Для последовательного прототипа метода приводятся результаты расчетов 56 тестовых задач из коллекции университета Флориды (отличающихся большими размерами и плохой обусловленностью), свидетельствующие о его высокой надежности и низких вычислительных затратах. Библ. 27.