Разреженные матрицы
Способы хранения разреженных матриц
Для хранения разреженных матриц целесообразно хранить только ненулевые элементы, чтобы обеспечить экономию памяти и числа операций, необходимых для преобразования матрицы в процессе решения линейных систем, а также простоту доступа к любому элементу матрицы при формировании системы.
Координатный формат
Используется 3 массива: AA, JR, JC. В первом массиве хранятся значения ненулевых элементов. В двух последних хранятся их координаты внутри матрицы (индексы строк и столбцов соответственно). Данный способ хранения является полным, поскольку представлена вся матрица, и неупорядоченным, поскольку элементы матрицы могут храниться в произвольном порядке. Данный формат обеспечивает медленный доступ к элементам матрицы, и является затратным по используемой памяти. Для хранения данных используется 3a чисел (a – кол-во ненулевых элементов).
Сжатый разреженный строчный формат
Если в координатном формате элементы были бы упорядочены построчно, то массив JC содержал бы излишнюю информацию. В таком случае он может быть заменен на массив, который указывает на начало каждой строки, что обеспечит экономию памяти. Новая структура данных содержит 3 массива, выполняющих следующие функции: AA содержит ненулевые значения матрицы, записанные построчно с 1 до n строки JA содержит индексы столбцов всех элементов, представленных в матрице IA содержит указатели на начало каждой строки в массивах AA и JA. Таким образом, содержимое IA(i) – позиция в массивах AA и JA, где начинается i-я строка. Длина IA равна n+1, IA(n+1) равен количеству ненулевых элементов + 1.
Данная схема хранения предпочтительнее координатного формата, поскольку часто оказывается удобнее для выполнения типовых вычислений.
Существуют вариации сжатого разреженного строчного формата. Наиболее очевидный вариант – хранение столбцов вместо строк. Данная схема известна как Сжатый разреженный столбцовый формат.
Модифицированный разреженный строчный формат
Другой вариант основывается на факте, что диагональные элементы большинства матриц обычно ненулевые и/или что они требуются чаще, чем остальные элементы. Как результат, они могут храниться отдельно. Таким образом, используется два массива: AA, в котором первые n позиций содержат диагональные элементы матрицы по порядку. Неиспользованная позиция n+1 может иногда содержать информацию о матрице. Начиная с позиции n+2, идут ненулевые элементы матрицы, исключая диагональные элементы, упорядоченные построчно. JA. JA(k) представляет значение индекса столбца для каждого элемента AA(k). n+1 первых позиций JA содержат указатель на начало каждой строки в AA и JA. Начиная с n+2, JA указывает на индексы столбцов элементов с соответствующими индексами в AA.
Диагонально структурированный формат
Диагонально структурированные матрицы – это матрицы, ненулевые элементы которой расположены вдоль небольшого числа диагоналей. Эти диагонали могут храниться в двумерном массиве DIAG(n, Nd), где Nd – количество диагоналей. Смещения для каждой из диагональной относительно главной диагонали должны быть известны, они хранятся в массиве IOFF(Nd). Таким образом, элемент a_(i,i+ioff(j)) изначальной матрицы расположен в позиции (i, j) массива DIAG. Все диагонали, кроме главной, будут иметь меньшее, чем n, число элементов, поэтому в DIAG будут неиспользуемые позиции.
Ellpack-Itpack формат
Для такого формата предполагается, что в диагоналях матрицы большинство элементов в каждой строке ненулевые. В данном случае используется два массива. Первый массив COEF похож на массив DIAG из диагонально структурированного формата и содержит ненулевые элементы матрицы A. Ненулевые элементы каждой строки матрицы могут храниться в массиве COEF(n, Nd), заполняя некоторые строки нулями, если необходимо. Целочисленный массив JCOEF(n, Nd) должен быть заполнен и содержать индексы столбцов для каждого элемента в COEF.
Определенное число столбцов должно быть выбрано для каждого нулевого элемента, который должен быть добавлен, чтобы дополнить сокращенные строки в матрице A (в примере: 1, 4, 5 строки).
Случай с симметричными матрицами
Когда обрабатываемая матрица симметрична, то есть A=A^T, достаточно хранить лишь ее верхнюю треугольную подматрицу. При этом для хранения можно использовать любую из рассмотренных схем. Если симметричная матрица является положительно определенной, то все ее диагональные элементы отличны от нуля, и могут храниться в отдельном массиве, а некоторым разреженным форматом представления будет представления только верхний треугольник матрицы.
Варианты представления матриц
Блочное представление'
Блочная матрица – матрица, которая разбивается на сектора, называемые блоками. Визуально это можно отобразить, проведя множество горизонтальных и вертикальных линий в изначальной матрице, которые будут ее разбивать на отдельные блоки матриц меньшего размера. Матрица: Может быть разделена на 4 блока с матрицами 2×2: Операции с блочными матрицами производятся по тем же правилам, как если бы на месте блоков были числовые элементы. Для выполнимости операций необходимо соответствующее согласование размеров блоков. Например, при умножении блочных матриц требуется, чтобы горизонтальные размеры блоков первого сомножителя совпадали с соответствующими вертикальными размерами второго сомножителя.
Ленточное представление
Ленточная матрица – разреженная матрица, все ненулевые элементы которой находятся внутри диагональной ленты, расположенной вдоль главной диагонали матрицы. Для хранения ленточных матриц обычно сохраняются диагонали внутри ленты, оставшиеся элементы неглавной диагонали заполняются нулями.
Профильное представление
Профилем матрицы называют сумму всех локальных ширин относительно главной диагонали. Совокупность позиций от локальной ширины до главной диагонали называется оболочкой. Формально это описывается следующим образом: f_i (A)=min{ j ┤| a_ij≠0 } β_i (A)=i-f_i (A) Число f_i (A) – столбцовый индекс первого ненулевого элемента i-й строки, β_i (A) – ширина ленты в i-й строке. Тогда профиль матрицы: e(A)=∑_(i=1)^n▒〖β_i (A) 〗
Базовые операции с разреженными матрицами
Умножение матрицы на вектор
Данная операция является важной и требуется во многих итерационных методах для решения разреженных линейных систем. В результате получается вектор. Умножение происходит циклично путем умножения каждой строки матрицы на столбец вектора.
При использовании сжатого разреженного строчного формата для хранения матрицы каждая итерация цикла вычисляет отдельный компонент результирующего вектора и это является плюсом, поскольку данные компоненты могут вычисляться независимо друг от друга.
При использовании сжатого разреженного столбцового формата в каждой итерации цикла произведение j-го столбца матрицы на вектор прибавляется к соответствующему компоненту результирующего вектора. В данном случае итерации не могут выполняться независимо, поскольку внутри нескольких итераций могут использоваться значения одной и той же составляющей результирующего вектора.
Для использования параллельного вычисления при данном формате возможно независимое вычисление компонентов результирующего вектора во внутреннем цикле.
Умножение матрицы на матрицу
Для умножения матрицы на матрицу P=AB необходимо, чтобы число столбцов матрицы A было равно числу строк матрицы B. Тогда результатом операции умножения будет матрица P. Пусть A имеет размерность (M×N), B-(N×R). Тогда размерность матрицы P, которая является результатом умножения AB, будет (M×R). Элементы матрицы P вычисляются следующим образом: P_ij=∑_(k=1)^N▒〖A_ik B_kj 〗,i=1,2,…,M,j=1,2,…,R. Компоненты матриц A и B не изменяются и только считываются, поэтому вычисления элементов P могут выполняться независимо друг от друга, что позволяет использовать параллельное вычисление для ускорения работы. Решение треугольной системы Решение верхней или нижней треугольной системы является важным аспектом при работе с разреженными матрицами. Происходят итерации, на каждой из которых вычисляется значение компонента вектора. Вычисление происходит путем вычитания из соответствующего вектора правых частей вычисленных ранее компонентов вектора неизвестных, умноженных на соответствующие коэффициенты из разреженной матрицы, после чего происходит деление результата на коэффициент при вычисляемом компоненте вектора неизвестных.
