Иллюстрированный самоучитель по Matlab



              

Алгоритмы упорядочения - часть 2


Если А — приводимая матрица, [

Квадратная матрица А называется приводимой, если она подобна клеточной матрице, квадратные элементы которой соответствуют индукции линейного оператора А в отдельные подпространства. — Примеч. ред.

]  линейная система Ах=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)

Р=

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, чтобы изменить некоторые опции и параметры, связанные с эвристикой в алгоритме.

Алгоритм упорядочения для симметрических матриц основан на алгоритме упорядочения по разреженности столбцов. Фактически symmmd(S) только формирует матрицу К с такой структурой ненулевых элементов, что К' *К имеет тот же трафик разреженности, что и S, и затем вызывает алгоритм упорядочения по разреженности столбцов для К. На рис. 12.2 приводится пример применения функции symmmd к элементам разреженной матрицы.




Содержание  Назад  Вперед