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

                                                  26


                 R1        S1        R2         S2          R3    S3           R4
                 →         ↑         →          ↑         →       ↑            →
                                          Рис.1


                                      S1+S2+S3




                      R1             R2                R3               R4


                                           Рис.2

   Выбирая k разделителей Si (i=1,..,k) небольшого размера (на рис.1 k=3),
образованных линиями узлов сетки, мы получим разбиение сетки на (k+1) блок
R1,R2, ,Rk+1 сравнимого размера. Если собрать все разделители в один блок,
то возникает древовидное разбиение (рис.2). Пронумеруем узлы каждого
множества типа R последовательно, слева направо вдоль горизонтальных
линий, начиная с нижнего левого узла (см. рис.1, по стрелкам). После того, как
пронумерованы все множества типа R, последовательно нумеруются
разделители в порядке, указанном стрелками (см. рис.1). Полученная
нумерация отвечает монотонному упорядочению дерева. Матрица, связанная с
конечно-элементной сеткой, разбивается на блоки, как показано на рис.3, где
заштрихованы области, которые могут содержать ненулевые элементы. При
выполнении гауссова исключения заполнение будет возникать только внутри
заштрихованных областей, а также внутри областей матрицы, помеченных
точками. Кроме того, заштрихованные области заполнены ненулевыми
элементами лишь частично.


                                R1         R2        R3      R4   S1 S2            S3
                      R1
                      R2
                      R3
                      R4
                      S1                                                 :::
                      S2                                          :::              :::
                      S3                                                 :::

                                                     Рис. 3