Формат хранения разреженных матриц

Формат хранения разреженных матриц

Формат для хранения разреженных матриц – CompressedSparseRow (CSR) – одна из наиболее широко используемых схем для хранения разреженных матриц. Он был предложен в 1969 году. Эта схема предъявляет минимальные требования к памяти и в то же время оказывается очень удобной для нескольких важных операций над разреженными матрицами: сложения, умножения, перестановок строк и столбцов, транспонирования, решения линейных систем с разреженными матрицами коэффициентов как прямыми, так и итерационными методами и т.д. [14]

Разреженная матрица хранится с использованием следующих массивов:

aelem, который содержит все ненулевые элементы матрицы, перечисленные в строчном порядке;

jptr, который содержит столько же элементов, сколькоaelemи для каждого из них указывает, в каком столбце находится данный элемент;

iptr, который хранит число элементов, равное увеличенной на единицу размерности СЛАУ. Егоi-й элемент указывает, с какой позиции в массивахaelemиjptrначинаетсяi-я строка матрицы. Соответственноiptr[i+1] – iptr[i]равно числу ненулевых элементов вi-й строке. Последний элементiptr[n+1]равен числу элементов вaelem, увеличенному на единицу.

Данный способ представления разреженной матрицы называют полным, поскольку представлена вся матрица, иупорядоченным, поскольку элементы каждой строки хранятся в соответствии с возрастанием столбцовых индексов [14]. Массивыiptrиjptrпредставляют портрет матрицы, задаваемый как множество списков смежности ассоциированного с матрицей графа.

В 1972 году был предложен еще один вариант строчной схемы хранения, приспособленный для приложений, где приходится выполнять операции над строками и столбцами. Матрицу хранят по строкам, как описано выше; кроме того, определяют портрет транспонированной матрицы и также хранят по строкам. Строчное представление портрета транспонированной матрицы равносильно столбцовому представлению портрета матрицы. Его можно получить транспонированием строчного портрета исходной матрицы [14].

Для несимметричных матриц была предложена и другая, гораздо более простая строчная схема. Ненулевые элементы хранят в двумерном массиве с размерами , гдеn– порядок матрицы,m– максимальное число ненулевых элементов в строке. Эта схема допускает простую обработку; недостаток ее в том, чтоmможет быть неизвестно заранее, а может оказаться слишком большим.

Для хранения матрицы коэффициентов при решении СЛАУ с помощью разрабатываемой модификации перезапускаемого метода обобщенных минимальных невязок был выбран CSRформат. Выигрыш по используемой оперативной памяти в процессе решения системы изNуравнений от использованияCSRформата в сравнении с хранением всех коэффициентов матрицы с долейdненулевых элементов в двумерном массиве может быть посчитан по формуле

, (3.1)

где – объем, который занимает в памяти ЭВМ вещественная переменная,– объем, который занимает в памяти ЭВМ целочисленная переменная.

3.4. Разделение данных

Способность параллельного алгоритма эффективно использовать процессоры является важной характеристикой выполняемых расчетов. Параллельный алгоритм называют масштабируемым, если при росте числа процессоров он обеспечивает увеличение ускорения при сохранении постоянного уровня эффективности использования процессоров [11]. Результатом применения параллельных вычислений стало не только уменьшение времени выполнения расчетов, но и обеспечение возможности решения более сложных вариантов задач или их постановок, решение которых не представляется возможным при использовании однопроцессорных вычислительных систем.

Читайте также:  Как подтвердить страницу вконтакте галочкой

Хранение вектора правой части системы, вектора начального приближения и вспомогательных векторов на всех процессорах целиком не является критичным: затраты памяти на хранение матрицы размерности nсущественно больше, чем затраты на вектор изnэлементов, особенно, если речь идет о больших размерностях. Главная трудность в распределении данных при решении больших СЛАУ – распределить матрицу коэффициентов таким образом, чтобы затратить при этом минимальное количество памяти. Поэтому для хранения матрицы коэффициентов был использован форматCSR, описанный в разделе 3.3, а также использован подход ленточного распределения матрицы по процессорам «на лету», что исключает возможность расположения матрицы целиком в памяти одного процессора даже во время чтения. Матрица представляется непрерывными наборами строк, как показано на рис. 3.2.

Рис. 3.2. Организация распределения данных при выполнении модификации алгоритма GMRES

Каждый исполнитель располагает информацией о части матрицы коэффициентов, а также хранит вектор начального приближения и вектор правой части. Для объединения результатов расчета после выполнения итерации и получения на исполнителях фрагментов уточненного решения (см. рис. 3.2), выполняется операция передачи, после которой вектор начального приближения будет заменен очередным приближением к решению.

В модели передачи сообщений существует два типа обменных взаимодействий: массовые обменные взаимодействия и точечные обмены. В разделе 3.5 представлено исследование двух этих типов. На примере классической задачи матричного умножения.

