И другие программы этой серии
Алгоритмы упорядочения
Упорядочение – это еще одна характерная для разреженных матриц операция. Ее алгоритм реализуется несколькими функциями:
• p = colmmd(S) возвращает вектор упорядоченности столбцов разреженной матрицы S1 . Для несимметрической матрицы S вектор упорядоченности столбцов p такой, что S(:,p) будет иметь более разреженные 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],[1,3,2,3,2],[4,3,5,6,7],4,5);full(S) ans =
05000
47000
00300
00600 >> t=colperm(S) t =
45123 >> full(S(:,t)) ans =
00050
00470
00003
00006
p = dmperm(A) возвращает вектор максимального соответствия p, такой что если исходная матрица À имеет полный столбцовый ранг, то A(p,:) – квадратная матрица с ненулевой диагональю. Матрица A(p,:) называется декомпозицией Далмейджа-Мендельсона, или DM-декомпозицией. Если A – приводимая матрица1, линейная система Ax=b может быть решена приведением À к верхней блочной треугольной форме с неприводимым диагональным блоком. Решение может быть найдено методом обратной подстановки;
[p,q,r] = dmperm(A) находит перестановку строк p и перестановку столбцов q квадратной матрицы A, такую что A(p,q) – матрица в блоке верхней треугольной формы.
Третий выходной аргумент r – целочисленный вектор, описывающий границы блоков.
Начало в части 1