Прямые методы решения больших разреженных систем уравнений на основе блочного порядка два разложения матрицы

Рассматриваются алгоритмы переупорядочения разреженной симметричной положительно определенной матрицы к блочной форме блочного порядка два; ставится задача о переупорядочении таком, что заполнение множителя Холецкого минимально в блоке (1,1) и концентрируется в основном в блоках $(2,1)$ и $(2,2)$. С этой точки зрения анализируются алгоритмы из известного пакета SPARSPAK: минимальной степени QMD и вложенных сечений ND; предложен новый алгоритм уравновешенных вложенных сечений с внутренним QMD-упорядочением – $\mathrm{BND}+\mathrm{qmd}$. Приводятся результаты численных экспериментов для сеточных задач с 10000–25000 неизвестными, показывающие, что благодаря предложенному блочному подходу удается достичь 25–30% экономии затрат памяти без заметного роста числа арифметических операций, требуемых на этапе решения треугольных систем; наилучшим является новый алгоритм $\mathrm{BND}+\mathrm{qmd}$.