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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

6
сложения , умножения , перестановок строк и столбцов, транспонирования ,
решения систем с разреженными матрицами коэффициентов как прямыми,
так и итерационными методами и т.д. Значения ненулевых элементов
матрицы и соответствующие столбцовые индексы хранятся в этой схеме по
строкам в двух массивах AN и JA. Используется также массив указателей IA,
отмечающих позиции массивов AN и JA, с которых начинается описание
очередной строки. Дополнительная компонента в IA содержит указатель
первой свободной позиции в JA и AN.
Описание r-й строки А хранится в позициях с IA(r) до IA(r + 1) – 1
массивов JA и AN, за исключением равенства IA(r + 1)=IA(r), означающего,
что r - я строка пуста. Если матрица А имеет m строк, то IA содержит m + 1
позиций ; IA(1) всегда равно единице.
Данный способ представления называют полным, поскольку представлена
вся матрица А . В зависимости от того, как записываются в каждой строке
столбцовые индексы в массиве JA (по порядку возрастания или нет ),
различают упорядоченное или неупорядоченное представление
соответственно. Неупорядоченные представления нужны для
алгоритмических удобств: результаты большинства матричных операций
получаются неупорядоченными, и упорядочение их требует дополнительных
затрат машинного времени, в то время как большинство алгоритмов для
разреженных матриц не требует , чтобы представления были
упорядоченными.
1.3 Разреженный столбцовый формат
Элементы матрицы А хранятся по столбцам . Столбцовые
представления могут рассматриваться и как строчные представления
транспонированных матриц . Таким образом, в массиве ANT хранятся
ненулевые элементы матрицы A , в массиве JAT указывается строчный
индекс соответствующего элемента, а элементы IAT указывают, с какой
позиции начинается описание очередного столбца матрицы А .
1.4 Сжатие по Шерману
Схема Шермана используется для хранения разреженных треугольных
матриц , вычисляемых в методе Гаусса. Нижней треугольной матрицей
называется матрица, у которой ненулевые элементы могут стоять только в
нижнем треугольнике и на главной диагонали (a
ij
=0 при j>i). Верхняя
треугольная матрица – матрица с ненулевыми элементами только в верхнем
треугольнике и на главной диагонали (a
ij
=0 при j<i). Наиболее важным их
приложением является треугольная факторизация матрицы А : А=LDU, где L
– нижняя треугольная , U – верхняя треугольная , D – диагональная матрицы .
L, D и U получаются из А посредством некоторого исключения , например
гауссова исключения . Часто случается , что некоторые множества строк в U
или L имеют сходную структуру. В частности, нередко будет так , что строки
U с номерами i и j, i < j, имеют идентичную структуру справа от позиции j. 
                                    6
сложения, умножения, перестановок строк и столбцов, транспонирования,
решения систем с разреженными матрицами коэффициентов как прямыми,
так и итерационными методами и т.д. Значения ненулевых элементов
матрицы и соответствующие столбцовые индексы хранятся в этой схеме по
строкам в двух массивах AN и JA. Используется также массив указателей IA,
отмечающих позиции массивов AN и JA, с которых начинается описание
очередной строки. Дополнительная компонента в IA содержит указатель
первой свободной позиции в JA и AN.
   Описание r-й строки А хранится в позициях с IA(r) до IA(r + 1) – 1
массивов JA и AN, за исключением равенства IA(r + 1)=IA(r), означающего,
что r-я строка пуста. Если матрица А имеет m строк, то IA содержит m + 1
позиций; IA(1) всегда равно единице.
   Данный способ представления называют полным, поскольку представлена
вся матрица А. В зависимости от того, как записываются в каждой строке
столбцовые индексы в массиве JA (по порядку возрастания или нет),
различают      упорядоченное     или     неупорядоченное     представление
соответственно.     Неупорядоченные        представления     нужны     для
алгоритмических удобств: результаты большинства матричных операций
получаются неупорядоченными, и упорядочение их требует дополнительных
затрат машинного времени, в то время как большинство алгоритмов для
разреженных      матриц    не   требует,    чтобы    представления   были
упорядоченными.

      1.3 Разреженный столбцовый формат
     Элементы матрицы А хранятся по столбцам. Столбцовые
представления могут рассматриваться и как строчные представления
транспонированных матриц. Таким образом, в массиве ANT хранятся
ненулевые элементы матрицы A, в массиве JAT указывается строчный
индекс соответствующего элемента, а элементы IAT указывают, с какой
позиции начинается описание очередного столбца матрицы А.

      1.4 Сжатие по Шерману
      Схема Шермана используется для хранения разреженных треугольных
матриц, вычисляемых в методе Гаусса. Нижней треугольной матрицей
называется матрица, у которой ненулевые элементы могут стоять только в
нижнем треугольнике и на главной диагонали (aij=0 при j>i). Верхняя
треугольная матрица – матрица с ненулевыми элементами только в верхнем
треугольнике и на главной диагонали (aij=0 при j

Страницы