Способы хранения разреженных матриц
Основной целью является хранение только ненулевых элементов матрицей и возможность производить над ней простейшие матричные операции.
Пусть Nz — количество ненулевых элементов матрицы A. Рассмотрим наиболее распространенные схемы хранения, более подробная информация приводится в [4].
Самой простой схемой хранения разреженных матриц является так называемый «координатный» формат. Структура исходной матрицы отображается на три одномерных массива: (1) — массив, содержащий значения ненулевых элементов матрицы А в произвольном порядке; (2) целочисленный массив, содержащий их строковые индексы; и (3) целочисленный массив, содержащий их столбцовые индексы. Все три вектора имеют длину Nz.
Пример 1. Матрица
Может быть представлена как:
| AA | 12 | 9 | 7 | 5 | 1 | 2 | 11 | 3 | 6 | 4 | 8 | 10 |
| JR | 5 | 3 | 3 | 2 | 1 | 1 | 4 | 2 | 3 | 2 | 3 | 4 |
| JC | 5 | 5 | 3 | 4 | 1 | 4 | 4 | 1 | 1 | 2 | 4 | 3 |
В приведенном примере элементы перечислены в произвольном порядке, однако обычно они перечисляются по строкам или столбцам. Если элементы перечисляются по строкам, то вектор JC, который содержит избыточную информацию, может быть заменен массивом указателей на начало каждой строки. Это даст заметную экономию при хранении. Новая структура данных будет иметь три массива, которые будут выполнять следующие функции:
— массив АА содержит ненулевые значения aij, сохраняемые построчно, от строки 1 до n. Длина массива АА есть Nz.
— целочисленный массив JA содержит столбцовые индексы элементов aij в матрице А. Длина массива JА есть Nz.
— целочисленный массив содержит указатели входа для каждой строки в массивах АА и JА. Таким образом, значение IA(i) показывается позиция, где начинается i-тая строка в массивах АА и JА. Длина IA есть n+1, где IA(n+1) содержит число IA(1)+ Nz, то есть адрес в А и JА начала фиктивной строки с номером n+1.
Таким образом, представленная выше матрица А может быть сохранена как:
| AA | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| JА | 1 | 4 | 1 | 2 | 4 | 1 | 3 | 4 | 5 | 3 | 4 | 5 |
| IA | 1 | 3 | 6 | 10 | 12 | 13 |
Такой формат является наиболее популярным для хранения разреженных матриц общего вида. Он носит название разреженного строчного формата или Compressed Sparse Row (CSR). Эта схема более предпочтительна, чем координатная, так как часто является более удобной для нескольких важных опе¬раций над разреженными матрицами: сложения, умножения, перестановок строк и столбцов, транспонирования, решения линейных систем с разреженными матрицами коэффициентов как прямыми, так и итерационными методами. С другой стороны, координатная схема более проста, наглядна и гибка, она часто используется в качестве «входного» формата для вычислительных библиотек, предназначенных для работы с разреженными матрицами.
Существует несколько модификаций данной схемы хранения, наиболее очевидной является разреженная столбцовая схема или Compressed Sparse Column (CSC).
Другая распространенная схема учитывает тот факт, что диагональные элементы большинства матриц ненулевые и/или используются чаще других. Модифицированная строчная схема (Modified Sparse Row, MSR) использует только два массива: массив значении АА и целочисленный массив JА. В первых n позициях АА содержит диагональные элементы исходной матрицы по порядку. Элемент АА(n+1) не заполняется (или же несет дополнительную информацию о матрице). Начиная с позиции n+2 записываются ненулевые элементы исходной матрицы по строкам, исключая диагональные. Для каждого элемента АА(k) элемент JA(k) показывает столбцовый индекс в исходной матрице. На n+1 позициях матрицы JA размещаются указатели входа для каждой строки матрицы АА и JA.
Поэтому для матрицы из примера выше эти два массива будут иметь вид:
| AA | 1 | 4 | 7 | 11 | 12 | * | 2 | 3 | 5 | 6 | 8 | 9 | 10 |
| JА | 7 | 8 | 10 | 13 | 14 | 14 | 4 | 1 | 4 | 1 | 4 | 5 | 3 |
Звездочка указывает на неиспользуемый элемент. Заметим, что JA(n)=JA(n+1)=14, показывая, что последняя строка является нулевой, так как диагональный элемент уже описан ранее.
Диагонально структурированные матрицы — это матрицы, чьи ненулевые элементы расположены вдоль небольшого числа диагоналей. Эти диагонали могут храниться в прямоугольном массиве DIAG(1:n, 1:Nd), где Nd — число диагоналей. Смещение каждой диагонали вычисляется относительно главной диагонали, которая должна быть известна. Смещения хранятся в массиве IOFF(1:Nd). Таким образом, элемент ai,i+ioff(j) исходной матрицы будет храниться в позиции (i,j) в массиве DIAG. Порядок, в каком хранятся диагонали, в общем случае, неважен, особенно если большинство операций сосредоточенно около главной диагонали, ее имеет смысл хранить в первом столбце. Также следует отметить, что все диагонали, кроме главной, имеют менее n элементов, так что не все элементы матрицы DIAG будут использоваться.
Пример 2. Трехдиагональная матрица
может быть сохранена в двух массивах согласно вышеприведенной схеме:
DIAG =
| * | 1 | 2 |
| 3 | 4 | 5 |
| 6 | 7 | 8 |
| 9 | 10 | * |
| 11 | 12 | * |
IOFF =
| -1 | 0 | 2 |
Более общей схемой, популярной для векторных машин является так называемый формат. Эта схема предполагает, что количество диагоналей Nd невелико. Для хранения требуются два прямоугольных массива размером n*Nd каждый.
В первом, COEF, подобном DIAG, хранятся ненулевые элементы матрицы А. Ненулевые элементы каждой строки могут сохраняться в строке массива COEF(1:n,1:Nd), дополняя эту строку нулями, если необходимо. Вместе с COEF, целочисленный массив JCOEF(1:n,1:Nd) должен хранить индекс столбца каждого элемента COEF.
Для матрицы А из примера 2, схема хранения Ellpack-Itpack примет вид:
COEF =
| 1 | 2 | 0 |
| 3 | 4 | 5 |
| 6 | 7 | 8 |
| 9 | 10 | 0 |
| 11 | 12 | 0 |
JCOEF =
| 1 | 3 | 1 |
| 1 | 2 | 4 |
| 2 | 3 | 5 |
| 3 | 4 | 4 |
| 4 | 5 | 5 |
Базовые операции для разреженных матриц
Умножение матрицы на вектор — важная операция, которая требуется в большинстве итерационных алгоритмов решения разреженных линейных систем. В этом разделе показано, как она может быть реализована для схем хранения, приведенных ранее.
В следующем примере кода на Fortran 90 представлен главный цикл умножения матрицы на вектор для матриц хранящихся в разреженном столбцовом формате:
Обратите внимание, что каждая итерация цикла вычисляет различные компоненты результирующего вектора. Это выгодно, потому что каждый из этих компонентов может быть вычислен независимо. Очевидно, если матрица хранится по столбцам, то должен быть использован следующий код:
В каждой итерации цикла, произведение j-го столбца добавляется к результату, который, как предполагается, был первоначально равен нулю. Заметим также, что внешний цикл уже не пригоден для параллелизации. В качестве альтернативного распараллеливания можно попытаться разделить векторную операцию во внутреннем цикле. Внутренний цикл имеет всего несколько операций, так что это вряд ли даст значительное улучшение производительности. Это сравнение показывает, что структуры данных, возможно, придется изменить, чтобы улучшить производительность при работе с мощными компьютерами. Рассмотрим теперь усножение матриці на вектор для матриц, хранящихся в диагональном формате.
Здесь каждый из диагоналей умножается на вектор х, и результат добавляется к вектору y. Снова предполагается, что вектор y заполнен нулями в начале цикла. С точки зрения распараллеливания и/или векторизации лучше использовать приведенный выше код, вероятно. С другой стороны, он носит недостаточно общий характер.
Решение нижне- или верхне- треугольной системы является еще одним важным «ядром» в вычислениях разреженных матриц . Следующий фрагмент кода показывает обычный блок решения нижнетреугольной системы Lx = у для формата хранения CSR.
Источник
Хранение разреженной матрицы общего вида.
3 Разреженные матрицы Традиционно считается, что разреженные данные это данные, которые в основном содержат нулевые, или пустые, значения. В некоторых стучаях разреженность данных может быть очевидной. Рассмотрим, например, нанесение на карту всех видимых на небе звезд. Очевидно, что на ночном небе будет гораздо больше пустого пространства, чем звезд, видимых невооруженным глазом (в противном стучае ночное небо было бы очень ярким). Несмотря на то, что количество видимых звезд очень велико, тем не менее, они распределены по огромной площади. Таким образом, количество видимых звезд по сравнению с количеством мест, которые могли бы быть заняты видимыми звездами, может служить примером разреженных данных. Разреженность данных определяется не количеством данных, а отношением занятых позиций данных к количеству всех возможных позиций. Такое отношение определяет разреженность данных. Для обоснования использования разреженной матрицы для данных той или иной степени разреженности необходимо оценить скорость работы и сложность кода, а также объем сэкономленной при этом памяти. Разреженными называются матрицы, в которых ненулевых элементов много меньше общего числа элементов. Хранение разреженной матрицы в памяти должно обеспечивать: 1) экономию памяти N M размерность матрицы NZ количество ненулевых элементов, Z 4 Первый индекс (номер строки) каждого ненулевого элемента записывается в одномерный массив LI. Второй индекс (номер столбца) каждого ненулевого элемента записывается в одномерный массив LJ. Пример, матрица B N a13;a32;a45;a46;a56;a61;a64; A : 2; 5; 9; 1; 3; 8; 4; LJ: 3; 2; 5; 6; 6; 1; 4; LI: 1; 3; 4; 4; 5; 6; 6; Координатный формат может быть: Упорядоченный (по строкам/столбцам) o Быстрый доступ к строкам/столбцам o Необходимость перепаковки при вставке/удалении элементов Неупорядоченный o «Переборный» доступ к элементам o Быстрая вставка/удаление элементов При данном способе упаковки для матрицы n m элементов с NZ ненулевыми элементами затраты памяти составят NZ ячеек под элементы массива NZ ячеек под массив LJ NZ ячеек под массив LI Хотя многие математические библиотеки поддерживают матрично-векторные операции в координатном формате, данный формат обеспечивает медленный доступ к элементам матрицы, и является затратным по используемой памяти. В рассмотренном выше примере избыточность по памяти образом проявляется в массиве LI, в котором строчные координаты хранятся неоптимальным образом. Перейдем далее к рассмотрению более экономных форматов хранения. Разреженный строчный формат это одна из наиболее широко используемых схем хранения разреженных матриц. Эта схема предъявляет минимальные требования к памяти и в то же время оказывается очень удобной для нескольких важных операций над разреженными матрицами: сложения, умножения, перестановок строк и столбцов, транспонирования, 4
5 решения линейных систем с разреженными матрицами коэффициентов как прямыми, так и итерационными методами и т. д. Разреженный строчный формат (Compessed Row Storage CRS или Compessed Sparse Rows CSR) Структура хранения Матрица храниться в виде трех одномерных массивов. Все ненулевые элементы aij построчно, с первой до последней строки, записываются в одномерный массив A. Второй индекс каждого ненулевого элемента (номера столбцов) записывается в одномерный массив LJ. Местоположение первого ненулевого элемента в каждой строке записывается в одномерный массив LI. Элементы i-ой строки хранятся в позициях матрицы A с номера (LI[i]) по (LI[i+1]-1). Если в строке i встречаются только нулевые элементы (строка является пустой), то значение LI[i] = LI[i+1]. Если матрица А состоит из n строк, то длина массива LI будет (n+1). Пример: Рассмотрим матрицу A. N A: a11;a12;a21;a22;a24;a33;a34;a42;a43;a44;a45;a54;a55; LJ: 1; 2; 1; 2; 4; 3; 4; 2; 3; 4; 5; 4; 5; LI: 1; 3; 6; 8; 12; 14; Последний элемент (14) в матрице LI определяет количество ненулевых элементов+1. Это нужно для того что бы не выйти за границы массива A при просмотре последней строки исходной матрицы. Пример с числами, матрица B 5
8 LJ: 1; 1; 4; 4; 6; 7; 10; Алгоритм доступа такой же, как и для CRS, только i и j меняются местами, а также LI и LJ Упаковка структурно симметричных матриц Разреженная матрица называется структурно симметричной, если для неё выполняется следующее: Если a ij 0, то и a ji 0 Если a ij = 0, то и a ji = 0 Такая матрица хранится следующим образом: Все диагональные элементы записываются в массив AD. Ненулевые элементы стоящие над диагональю построчно записываются в одномерный массив AU, при этом их вторые индексы в том же порядке записываются в одномерный массив LJ. Значения элементов стоящих под диагональю по столбцам записываются в одномерный массив AL. Заметим, что их первые индексы уже находятся в LJ. Местоположение первого элемента в каждой строке (каждого столбца) записывается в массив LI. LI[i] указывает на начало i-ой строки в массиве AU Элементы строки i в массиве AU находятся по индексам от LI[i] до LI[i + 1] — 1 включительно — Обрабатываются пустые строки (LI[p] = LI[p + 1]) — Единообразно обрабатывается последняя строка (LI[N]=NZ+1). LI[j] указывает на начало j-ого столбца в массиве AL Элементы столбца j в массиве AL находятся по индексам от LI[j] до LI[j + 1] — 1 включительно — Обрабатываются пустые столбцы (LI[p] = LI[p + 1]) — Единообразно обрабатывается последний столбец (LI[N]=NZ+1). Для рассмотренной ранее матрицы A массивы заполняются следующим образом: 8
9 AD: a11; a22; a33; a44; a55; AU: a12; a24; a34; a45; AL: a21; a42; a43; a54; LJ : LI : Объем памяти для хранения массива N N с 2*NZ ненулевыми элементами (исключая диагональ): — Массив значений AD — N ячеек — Массив значений AU — NZ ячеек — Массив значений AL — NZ ячеек — Массив LJ NZ ячеек — Массив LI — N ячеек Алгоритм доступа: Доступ к диагональному элементу тривиален. Если искомый элемент лежит в верхнем треугольнике, т.е. i 10 6.3. Ленточные матрицы Матрица A называется ленточной, если все ее ненулевые элементы заключены внутри ленты, образованной между диагоналями, параллельными главной. Ленточный формат используется, когда можно выделить плотную ленту, состоящую из ненулевых элементов и имеющую определенную ширину. Существует несколько модификаций этого формата. Если для матрицы А справедливо: aij = 0 при i > j + р и aij = 0 при j > i + q, то р называется нижней шириной ленты, q — верхней шириной ленты. Величина m = р + q + 1 называется шириной ленты матрицы A Ленточный строчный формат Строчный ленточный формат для хранения исходной матрицы A использует массив размера n х m, в котором построчно хранятся ненулевые элементы матрицы А. Побочные диагонали доопределяются нулями до размерности n: в начале диагоналей для нижнего треугольника и в конце диагоналей для верхнего треугольника. Рисунок ниже, иллюстрирует хранение матрицы по столбцам. 10
11 Пример Элемент исходной матрицы aij расположен в упакованном массиве P[ i, j i + p + 1], если aij находятся в пределах упакованного массива, т.е. если i j и (i-j) 12 Ленточный столбцовый формат Общий вид Пример Элемент исходной матрицы aij расположен в упакованном массиве P [ i j + q + 1, j], если aij находятся в пределах упакованного массива, т.е. если i j и ( i j) 13 Ленточный формат матрицы с одинаковыми полуширинами ленты Рассмотрим частным случай ленточной матрицы, у которой β =p=q полуширина ленты. В этом случае aij = 0, если i j > β. Такая матрица может упаковываться в двумерный массив, имеющий столько же строк, сколько исходный и ( 2β + 1) столбцов. Т.е. это частный случай строчного формата. Средний столбец ( β + 1) соответствует главной диагонали. Остальные элементы располагаются на том же удалении от диагонального элемента, что и в неупакованной матрице. Алгоритм доступа к элементу aij. Если i j > β то этот элемент равен нулю. В противном случае берём элемент A [ i, j i + β + 1]. Дома рассмотреть симметричный столбцовый формат хранения ленточной матрицы. 13
14 Диагональный формат хранения (Матрица с плотной диагональю) Диагональныи формат хранения матриц используется, когда все ненулевые элементы матрицы расположены на различных, не плотно расположенных- диагоналях. Хранение таких матриц аналогично хранению ленточных матриц, то есть используется массив размера n m, где n — размерность исходной матрицы, m — количество ненулевых диагоналей. Побочные диагонали доопределяются до общей размерности нулями аналогично ленточному формату. При этом дополнительно хранится массив целых чисел Index размера m, в котором указывается сдвиг каждой диагонали от главной — положительные индексы для верхнего треугольника, отрицательные для нижнего треугольника. Так. для матрицы, показанной на Рис. выше, массив Index будет содержать элементы (-i1; — i2; 0; i3; i4; i5; i6;) Пример хранения матрицы в диагональном строчном формате показан на Рис. Доступ к элементу aij если элемент (j-i) есть в матрице Index и он расположен в k-ой позиции, то берем элемент A[i, k] и 0 в другом случае. 14
15 Задания к лабораторной работе «Разреженные матрицы» Задача 1. Даны две разреженные матрицы общего вида. Перемножить их и результат занести в разреженную матрицу CSR. Задача 2. Даны две разреженные структурно симметричные матрицы. Перемножить их и результат занести в разреженную матрицу CSS. Задача 3. Даны две разреженные ленточные матрицы. Перемножить их и результат занести в разреженную матрицу CSR. Задача 4. Даны две разреженные матрицы общего вида. Сложить их и результат занести в разреженную матрицу CSS. Задача 5. Даны две разреженные структурно симметричные матрицы. Сложить их и результат занести в разреженную матрицу CSR. Задача 6. Даны две разреженные ленточные матрицы. Сложить их и результат занести в разреженную матрицу CSS. Задача 7. Даны две разреженные матрицы общего вида. Из одной матрицы вычесть другую и результат занести в разреженную матрицу CSR. Задача 8. Даны две разреженные структурно симметричные матрицы. Из одной матрицы вычесть другую и результат занести в разреженную матрицу CSS. Задача 9. Даны две разреженные ленточные матрицы. Из одной матрицы вычесть другую и результат занести в разреженную матрицу CSR. Задача 10. Дана разреженная структурно симметричная матрица. Найти её определитель. Задача 11. Дана разреженная ленточная матрица. Найти её определитель. Задача 12. Дана разреженная матрица CSR. Найти её определитель. Задача 13. Дана разреженная матрица общего вида. Найти матрицу, обратную к ней. Задача 14. Дана разреженная ленточная матрица. Найти матрицу, обратную к ней. Задача 15. Дана разреженная структурно симметричная матрица. Найти матрицу, обратную к ней. Задача 16. Дана разреженная матрица CSS. Найти сумму её элементов. Задача 17. Дана разреженная ленточная матрица. Найти сумму её элементов. 15
16 Задача 18. Дана разреженная структурно симметричная матрица. Найти сумму её элементов. Задача 19. Дана разреженная матрица CSR. Найти количество её различных элементов и вывести их на экран. Задача 20. Дана разреженная ленточная матрица. Найти количество её различных элементов и вывести их на экран. Задача 21. Дана разреженная структурно симметричная матрица. Найти количество её различных элементов и вывести их на экран. Задача 22. Дана разреженная матрица общего вида (CSS или CSR) и число b. Матрица просматривается слева на право, и сверху вниз. На места ненулевых элементов матрицы вначале поместить все её ненулевые элементы большие b, а затем ненулевые элементы меньшие b. Элементы не сортировать. Задача 23. Дана разреженная ленточная матрица и число b. Матрица просматривается слева на право, и сверху вниз. На места ненулевых элементов матрицы вначале поместить все её ненулевые элементы большие b, а затем ненулевые элементы меньшие b. Элементы не сортировать. Задача 24. Дана разреженная структурно симметричная матрица и число b. Матрица просматривается слева на право, и сверху вниз. На места ненулевых элементов матрицы вначале поместить все её ненулевые элементы большие b, а затем ненулевые элементы меньшие b. Элементы не сортировать. Задача 25. Дана разреженная матрица общего вида(css или CSR). Найти сумму её элементов aij, у которых сумма (i+j) является чётной. Задача 26. Дана разреженная ленточная матрица. Найти сумму её элементов aij, у которых сумма (i+j) является чётной. Задача 27. Дана разреженная структурно симметричная матрица. Найти сумму её элементов aij, у которых сумма (i+j) является чётной. Задача 28. Дана разреженная матрицы общего вида(css или CSR). Переставить столбцы в матрице по возрастанию сумм элементов в этих столбцах. Задача 29. Дана разреженная матрицы общего вида(css или CSR). Переставить строки в матрице по возрастанию сумм элементов в этих строках. Задача 30. Дана разреженная матрицы общего вида(css или CSR). Отобразить элементы относительно диагонали, проходящей с левого верхнего угла к правому нижнему углу. Задача 31. Дана разреженная структурно симметричная матрица. Зеркальное отображение относительно диагонали, проходящей с левого верхнего угла к правому нижнему углу. 16
17 Задача 32. Дана разреженная матрицы общего вида(css или CSR). Зеркальное отображение относительно диагонали, проходящей с левого нижнего угла к правому верхнему углу. Задача 33. Дана разреженная структурно симметричная матрица. Зеркальное отображение относительно диагонали, проходящей с левого нижнего угла к правому верхнему углу. Задача 34. Дана разреженная матрицы общего вида(css или CSR). Осуществить циклический сдвиг в матрице каждого столбца на n разрядов. Задача 35. Дана разреженная матрицы общего вида(css или CSR). Осуществить циклический сдвиг в матрице каждой строки на n разрядов. Задача 36. Дана разреженная матрицы общего вида(css или CSR). Осуществить циклический сдвиг в матрице. Сдвинуть всю матрицу. С первой строки элементы переносятся на вторую. И т.д. С последней на первую. Задача 37. Дана разреженная матрицы общего вида(css или CSR). Осуществить циклический сдвиг в матрице. Сдвинуть всю матрицу. С первого столбца элементы переносятся на второй. И т.д. С последнего на первый. Задача 38. Дана разреженная матрицы общего вида(css или CSR). Циклически сдвинуть все диагонали a,b,c, и т.д.. a b c d d a b c c d a b b c d a a b c d d a b c Задача 39. Дана разреженная ленточная матрица. Циклически сдвинуть все диагонали a,b,c, и т.д.. a b c d d a b c c d a b b c d a Задача 40. Дана разреженная матрицы общего вида(css или CSR). Повернуть матрицу на 90 градусов. Задача 41. Дана разреженная матрицы общего вида(css или CSR). Повернуть матрицу на 180 градусов. Задача 42. Дана разреженная матрицы общего вида(css или CSR). Повернуть матрицу на 270 градусов. 17
18 Список литературы 1. Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений. Пер. с англ. — М:Мир, 1984, 336 с. 2. О. Эстербрю, З. Златаев. Прямые методы для разреженных матриц. Пер. с англ.- М.: Мир, с 3. Серджио Писсанецки. Технология разреженных матриц. Пер. с англ. М.: Мир, с. 4. Баталов Б. В., Егоров Ю. Б., Русаков С. Г. Основы математического моделирования больших интегральных схем на ЭВМ. — М.: Радио и связь, с. 5. Р. Тьюарсон. Разреженные матрицы. М.: Мир, с. СОДЕРЖАНИЕ Разреженные матрицы. 3 Хранение разреженной матрицы общего вида Координатный формат хранения. 3 Разреженный строчный формат. 5 Разреженный столбцовый формат Упаковка структурно симметричных матриц Использование связных списков Ленточные матрицы Ленточный строчный формат Ленточный столбцовый формат Ленточный формат матрицы с одинаковыми полуширинами ленты Диагональный формат хранения Задания к лабораторной работе «Разреженные матрицы» Список литературы
Источник
