Методы работы с разреженными матрицами произвольного вида. Глушакова Т.Н - 8 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

8
Таблица 1: Объем памяти и число операций для факторизации.
Суммирование производится от i =1 до i = n – 1 включительно .
Матрица А Число
умножений и
делений
Число сложений Объем памяти
Заполненная
несимметричная
nn
3
1
3
1
3
− nnn
6
1
2
1
3
1
23
+−
2
n
Ленточная
несимметричная ,
диагональный
выбор главного
элемента
β
ββ
β
β
3
1
3
2
)
1
(
23
−
−−−
−
+
n
ββ
ββ
6
1
2
1
3
2
2
32
+−
−− n
(
)
βββ −−+
2
12 n
Ленточная
несимметричная ,
частичный выбор
главного элемента
(
)
ββ
β
β
β
3
1
2
3
6
13
12
2
3
−−
−−
−
+
≤
n
ββ
ββ
6
1
6
13
2
2
32
+−
−−≤ n
(
)
ββ
β
2
3
2
5
13
2
−−
−
+
≤
n
Разреженная
несимметричная
(
)
∑
+
L
j
U
i
cr 1
∑
L
j
U
i
cr
(
)
∑
++
L
j
U
i
crn
Таблица 2: Число операций для прямой и обратной подстановки .
Суммирование проводится от i = 1 до i = n – 1 включительно .
Матрица А Число умножений Число
сложений
Заполненная симметричная или
несимметричная
n
2
n
2
– n
Ленточная симметричная или
несимметричная с диагональным
выбором главного элемента
(
)
βββ −−+
2
12 n βββ −−
2
2 n
Ленточная несимметричная ,
частичный выбор главного элемента
()
βββ
2
3
2
5
13
2
−−+≤ n
βββ
2
3
2
5
3
2
−− n
Разреженная несимметричная
(
)
∑
++
L
j
U
i
crn
(
)
∑
+
L
j
U
i
cr
Где
U
i
r = число внедиагональных ненулевых элементов в i - й строке матрицы
U ,
L
j
c
= число внедиагональных ненулевых элементов в j - м столбце
матрицы L,
n = порядок матрицы .
β = обе полуширины ленты (ширина ленты равна 2β + 1).
Для плотных матриц все элементы рассматриваются как ненулевые, даже
если их значение может быть равным нулю. Все элементы , расположенные 
                                     8
Таблица 1: Объем памяти и число операций          для   факторизации.
Суммирование производится от i =1 до i = n – 1 включительно.
   Матрица А           Число             Число сложений     Объем памяти
                    умножений и
                      делений
Заполненная             1 3 1             1 3 1 2 1                n2
                          n − n             n − n + n
несимметричная          3      3          3      2     6
Ленточная            ( β +1) βn −                  2
                                            β 2n − β 3 −    (2β +1)n −β 2 −β
несимметричная,         2                          3
диагональный         − β 3 −β 2 −
                        3                     1 2 1
выбор главного                              − β + β
                        1                     2      6
элемента             − β
                        3
Ленточная            ≤(2 β +1)βn −                 13         ≤(3β +1)n −
                                         ≤2 β 2 n − β 3 −
несимметричная,        13                           6          5      3
частичный выбор      − β3 −                                   − β2 − β
                        6                        1             2      2
главного элемента                        −β 2 + β
                        3      1                 6
                     − β2 − β
                        2      3
Разреженная             (     )
                      ∑ ri +1 c Lj
                           U
                                             ∑ riU c Lj            (
                                                             n +∑ riU +c Lj   )
несимметричная

Таблица 2: Число операций для прямой и обратной подстановки.
Суммирование проводится от i = 1 до i = n – 1 включительно.
           Матрица А                     Число умножений          Число
                                                                сложений
Заполненная симметричная или                n2                    n2 – n
несимметричная
Ленточная симметричная или          (2 β +1)n −β 2 −β          2 βn −β 2 −β
несимметричная с диагональным
выбором главного элемента
Ленточная несимметричная,                      5      3            5       3
                                  ≤(3β +1)n − β 2 − β         3βn − β 2 − β
частичный выбор главного элемента              2      2            2       2
Разреженная несимметричная            n +∑ (ri +c j )
                                              U    L
                                                                   (
                                                                ∑ ri +c j
                                                                    U    L
                                                                              )
Где riU = число внедиагональных ненулевых элементов в i-й строке матрицы
U,
    c Lj = число внедиагональных ненулевых элементов в j-м столбце
матрицы L,
    n = порядок матрицы.
    β = обе полуширины ленты (ширина ленты равна 2β + 1).
   Для плотных матриц все элементы рассматриваются как ненулевые, даже
если их значение может быть равным нулю. Все элементы, расположенные

Страницы