Зберігання розріджених матриць загального вигляду

ЛАБОРАТОРНА РОБОТА № 1

Тема: Зберігання розріджених матриць загального вигляду

Короткі теоретичні відомості

Традиційно вважається, що розріджені дані – це дані, які в основному мають нульові (або, як варіант, пусті) значення. Більш строго розрідженість даних визначається не кількістю даних, а відношенням занятих позицій в матриці (чи іншій структурі даних) до кількості всіх можливих позицій. Для обгрунтування використання розрідженої матриці для даних тої чи іншої степені розрідженості необхідно оцінити швидкість --- і складність коду, а також об`єм з пам`яті, яка при цьому економиться.

Зберігання розрідженої матриці повинно забезпечувати:

• економію пам`яті;
• швидкий доступ до нульових і ненульових елементів за їх індексом.

Існує добре визначений набір задач, для розв`язку яких рекомендується використовувати структури даних типу розріджених матриць, зокрема, до таких відносять наступні задачі:

• чисельний розв’язок задач систематичної фізики;
• для представлення графів (у вигляді розріджених матриць сумістності).

Найпростішим способом зберігання довільної розрідженої матриці є координатний формат: зберігаються ненульові елементи матриці та їх координати (номера рядків та стовпців).

Структура зберігання:

• матриця зберігається у вигляді трьох одновимірних масивів;
• всі ненульові елементи aij послідовно записуються в одновимірний масив А;
• перший індекс (номер рядка) кожного ненульового елементу записується у одновимірний масив LI;
• другий індекс (номер стовпця) кожного ненульового елементу записується в одновимірний масив LJ;

При такому способі упаковки для матриці n x m елементів з NZ ненульовими елементами необхідно (3*NZ) комірок пам`яті.

Практично багато математичних бібліотек на даний час використовують такий спосіб представлення розріджених матриць, але він вважається не найкращим як з точки зору об`єму даних, так і з точки зору швидкості доступу до них.

Приклад координатного формату зберігання матриць (Рис. 1.1).

Формат, який використовується  найчастіше, і який рекомендовано використовувати для зберігання розріджених даних матриці – це розріджений рядковий формат (Compessed Row Storage – CRS або Compessed Sparse Rows – CSR).

Рисунок 1.1 – Приклад для координатного представлення розріджених матриць.

Структура зберігання:

• матриця зберігається у вигляді трьох динамічних масивів;
• всі ненульові елементи aij порядково, з першого до останього рядка, записуються в двимірний масив А;
• другий індекс кожного ненульового елемента (номер стопців) записується в одновимірний масив LJ;
• місце першого ненульового елемемнта в кожному рядку записується в одновимірний масив LI. Елементи  і-го рядка у позицях матриці А з номеру (LI[i]) по (LI[i+1]-1). Якщо в рядку і лише нульові елементи (пустий рядок), то значення LI[i]=LI[i+1]. Якщо матриця А складається з n рядків, то довжина масива LI буде (n+1);
• останій елемент (14 та 10) в масиві LI – це кількість ненульових елементів +1.

Приклад представлений на рисунках 1.2 і 1.3.

Рисунок 1.2 – Приклад 1 – Розріджений рядковий формат.

Рисунок 1.3 – Приклад 2 – Розріджений рядковий формат.