Синтаксис:

            p = symmmd(S)

Описание:

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

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

Алгоритм:

Алгоритм упорядочения для симметрических матриц основан на алгоритме упорядочения по разреженности столбцов. Фактически функция symmmd формирует матрицу K с такой структурой ненулевых элементов, что симметрическая матрица K’ * K имеет такую же структуру ненулевых элементов, как и исходная матрица S, а затем вызывается функция colmmd для K.

Пример:

Сравним два алгоритма упорядочения, реализованные в виде функций symrcm и symmmd, которые предшествуют LL^T-разложению (разложение Холецкого) матрицы bucky размера 60 х 60, которая описывает граф связности bucky (рис. а) и имеет структуру (рис. б).

Хотя эта задача и не является очень сложной, тем не менее поведение алгоритмов упорядочения является типичным. Применение функции symrcm порождает ленточную матрицу (рис. в), которая после LL^T-разложения оказывается целиком заполненной внутри ленты (рис. д). Применение функции symmmd порождает ленточную матрицу с крупными блоками нулевых элементов (рис. г), которые не заполняются и в процессе LL^T-разложения (рис. е). Следовательно, алгоритм симметрической разреженности требует меньшего времени и объема памяти в процессе LL^T-разложения.

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

Ссылки:

1. 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.

а)	б)
в)	г)