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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

27
Таким образом,
суть МПС
состоит в следующем.
1. В графе G, соответствующем матрице А, выбираем в качестве разделителей
вершины, отвечающие узлам сетки, лежащим на одном горизонтальном или
вертикальном уровне.
2. Обозначим выбранные разделители через S
1
, S
2
,…,S
k
, тогда граф разбивается
на (k+1) компоненту связности R
1
, R
2
,…,R
k+1.
3. Вершины графа, принадлежащие множеству разделителей, нумеруем от n до
(n–s+1) (где n – число вершин графа, s – совокупное число вершин
разделителей), а вершины, принадлежащие R
1
, R
2
,…,R
k+1
, – от 1 до (n – s).
Осталось определить количество разделителей k.
Для минимизации заполнения и объёма вычислительных работ в случае
регулярной сетки m
×
n (m
<
n ) (т.е. прямоугольной структуры)
целесообразно брать
=
==
=
m
n
k
3
2
.
При этом разделители S
1
,..., S
k
следует брать так, чтобы получающиеся
множества R
i
(i = 1,...,k+1) содержали приблизительно одинаковое число
элементов.
Если в качестве разделителей выбраны линии сетки, члены разбиения
содержат примерно равное количество узлов и используется неявная схема
хранения, то общий объём памяти
2
3
22
km
k
mn
V +
++
+≈
≈≈
≈
.
Достоинства этого метода:
1) уменьшение заполнения;
2) возможность эффективного распараллеливания вычислений (т.к. ЭВМ
последних моделей имеют несколько параллельно работающих
процессоров).
12.2. Общий алгоритм МПС
12.2.1. Упрощенный алгоритм (1-ый вариант)
1) В графе G матрицы A ищется ППВ u.
2) Строим СУС L
0
, L
1
,..., L
n
с корнем в вершине u.
3) Определяем m = [q / n], где q – порядок матрицы, n – длина построенной на
2) СУС.
4) Определяем
=
==
=
m
n
k
3
2
.
5) В качестве разделителей выбираем множества L
1
, L
1+p
,..., L
1+kp
, где
p = [(n – 2) / k] (1 + kp
≈
n – 1). 
                                     27

     Таким образом, суть МПС состоит в следующем.
1. В графе G, соответствующем матрице А, выбираем в качестве разделителей
   вершины, отвечающие узлам сетки, лежащим на одном горизонтальном или
   вертикальном уровне.
2. Обозначим выбранные разделители через S1, S2, ,Sk, тогда граф разбивается
   на (k+1) компоненту связности R1, R2, ,Rk+1.
3. Вершины графа, принадлежащие множеству разделителей, нумеруем от n до
   (n–s+1) (где n – число вершин графа, s – совокупное число вершин
   разделителей), а вершины, принадлежащие R1, R2, ,Rk+1 , – от 1 до (n – s).

    Осталось определить количество разделителей k.
    Для минимизации заполнения и объёма вычислительных работ в случае
регулярной сетки m × n (m

Страницы