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

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

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

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

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

Застосування ред.

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

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

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

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

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

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

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

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

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

Примітки ред.

↑ Писсанецки, 1988, Введение
↑ SparseLib++
↑ uBLAS / Boost
↑ Alan George, Esmond Ng A brief description of SPARSPAK Waterloo sparse linear equations package (англ.) // ACM SIGNUM Newsletter, Volume 19 Issue 4, October 1984. — N.Y, 1984. — С. 17-20. — ISBN 978-1-4503-0245-6. — DOI:10.1145/1057931.1057933
↑ T. A. Davis, Direct Methods for Sparse Linear Systems, SIAM, Philadelphia, September 2006

Література ред.

Reginald P. Tewarson Sparse Matrices. — Academic Press, 1973. — 160 с. — ISBN 0126856508 перевод: Тьюарсон Р. Разреженные матрицы = Sparse Matrices. — М.: Мир, 1977. — 191 с.
Писсанецки С. Технология разреженных матриц = Sparse Matrix Technology. — М.: Мир, 1988. — 410 с. — ISBN 5-03-000960-4
Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений = Computer Solution of Large Sparse Positive Definite Systems. — М.: Мир, 1984. — 333 с.

Це незавершена стаття з математики.
Ви можете допомогти проєкту, виправивши або дописавши її.

[1] Писсанецки, 1988, Введение

[2] SparseLib++

[3] uBLAS / Boost

[4] Alan George, Esmond Ng A brief description of SPARSPAK Waterloo sparse linear equations package (англ.) // ACM SIGNUM Newsletter, Volume 19 Issue 4, October 1984. — N.Y, 1984. — С. 17-20. — ISBN 978-1-4503-0245-6. — DOI:10.1145/1057931.1057933

[5] T. A. Davis, Direct Methods for Sparse Linear Systems, SIAM, Philadelphia, September 2006

[1]

[2]

[3]

[4]

[5]