MATLAB.Exponenta
MATLAB и Simulink на русском
Технологии разработки и отладки
		сложных технических систем

MATLAB\MATLAB

В.Г.Потемкин "Справочник по MATLAB"
Работа с разреженными матрицами

  В оглавление книги \ К следующему разделу \ К предыдущему разделу

Алгоритмы упорядочения

SYMMMD
Симметрическая упорядоченность

Синтаксис:

            p = symmmd(S)

Описание:

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

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

Алгоритм:

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

Пример:

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

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

Сопутствующие функции: 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.

image914.gif (2050 bytes) image915.gif (1375 bytes)
а) б)
image916.gif (871 bytes) image917.gif (871 bytes)
в) г)
image918.gif (917 bytes) image919.gif (903 bytes)

  В оглавление книги \ К следующему разделу \ К предыдущему разделу

 


Поиск по сайту:

Система Orphus

Яндекс.Метрика