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

                                                      23
Spc состоит из ненулевых элементов p строк активной подматрицы. Выбор
указанных          p строк осуществляется из соображений улучшения
разреженности, например, это могут быть p строк, имеющих наименьшее
количество ненулевых элементов на k-м шаге исключения. Условия
устойчивости, используемые для того, чтобы определить, какие элементы из
Spc принадлежат множеству Sst, те же, что и в стратегии порогового выбора
главного элемента по строкам, и определяются неравенством (21б).
Множество Ssp определяется как подмножество Sst на основе следующего
критерия, обеспечивающего локальную оптимизацию разреженности:
считается, что элемент aij(k ) из Sst принадлежит Ssp, если μij ≡ (ri – 1)(cj – 1) = μ,
где μ=mini,j(μij), ri – число активных ненулевых элементов в i-й строке на k-м
шаге исключения, а cj – число активных ненулевых элементов в j-м столбце
на k-м шаге исключения. Другими словами, множество Ssp содержит все
ненулевые элементы из Sst, для которых произведение числа всех остальных
ненулевых элементов в той же строке на число всех остальных активных
ненулевых элементов в том же столбце минимально (перед началом
выполнения k-го шага). В этом случае множество Spiv совпадает с Ssp.
    Стратегия Златева заключается в выборе в качестве главного любого
элемента из Spiv. Улучшенная стратегия Златева использует в качестве
главного элемент из Spiv, имеющий наибольшее абсолютное значение.
Обычно обе стратегии дают примерно одинаковую точность, однако
улучшенная стратегия позволяет получить лучшие результаты в некоторых
трудных случаях, так как устраняются «плохие» последовательности главных
элементов, допускаемые первой стратегией.

       3. Теория графов для разреженных матриц
     Если свойства матрицы A неизвестны, возможно, имеет смысл
попытаться до начала исключения переупорядочить ее к блочной нижней
треугольной форме. Линейная система с блочной нижней треугольной
матрицей блочного порядка N имеет вид

                       � A11                             � � x1 � � b1 �
                        � A           A22                 � � x � � b �
                         � 21                              � � 2 � =� 2 � ,       (22)
                          � Μ                   Ο           � � Μ� � Μ�
                           �                                 � �  � �    �
                             � AN 1                 ANN � � x N � � bN �

где элементами являются матрицы, каждый диагональный блок Aii –
                                            N
квадратный порядка ni, и                    ∑
                                            i =1
                                                 ni =n .   Систему (22) можно решать как

последовательность N меньших задач. Задача i имеет порядок ni и матрицу
коэффициентов Aii, i=1,2,…, N. При этом заполнение будет происходить
только в диагональных блоках, даже если выбор главных элементов вызвал
несимметричные перестановки строк и столбцов каждого блока. Процедура
такова: