Способы хранения и представления разреженных матриц, операции над ними. Блатов И.А - 27 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

- 27 -
4. Просматриваем
i
-й АС и для каждого элемента
j
этого списка
определяем список только тех столбцовых индексов ненулевых элементов
j
-й строки, номер которых больше
i
.
5. Сливаем все полученные списки, определенные на 4, и список
i
-й строки
матрицы с помощью ПП. Результатом слияния будет портрет
i
-й строки
матрицы
U
.
6. Приписываем список, полученный на 5, к первой свободной позиции
массива
JU
.
7. Определяя число элементов списка, полученной на 5, вычисляем очередную
компоненту массива
IU
, которая будет указывать начало
)
1
(
+
i
-й строки
( значением этой компоненты будет номер первой свободной позиции
массива
JU
после присоединения к нему списка, полученного на 5).
8.
1
+
=
i
i
и обрабатываем следующую строку, перейдя на 3, и так до тех пор,
пока
n
i
≤
.
Результатом будет портрет матрицы
U
.
4.1.2. Численный этап
4.1.2.1. Составление АС
i
-го столбца. Отличия от символического
этапа
1. На символическом этапе каждая строка приписывалась только к одному
столбцу. Здесь же каждая строка должна быть приписана ко всем тем
столбцам , с которыми она имеет ненулевое пересечение , то есть если в
j
-ом
столбце
i
-й строки (
j
i
<
) содержится ненулевой элемент , то она должна
быть приписана к
j
-ому столбцу, так как важны численные значения
элементов.
2. Нам потребуется упорядоченное представление матриц
A
и
U
, поэтому
перед реализацией численного этапа нужно перейти от неупорядоченного
представления к упорядоченному двукратным транспонированием.
4.1.2.2. Алгоритм численного этапа
1.
1
=
i
. Определяем в
и
JA
содержимое первой строки матрицы
A
,
делим эту строку на диагональный элемент
11
a (который хранится в
первой позиции массива
AD
) и помещаем первую строку в
соответствующие позиции массива
UN
. )1()1(
~
ADD = .
2.
1
+
=
i
i
.
3. Просматриваем
)
1
(
−
i
-ю строку матрицы
U
(массив
JU
). Если
)
1
(
−
i
-
я строка пуста, то переходим к 5. Если нет, то определяем столбцовый
индекс
j
первого ненулевого элемента этой строки правее главной
диагонали. Приписываем
)
1
(
−
i
-ю строку к АС
j
-го столбца . 
                                   - 27 -

4. Просматриваем i -й АС и для каждого элемента j этого списка
   определяем список только тех столбцовых индексов ненулевых элементов
    j -й строки, номер которых больше i .
5. Сливаем все полученные списки, определенные на 4, и список i -й строки
   матрицы с помощью ПП. Результатом слияния будет портрет i -й строки
   матрицы U .
6. Приписываем список, полученный на 5, к первой свободной позиции
   массива JU .
7. Определяя число элементов списка, полученной на 5, вычисляем очередную
   компоненту массива IU , которая будет указывать начало (i +1) -й строки
   (значением этой компоненты будет номер первой свободной позиции
   массива JU после присоединения к нему списка, полученного на 5).
8. i =i +1 и обрабатываем следующую строку, перейдя на 3, и так до тех пор,
   пока i ≤n .
  Результатом будет портрет матрицы U .

   4.1.2. Численный этап
     4.1.2.1. Составление АС i -го столбца. Отличия от символического
              этапа
1. На символическом этапе каждая строка приписывалась только к одному
   столбцу. Здесь же каждая строка должна быть приписана ко всем тем
   столбцам, с которыми она имеет ненулевое пересечение, то есть если в j -ом
   столбце i -й строки ( i < j ) содержится ненулевой элемент, то она должна
   быть приписана к j -ому столбцу, так как важны численные значения
   элементов.
2. Нам потребуется упорядоченное представление матриц A и U , поэтому
   перед реализацией численного этапа нужно перейти от неупорядоченного
   представления к упорядоченному двукратным транспонированием.
   4.1.2.2. Алгоритм численного этапа
1. i =1 . Определяем в AN и JA содержимое первой строки матрицы A ,
   делим эту строку на диагональный элемент a11 (который хранится в
   первой позиции массива AD ) и помещаем первую строку в
                                         ~
   соответствующие позиции массива UN . D (1) = AD (1) .
2. i =i +1.
3. Просматриваем (i −1) -ю строку матрицы U (массив JU ). Если (i −1) -
   я строка пуста, то переходим к 5. Если нет, то определяем столбцовый
   индекс j первого ненулевого элемента этой строки правее главной
   диагонали. Приписываем (i −1) -ю строку к АС j -го столбца.

Страницы