Иллюстрированный самоучитель по MatLab › Функции разреженных матриц › Алгоритмы упорядочения [страница - 251] | Самоучители по математическим пакетам

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

Упорядочение – это еще одна характерная для разреженных матриц операция. Ее алгоритм реализуется несколькими функциями:

р = colmmd(S) – возвращает вектор упорядоченности столбцов разреженной матрицы S. [то nzmax(S) – максимальное количество ячеек для хранения ненулевых элементов. Если S – полная матрица, то nzmax(S)=numel(S).] Для несимметрической матрицы S вектор упорядоченности столбцов р такой, что S(:. р) будет иметь более разреженные L и U в LU-разложении, чем S. Такое упорядочение автоматически применяется при выполнении операций обращения \ и деления /, а также при решении систем линейных уравнений с разреженными матрицами. Можно использовать команду spparms, чтобы изменить некоторые параметры, связанные с эвристикой в алгоритме colmmd;
j = colperm(S) – возвращает вектор перестановок j, такой что столбцы матрицы S(: .j) будут упорядочены по возрастанию числа ненулевых элементов. Эту функцию полезно иногда применять перед выполнением LU-разложения. Если S – симметрическая матрица, то j=colperm(S) возвращает вектор перестановок j, такой что и столбцы, и строки S(j,j) упорядочены по возрастанию ненулевых элементов. Если матрица S положительно определенная, то иногда полезно применять эту функцию и перед выполнением разложения Холецкого.

Пример:

>> S=sparse([2.3.1.4.2].[l,3.2.3.2],[4.3.5.6.7].4.5);full(S) 
ans =
0 5 0 0 0
4 7 0 0 0
0 0 3 0 0
0 0 6 0 0
>> t=colperm(S) 
t=         
5 1 2 3 
>> full(S(;,t))          
ans =         
0 0 0 5 0 
0 0 4 7 0 
0 0 0 0 3 
0 0 0 0 6

p = dmperm(A) – возвращает вектор максимального соответствия р такой, что если исходная матрица А имеет полный столбцовый ранг, то А(р.:) – квадратная матрица с ненулевой диагональю. Матрица А(р,:) называется декомпозицией Далмейджа-Мендельсона, или DM-декомпозицией.

Если А – приводимая матрица, [Квадратная матрица А называется приводимой, если она подобна клеточной матрице, квадратные элементы которой соответствуют индукции линейного оператора А в отдельные подпространства. – Примеч. ред.] линейная система Ах=b может быть решена приведением А к верхней блочной треугольной форме с неприводимым диагональным блоком. Решение может быть найдено методом обратной подстановки.

[p.q.r] = dmperm(A) – находит перестановку строк р и перестановку столбцов q квадратной матрицы А, такую что A(p,q) – матрица в блоке верхней треугольной формы.

Третий выходной аргумент г – целочисленный вектор, описывающий границы блоков. К-й блок матрицы A(p,q) имеет индексы r(k):r(k+l)-l.

[p.q.r.s] = dmperm(A) – находит перестановки р и q и векторы индексов г и s, так что матрица A(p,q) оказывается в верхней треугольной форме. Блок имеет индексы (r(i):r(i+l)-l,s(i):s(i+l)-l).

В терминах теории графов диагональные блоки соответствуют сильным компонентам Холла графа смежности матрицы А.

Примеры:

>> A=sparse([1.2.1.3.2].[3.2.1.1.1].[7.6.4.5.4],3.3) 
:full(A) 
ans =
4 0
4 6 0
5 0 0
>> [p.q.r]=dmperm(A) 
P=
1 2 3
q =
3 2 1
r =
1 2 3 4
>> fulKA(p.q)) 
ans =
7 0 4
0 6 4
0 0 5

symmmd(S) – возвращает вектор упорядоченности для симметричной положительно определенной матрицы S, так что S(p,p) будет иметь более разреженное разложение Холецкого, чем S. Иногда symmmd хорошо работает с симметрическими неопределенными матрицами. Такое упорядочение автоматически применяется при выполнении операций \ и /, а также при решении линейных систем с разреженными матрицами [Функция symamd работает значительно быстрее. – Примеч. ред.].

Можно использовать команду spparms, чтобы изменить некоторые опции и параметры, связанные с эвристикой в алгоритме.