Основной целью является хранение только ненулевых элементов матрицей и возможность производить над ней простейшие матричные операции.

Пусть 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
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
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 2

Более общей схемой, популярной для векторных машин является так называемый формат. Эта схема предполагает, что количество диагоналей Nd невелико. Для хранения требуются два прямоугольных массива размером n*Nd каждый.

В первом, COEF, подобном DIAG, хранятся ненулевые элементы матрицы А. Ненулевые элементы каждой строки могут сохраняться в строке массива COEF(1:n,1:Nd), дополняя эту строку нулями, если необходимо. Вместе с COEF, целочисленный массив JCOEF(1:n,1:Nd) должен хранить индекс столбца каждого элемента COEF.

Читайте также:  Как настроить масштаб в виндовс 10

Для матрицы А из примера 2, схема хранения Ellpack-Itpack примет вид:
COEF =

1 2
3 4 5
6 7 8
9 10
11 12

JCOEF =

1 3 1
1 2 4
2 3 5
3 4 4
4 5 5

Базовые операции для разреженных матриц

Умножение матрицы на вектор — важная операция, которая требуется в большинстве итерационных алгоритмов решения разреженных линейных систем. В этом разделе показано, как она может быть реализована для схем хранения, приведенных ранее.

В следующем примере кода на Fortran 90 представлен главный цикл умножения матрицы на вектор для матриц хранящихся в разреженном столбцовом формате:

Обратите внимание, что каждая итерация цикла вычисляет различные компоненты результирующего вектора. Это выгодно, потому что каждый из этих компонентов может быть вычислен независимо. Очевидно, если матрица хранится по столбцам, то должен быть использован следующий код:

В каждой итерации цикла, произведение j-го столбца добавляется к результату, который, как предполагается, был первоначально равен нулю. Заметим также, что внешний цикл уже не пригоден для параллелизации. В качестве альтернативного распараллеливания можно попытаться разделить векторную операцию во внутреннем цикле. Внутренний цикл имеет всего несколько операций, так что это вряд ли даст значительное улучшение производительности. Это сравнение показывает, что структуры данных, возможно, придется изменить, чтобы улучшить производительность при работе с мощными компьютерами. Рассмотрим теперь усножение матриці на вектор для матриц, хранящихся в диагональном формате.

Здесь каждый из диагоналей умножается на вектор х, и результат добавляется к вектору y. Снова предполагается, что вектор y заполнен нулями в начале цикла. С точки зрения распараллеливания и/или векторизации лучше использовать приведенный выше код, вероятно. С другой стороны, он носит недостаточно общий характер.

Решение нижне- или верхне- треугольной системы является еще одним важным "ядром" в вычислениях разреженных матриц . Следующий фрагмент кода показывает обычный блок решения нижнетреугольной системы Lx = у для формата хранения CSR.

Вверх Назад Вперёд Пред. След. Указатель Помощь Экран

2.9. Форматы хранения разреженных матриц

2.9.1. Координатный формат

2.9.2. Форматы CSR и CSC

Часть III. Теоретические материалы Глава 2. Методы решения СЛАУ

2.9. Форматы хранения разреженных матриц

Меню 2.9.1. Координатный формат Вверх Назад Вперёд Пред. След. Указатель Помощь Экран

2.9.1. Координатный формат

Определение. Разреженными называют матрицы, содержащие большой процент нулевых элементов.

Разреженные матрицы очень часто возникают в приложениях, в частности, при численном моделировании различных физических процессов. Количество ненулевых элементов матрицы в дальнейшем будем обозначать .

Понятно, что нерационально хранить в памяти ЭВМ все нулевые элементы разреженных матриц. Они, во-первых, зря занимают память, и, во-вторых, замедляют операции с матрицами. Поэтому существует ряд общепринятых способов хранения разреженных матриц.

Самый простой — так называемый координатный формат . В этом формате для хранения вещественной матрицы используется три массива:

∙ AA — массив вещественных чисел для хранения ненулевых элементов .

∙ IA — массив целых чисел для хранения номеров строк соответствующих элементов массива AA.

∙ JA — аналогичный массив для номеров столбцов.

Длина всех трёх массивов равна .

Пример 2.1. Записать в координатном формате матрицу

Ссылка на основную публикацию
Фильм про девушку запертую в квартире
От нехватки ли бюджета, по сюжетному ли велению или просто из желания выпендриться, режиссеры время от времени помещают киноперсонажей в...
Установка строго с биоса
БИОС – основа, на которой работает вся система компьютера. Именно с его помощью осуществляется выполнение ввода или вывода информации, а...
Установка тахометра на дизель
И так…тахометр для дизеля …мечта многих владельцев старых тарахтелок в большинстве которых тахометра просто не было с завода…В старых дизельных...
Фильмы для ipod classic
Хорошо, когда есть возможность удобно устроиться перед широким экраном огромного телевизора, а что делать, когда находишься в дороге и доступа...
Adblock detector