Вычислительные методы линейной алгебры. Горбаченко В.И - 25 стр.

мое симметричное обратное упорядочение Катхилл-МакКи (Elizabeth
Cuthill-J. McKee). Это упорядочение минимизирует ширину ленты исходной
симметричной матрицы. Функция возвращает вектор упорядоченности p, со-
держащий номера столбцов (и строк) переупорядоченной матрицы.               Рас-
смотрим пример. Зададим матрицу
>> A=[4   1   0   0   1   0
      1   4   1   0   0   0
      0   1   4   0   0   0
      0   0   0   4   0   1
      1   0   0   0   4   1
      0   0   0   1   1   4];
Преобразуем матрицу в разреженный формат, найдем разложение Холецкого
и построим спай-график матрицы R1 (рис. 1.2)
>> AS=sparse(A);
>> R1=chol(AS);
>>spy(R1)




                          Рис. 1.2. Разложение Холецкого без упорядочения


Из рис. 1.2 видно, что матрица содержит 13 элементов и довольно широкую
ленту. Применим упорядочение Катхилл-МакКи
>> p1=symrcm(AS)
p1 =
     3     2     1                5       6       4
Получим разложение Холецкого для упорядоченной матрицы. Для этого в
качестве индексов матрицы укажем вектор перестановок p1
>> R2=chol(AS(p1,p1));
    Спай-график spy(R2) матрицы R2 (рис. 1.3) показывает, что матрица
содержит 11 ненулевых элементов, а полуширина равна 2. В данном простом
примере эффект от сокращения числа ненулевых элементов не столь показа-



                                                                              25