Розріджена матриця

Розріджена матриця — матриця, більша частина елементів якої є нулі. Матрицю, в якої більшість елементів не дорівнюють нулю називають щільною.

Розріджена матриця
Підтримується Вікіпроєктом	Вікіпедія:Проєкт:Математика
Протилежне	щільна матриця[d]
Розріджена матриця у Вікісховищі

Немає єдиного визначення, яка кількість ненульових елементів має бути в матриці, щоб вона була розрідженою. Для матриці порядку n елементів кількість ненульових елементів:^[1]

• є O(n). Таке визначення підходить хіба для теоретичного аналізу асимптотичних властивостей матричних алгоритмів.
• в кожному рядку не перевищує 10 в типовому випадку.
• обмежено ${\displaystyle n^{1+\gamma }}$, де ${\displaystyle \gamma <1}$.

Застосування

Величезні розріджені матриці часто виникають, наприклад, при чисельному розв’язуванні диференціальних рівнянь у частинних похідних.

Представлення у структурах даних

Зберігати цілу матрицю у пам'яті комп'ютера є неефективно по відношенню до пам'яті, тому є альтернативні способи збереження таких матриць.

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

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

Зберігання ненульових елементів зв'язаних вказівниками

У цьому способі збереження кожен ненульовий елемент зберігається у вигляді значення, номера рядка та стовпця і вказівника на наступний елемент в рядку і стовпці. Для цього методу збереження потрібно також зберігати рамку, яка складається з таких самих елементів, до якої ми будемо прив'язувати всі елементи вказівниками. Цей спосіб потребує більше пам'яті, але при цьому збільшується швидкість виконання дій над матрицями.

Бібліотеки програм

• SparseLib++ (C++)^[2]
• uBLAS (C++, в скад Boost)^[3]
• SPARSPAK (Fortran)^[4]
• CSparse (C)^[5]