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

                                      33
+ 1), идет вдоль строки k+1 до ненулевого            элемента,       стоящего,
скажем, в столбце l (хотя бы один такой элемент должен быть, иначе строка k
+ 1 целиком состоит из нулей, и A – вырожденная матрица), затем вдоль
столбца l до позиции (l, l), далее к внедиагональному ненулевому элементу
строки l, расположенному, скажем, в столбце m, и т.д. Другими слова, путь
попеременно проходит через диагональный и внедиагональный ненулевой
элементы. Путь не может дважды идти вдоль какой-либо строки или столбца
и заканчивается на ненулевом элементе подматрицы, образованной строками
1, …, k и столбцами k + 1, …, n. В памяти компьютера путь может
регистрироваться записью номеров диагональных позиций в том порядке, в
каком они посещались, т.е. k + 1, l, m, … . Поскольку некоторые
диагональные позиции могли быть посещены, а впоследствии удалены из
пути, нужно завести и список посещавшихся позиций, чтобы не войти в них
снова.
    Рассмотрим соответствующий пример. Чтобы построить нужный путь,
мы начинаем с позиции (k + 1, k + 1) и ищем в строке k + 1 ненулевой
элемент. Для невырожденной матрицы A такой должен найтись, потому что в
противном случае строка k + 1 целиком состояла бы из нулей. Если
ненулевой элемент стоит в столбце l, то мы переходим к строке l и ищем в
ней ненулевой элемент в столбах k+1, …, n. Если такой имеется, то путь
закончен. Если нет, то мы ищем в первых k позициях строки l ненулевой
элемент, который бы стоял в столбце, ранее не посещавшемся, скажем, в
столбце m. Далее мы переходим к строке m и повторяем вышеописанные
операции, пока путь не будет завершен. Если в некоторой строке не удается
найти внедиагональный ненулевой элемент в непосещавшемся столбце, то
эта строка удаляется из пути (но не из списка посещавшихся позиций), и мы
возвращаемся к предыдущей строке. Если на некотором шаге после
посещения r позиций в пределах от 1 до k наш путь становится пустым (т.е.
мы вернулись к начальному пункту), это означает, что A вырождена:
действительно, мы нашли r+1 строк (r посещавшихся строк плюс строка k +
1), имеющих ненулевые элементы только в r столбцах.
    Как только искомый путь построен (скажем, k + 1, l1, l2, …, lr, где lr > k),
мы переставляем r + 1 строк и два столбца, чтобы вывести последний
найденный ненулевой элемент в позицию (k + 1, k + 1). Нужны такие
перестановки строк: строка k + 1 становится строкой l1, строка l1 становится
строкой l2, …, строка lr-1 становится строкой k + 1.
    Поскольку строки выбирались так, чтобы ненулевой элемент строки li
стоял в позиции li+1, то при замене строки li строкой li+1 этот ненулевой
элемент попадает в диагональную позицию (li+1, li+1). Следовательно, после
строчных перестановок элементы в первых k позициях диагонали останутся
ненулевыми. Кроме того, последний ненулевой элемент пути будет
переведен в позицию (k +1, lr). Перестановка столбцов k + 1 и lr перемещает
его в позицию (k + 1, k + 1), чем (k+1)-й шаг завершается. Если lr = k + 1, то
перестановка столбцов не нужна.