Синтаксис:

             p = colmmd(S)

Описание:

Функция p = colmmd(S) возвращает такой вектор упорядоченности столбцов для несимметрической матрицы S, что S(:, p) будет иметь более разреженное LU-разложение, чем S.

Такое упорядочение автоматически применяется системой MATLAB при выполнении операций обращения \ и / при решении систем линейных уравнений с разреженными матрицами.

Алгоритм:

Алгоритм упорядочения по разреженности столбцов для симметрических матриц описан в обзоре Джорджа (George) и Лиу (Liu) [1]. Для несимметрических матриц аналогичный алгоритм разработан заново и описан в работе Гилберта (Gilbert), Моулера (Moler) и Шрайбера (Schriber) [2]. Он напоминает прежний алгоритм для матрицы A’ * A, но в действительности такая матрица не формируется.

На каждом шагу алгоритма из оставшихся выбирается вершина низшего порядка, то есть столбец, имеющий минимальное количество ненулевых элементов, удаляет эту вершину и строит новый граф, объединяя строки. После n шагов все столбцы оказываются удаленными и перестановка завершается. Для ускорения этого процесса используются специальные приемы для одновременного выполнения нескольких шагов.

Пример:

Коллекция разреженных матриц фирмы Harwell-Boeing включает тестовую матрицу abb313. Это прямоугольная матрица размера 313 х 176, связанная с задачей оценки по методу наименьших квадратов геодезических данных. При решении задачи возникает вспомогательная матрица S, генерируемая функцией spaugment. Она является квадратной и имеет порядок 489.

           load abb313.mat
           S = spaugment(abb313);
           p = colmmd(S);
           spy(S)
           spy(S(:, p))

          spy(lu(S))
          spy(lu(S(:, p))

Сопутствующие функции: SYMMMD, SYMRCM, COLPERM, LU, SPPARMS.

Ссылки:

1. George A., Liu J. The evolution of the minimum degree ordering algorithm//SIAM Review. 1989. Vol. 31. P. 1-19.

2. Gilbert J. R., Moler C., Schreiber R. Sparse Matrices in MATLAB: Design and Implementation//SIAM Journal on Matrix Analysis and Applications. 1992. Vol. 13. P. 333-356