Методы работы с разреженными матрицами произвольного вида. Глушакова Т.Н - 24 стр.

                                    24
  (1) Решить первую подсистему, для которой А11 является матрицей
коэффициентов, относительно первых n1 неизвестных. Вычислить вектор x1
порядка n1.
  (2) Вычесть произведение Aj1x1 из j-й правой части для j = 2, …, N. Будет
получена блочная нижняя треугольная матрица порядка N – 1, и процедура
повторяется, пока не будет вычислено полное решение.
Следует сделать предположение о невырожденности диагональных блоков в
системе (22).
   Матрица имеет полную трансверсаль, если все ее диагональные элементы
не равны нулю. Трансверсаль есть в точности множество ненулевых
диагональных элементов. Всякую невырожденную матрицу A посредством
несимметричных перестановок с подходящими матрицами P и Q можно
переупорядочить так, чтобы PAQ имела полную трансверсаль. Обратное
неверно.
   Когда матрица A заданной линейной системы (1) имеет полную
трансверсаль, блочную нижнюю треугольную форму (22) можно получить
путем симметричных перестановок вида PAPT. Если существует блочная
форма, то A называют разложимой матрицей. Некоторые матрицы не могут
быть приведены к (нетривиальной) блочной нижней треугольной форме. Это
почти    всегда    так     для   систем,    полученных      дискретизацией
дифференциальных уравнений с частными производными. В других случаях
разложимость матрицы может быть известна из ее построения.
   Если A содержит нули на главной диагонали, то необходимо получить
полную трансверсаль, прежде чем пытаться переупорядочить матрицу к
блочной форме. Получение полной трансверсали требует несимметричных
перестановок. Матрицу, допускающую несимметричное переупорядочение к
форме с полной трансверсалью, а затем симметричное переупорядочение к
блочной нижней треугольной форме, будем называть двояко разложимой.
   Теория графов играет важную роль в анализе разреженных
несимметричных матриц. Со всякой несимметричной матрицей, имеющей
полную трансверсаль, можно связать ориентированный граф, или орграф.
Орграф инвариантен относительно симметричных перестановок строк и
столбцов матрицы, меняется лишь его помечивание. Орграф может быть
разбит на сильные компоненты, соответствующие диагональным блокам
блочной нижней треугольной формы (22) данной матрицы. Матрица
разложима тогда и только тогда, когда ее орграф может быть разбит на
сильные компоненты. Обе задачи – приведение разреженной матрицы и
разбиение орграфа – эквивалентны, и для обеих используются одни и те же
алгоритмы.
   Если матрица не имеет полной трансверсали, то с ней можно
ассоциировать двудольный граф. Двудольный граф инвариантен
относительно несимметричных перестановок матрицы, и получение
трансверсали эквивалентно отысканию паросочетаний в двудольном графе.
   Приведем несколько определений, которые нам потребуются в
дальнейшем.