sparse matrix

Angol

Főnév

sparse matrix (tsz. sparse matrixes)

1. (informatika) ritka mátrix

---

A sparse matrix vagy magyarul ritka mátrix olyan mátrix, amelyben az elemek többsége nulla. Ezek az adatszerkezetek különösen fontosak a nagy méretű matematikai modellezés, tudományos számítások, gépitanulás, és gráfalgoritmusok esetén. A ritka mátrixok hatékony kezelése memória- és számítási időmegtakarítást tesz lehetővé.

---

Mit jelent az, hogy ritka mátrix?

Egy mátrix akkor számít ritkának, ha elemeinek jelentős része zéró, jellemzően több mint 90%-uk nulla. Például egy 1000x1000-es mátrixban 1 millió elem van. Ha ebből csak 10 000 nem nulla, az arány 1%, vagyis ez egy tipikus ritka mátrix.

Ezzel szemben a sűrű mátrix (dense matrix) olyan, ahol az elemek többsége nem nulla.

---

Példa egy ritka mátrixra:

A = [
 [0, 0, 0, 0, 5],
 [0, 0, 0, 0, 0],
 [0, 0, 3, 0, 0],
 [0, 0, 0, 0, 0],
 [7, 0, 0, 0, 0]
]

Ebben az 5x5-ös mátrixban 25 elem van, de csak 3 nem nulla – ez 12% kitöltöttség.

---

Ritka mátrixok tárolása

Egy hagyományos mátrixot 2D tömbként tárolunk, minden elemet memóriában tartva – függetlenül attól, hogy nulla-e. Ritka mátrixoknál ez pazarló, ezért speciális adattárolási módokat alkalmazunk.

1. Coordinate list (COO)

Minden nemnulla elemet koordinátapárral (sor, oszlop) és értékkel együtt tárolunk.

Példa:

Sor  Oszlop  Érték
 0     4      5
 2     2      3
 4     0      7

2. Compressed Sparse Row (CSR)

A mátrixot három tömb segítségével tároljuk:

• values[]: nem nulla értékek
• col_index[]: a hozzájuk tartozó oszlopindexek
• row_ptr[]: a sorok kezdőindexei a values tömbben

3. Compressed Sparse Column (CSC)

Hasonló a CSR-hez, de oszlopokra optimalizált.

4. Dictionary of Keys (DOK)

Egy szótárban kulcsként (i,j) párokat tárolunk, értékként pedig a megfelelő számokat.

---

Előnyök

• Memóriahatékonyság: Nem tárolunk nullákat.
• Gyorsabb műveletek: Csak a nem nulla elemekkel dolgozunk.
• Skálázhatóság: Nagy mátrixok is kezelhetők kevés memóriával.

---

Műveletek ritka mátrixokkal

Ritka mátrixokra a szokásos mátrixműveletek végrehajthatók, de optimalizált algoritmusokat használnak.

1. Összeadás / kivonás

Csak a nem nulla elemeket kell egyeztetni és módosítani.

2. Szorzás

• Skalárral: egyszerűen minden nemnulla elemet megszorozunk.
• Mátrix-mátrix szorzás: speciális algoritmusok (pl. sparse matrix multiplication) szükségesek.
• Vektorral: nagyon gyorsan megoldható, pl. CSR + vektor = soronkénti összeadás.

3. Transzponálás

Adatszerkezettől függően egyszerű lehet, pl. COO-t csak az indexeket kell felcserélni.

---

Használati területek

1. Tudományos számítások

• Részleges differenciálegyenletek megoldása
• Finite element method (FEM)
• Lineáris egyenletrendszerek

2. Gépitanulás

• Szövegbányászat, TF-IDF mátrixok
• One-hot vektorok tárolása
• Ajánlórendszerek (pl. Netflix, Spotify)

3. Gráfok feldolgozása

• Szomszédsági mátrix ritka gráfok esetén
• Hálózatelemzés (pl. weboldalak, közösségi hálók)

4. Természetes nyelvfeldolgozás (NLP)

• Nagy szókészlettel dolgozó modellek
• Bigrams/trigrams modellek tárolása

---

Szoftveres támogatás

Számos könyvtár támogatja a ritka mátrixokat:

Python

• SciPy: scipy.sparse modul – támogatja CSR, CSC, COO, DOK stb.
• NumPy: alapból nem ritkák, de jól integrálódik SciPy-vel.
• scikit-learn: gépitanulási modellekhez optimalizált ritka mátrix kezelés.

MATLAB

• Beépített sparse() függvény – automatikusan optimalizál

R

• Matrix csomag dgCMatrix típus

C++ / Fortran

• Eigen, Armadillo, PETSc, Trilinos – tudományos alkalmazásokhoz

---

Példa: Sparse mátrix szorzása vektorral (Python, CSR)

import numpy as np
from scipy.sparse import csr_matrix

# 3x3 mátrix:
data = [10, 20, 30]
rows = [0, 1, 2]
cols = [0, 1, 2]

A = csr_matrix((data, (rows, cols)), shape=(3,3))
v = np.array([1, 2, 3])

result = A.dot(v)
print(result)  # [10, 40, 90]

---

Sűrűsödés – mikor nem éri meg?

Ha egy mátrixban a nemnulla elemek aránya 30–50% feletti, a ritka mátrix formátum több memóriát is foglalhat, mivel extra indexeket kell tárolni. Ilyenkor a sűrű tárolás hatékonyabb.

---

Összefoglalás

A ritka mátrix az egyik legfontosabb adatstruktúra a modern számítástechnikában, amikor nagy, de nagyrészt üres (nullákkal teli) adatstruktúrákkal dolgozunk. A speciális tárolási formák és algoritmusok lehetővé teszik a hatékony műveletvégzést, jelentős memória- és időmegtakarítással. Ez különösen kritikus az olyan területeken, mint a gépi tanulás, grafikus számítások, vagy fizikai szimulációk.

További információk

• sparse matrix - Szótár.net (en-hu)
• sparse matrix - Sztaki (en-hu)
• sparse matrix - Merriam–Webster
• sparse matrix - Cambridge
• sparse matrix - WordNet
• sparse matrix - Яндекс (en-ru)
• sparse matrix - Google (en-hu)
• sparse matrix - Wikidata
• sparse matrix - Wikipédia (angol)