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

                                    42
произведение n(c)n(r). Стандартный критерий устойчивости – это отбор
по барьеру. Spc содержит все ненулевые элементы активной подматрицы, Sst –
те элементы из Spc, которые подчиняются принятому критерию устойчивости.
Ssp – это подмножество Sst, выделяемое условием Марковица. В общем случае
Ssp может содержать несколько ненулевых элементов. Наконец, главный
элемент – это любой элемент из Spiv ≡ Ssp.
Одна из сильных сторон стратегии Марковица – ее симметрия. Это означает,
что (если не учитывать влияние критерия устойчивости и неоднозначности
выбора) для обеих матриц A и AT получается одно и то же упорядочение.
Стоимость алгоритма Марковица существенно зависит от размера множества
Sst на каждом шаге, поскольку произведение n(c)n(r) должно вычисляться для
любого элемента из Sst.
    Для реализации методы Марковица требуется два целых массива, в
которые поначалу записывается число ненулевых внедиагональных
элементов соответственно каждой строки и каждого столбца А. Эти массивы
переопределяются от шага к шагу с учетом исключаемых элементов и
заполнения.

      3.2.9 Стратегия Даффа
      Дафф предложил более дешевую стратегию, называемую ri в cj, или
минимальная строка в минимальном столбце. Эта стратегия не имеет
симметрии. Формулируется она так: на каждом шаге выбирается столбец с
наименьшим числом ненулевых элементов. Затем среди ненулевых
элементов этого столбца, удовлетворяющих принятому критерию
устойчивости, выбирается тот, что стоит в строке с наименьшим числом
ненулевых элементов. Здесь Spc содержит все ненулевые6 элементы активной
подматрицы, Ssp – ненулевые элементы столбца с наименьшим числом
ненулевых элементов, Sst – это подмножество Spc, выделяемое критерием
устойчивости, и Spiv ≡ Ssp. Наконец, главный элемент выбирается из Spiv
исходя из соображений разреженности. В некоторых случаях эта стратегия
работает гораздо хуже, чем стратегия Марковица. Ценой некоторой
дополнительной работы ее можно симметризовать. На каждом шаге
выполняется предписание стратегии ri в cj, а затем независимо – предписание
стратегии ck в rl (т.е. выбирается строка с наименьшим числом ненулевых
элементов, скажем, строка l, выбираются ненулевые элементы строки l,
подчиняющиеся критерию устойчивости, выбирается ненулевой элемент,
стоящий в столбце (скажем, k) с наименьшим числом ненулевых элементов).
Наконец, из двух найденных главных элементов берется тот, для которого
произведение n(c)n(r) меньше.

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