Методы решения систем с разреженными матрицами. Теория графов. Глушакова Т.Н - 16 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

16
9.2. Алгоритм оценки объёма заполнения в
методе минимальной степени
Этот алгоритм даёт оценку объёма оперативной памяти.
Заметим, что объём заполнения в матрице U, которая получится после
гауссова исключения, равен полусумме степеней всех вершин графа
заполнения G
F
. Таким образом, всё сводится к определению суммы всех
степеней вершин G
F
, причём сам граф G
F
определять необязательно
−
достаточно воспользоваться теоремой Джорджа-Лю.
Алгоритм
1) Полагаем k=1. В качестве 1-ой вершины возьмём вершину минимальной
степени (лучше ППВ). Полагаем deg U= deg v
1
.
2) Полагаем k=2. Выбираем в графе исключения G
K
вершину минимальной
степени и нумеруем её как k-ую.
3) Перебираем вершины из множества Reach(v
k
,Q
k
) (Q
k
= {V
1,
..., V
k-1
}) и для
каждой вершины u
∈
Reach(v
k
,Q
k
)
а) определяем множество Reach(u,Q
k+1
),
б) полагаем deg U = deg U +
Reach(u,Q
k+1
)
, где
...
означает
количество элементов соответствующего множества.
4) Полагаем k=k+1 и переходим к 3).
Таким образом, сумма степеней всех вершин deg U накапливается в
процессе реализации алгоритма, причём все множества достижимости
рассматриваются только для исходной матрицы A.
Заметим, что объём заполнения равен числу рёбер графа заполнения G
F
.
43798105621
10987654321
***
******
***
*****
**
****
**
***
***
***
410
39
78
97
86
105
54
63
22
11
Новые номе р а строк
Стар ые номера строк
1
1 10 3 8
7 4 2 9
6 5
5 9 6
4
8
10 2 7
3
Граф G с перену м ерованным и
вершинами
                                     16

        1 2 3 4 5 6 7 8 9 10         Новые номера строк
         1   2 6 5 10 8 9 7 3 4      Старые номера строк
1     1 *     *    *          
                              
2     2     *          *   *                    1           5           9            6

3     6 *     *        *                    1           10          3            8
                                   3                                                             4
 4    5              *   *    
                                          6                                                    5
 5   10*          *   *   * 
 6    8         *          *                9           2           4            7
                                                    7           2           10           8
 7    9     * *    *   *   * 
 8    7         *          * *              Граф G с перенумерованными
                                            вершинами
 9    3            * * * * * *
10    4    *            * * 

                9.2. Алгоритм оценки объёма заполнения в
                       методе минимальной степени

   Этот алгоритм даёт оценку объёма оперативной памяти.
   Заметим, что объём заполнения в матрице U, которая получится после
гауссова исключения, равен полусумме степеней всех вершин графа
заполнения GF. Таким образом, всё сводится к определению суммы всех
степеней вершин GF, причём сам граф GF определять необязательно −
достаточно воспользоваться теоремой Джорджа-Лю.

                                 Алгоритм
1) Полагаем k=1. В качестве 1-ой вершины возьмём вершину минимальной
   степени (лучше ППВ). Полагаем deg U= deg v1.
2) Полагаем k=2. Выбираем в графе исключения GK вершину минимальной
   степени и нумеруем её как k-ую.
3) Перебираем вершины из множества Reach(vk,Qk) (Qk = {V1,..., Vk-1}) и для
   каждой вершины u∈Reach(vk,Qk)
   а) определяем множество Reach(u,Qk+1),
   б) полагаем      deg U = deg U + Reach(u,Qk+1),   где ... означает
      количество элементов соответствующего множества.
4) Полагаем k=k+1 и переходим к 3).

  Таким образом, сумма степеней всех вершин deg U накапливается в
процессе реализации алгоритма, причём все множества достижимости
рассматриваются только для исходной матрицы A.
   Заметим, что объём заполнения равен числу рёбер графа заполнения GF.

Страницы