Линейная алгебра
Разреженная линейная алгебра: когда матрица почти пуста
Матрица смежности Twitter с 350 миллионами пользователей в плотном виде - 980 петабайт. В разреженном CSR-формате - несколько терабайт: у каждого пользователя не больше нескольких тысяч связей. Весь PageRank, вся спектральная кластеризация, все GNN работают с разреженными матрицами.
- PageRank Google: матрица 50B страниц в CSR-формате, степенная итерация за 50-100 шагов
- GNN: матрица смежности графа молекулы в PyTorch Geometric хранится как edge_index (COO)
- TF-IDF Википедия: 6.7M статей x 10M слов, ~0.005% заполнение - CSR экономит 99.99% памяти
- FEM-симуляции: матрица жёсткости трёхмерного тела - трёхдиагональная, разреженность >99%
- Sparse Attention: Longformer/BigBird - маска attention как разреженная матрица
**Матрица смежности графа социальной сети из 500 миллионов пользователей - это 500M × 500M.** Плотное хранение потребует 2 × 10¹⁷ байт - в двести тысяч раз больше всех жёстких дисков на Земле. Но в этой матрице ненулевых элементов - доли процента: у каждого пользователя от силы несколько тысяч связей. Разреженная матрица хранит только эти связи. Весь PageRank Google, все рекомендации по графу знакомств, вся sparse attention в Longformer - это разреженная линейная алгебра.
**О чём этот урок на самом деле**: не про экономию памяти как самоцель. Про то, что структура нуля - это информация. Граф связей, матрица документ-терминов TF-IDF, веса нейросети после pruning - все они разрежены не случайно, а потому что большинство пар объектов просто не связаны. Умение работать с этой структурой отделяет прод-решение от учебного.
Зачем вообще хранить нули
Плотная матрица 10 000 × 10 000 занимает 800 МБ. Если в ней всего 50 000 ненулевых элементов (0.05%) - это расточительство в 1600 раз. Три главных формата для хранения только ненулей:
**Когда какой формат**: COO - при построении (просто добавлять записи). CSR - при умножении A·x (итерация по строкам). CSC - при умножении xᵀ·A. scipy умеет конвертировать: `A.tocsr()`, `A.tocsc()`, `A.tocoo()`.
ML-применение №1: граф нейронной сети (GNN)
В **Graph Neural Network** центральный объект - матрица смежности A графа молекулы, социальной сети, дорожной карты. Операция message passing - это буквально A·H, где H - матрица эмбеддингов узлов. Если хранить A плотно для молекулы из 10 000 атомов - 800 МБ на одну молекулу. В sparse формате - несколько MB.
**PyTorch Geometric** и **DGL** хранят граф именно в sparse формате (edge_index - это по сути COO). Все слои GCN, GAT, GraphSAGE внутри выполняют sparse матрично-матричное произведение. Без sparse алгебры GNN на реальных датасетах (OGB: миллионы узлов) не запустить.
ML-применение №2: TF-IDF матрица
Матрица **документ-терминов** (document-term matrix) в NLP - классический пример разреженности. Словарь из 100 000 слов, корпус из 1 000 000 документов. Каждый документ содержит от силы 500 уникальных слов - заполнение 0.0005%. scikit-learn строит её именно как CSR.
ML-применение №3: sparse attention (Longformer, BigBird)
Стандартный Transformer: attention матрица Q·Kᵀ имеет размер n×n (n - длина последовательности). При n=4096 это 16M элементов на один слой. **Longformer** и **BigBird** заменяют плотную attention на sparse: каждый токен смотрит только на локальное окно + несколько глобальных токенов. Маска - разреженная матрица.
Итерационные решатели для разреженных систем
**Метод конечных элементов (FEM)** - основа симуляции в ANSYS, COMSOL, OpenFOAM - порождает системы Ax=b, где A разреженная и часто симметричная положительно определённая (SPD). Прямые методы (LU) создают **fill-in**: нули в A становятся ненулями в L и U. Итерационные методы используют только умножение A·v - и разреженность сохраняется.
**Почему предобусловитель помогает**: CG сходится за O(√κ) итераций, где κ = λ_max/λ_min - число обусловленности. Для дискретного Лапласиана κ = O(n²). Хороший ILU приближает A⁻¹, и кондиционное число M⁻¹A резко падает. При M = A получили бы 1 итерацию - идеал, недостижимый на практике без огромного fill-in.
torch.sparse: разреженность в нейросетях (pruning)
**Neural network pruning** - удаление малых весов для сжатия модели. После pruning матрица весов линейного слоя становится разреженной. torch.sparse позволяет хранить и умножать её без материализации нулей. При 90% разреженности - потенциально 10x экономия памяти и 5-10x ускорение инференса на специализированном оборудовании.
**В реальном pruning пайплайне**: сначала обучают dense модель, затем применяют structured или unstructured pruning, дообучают (fine-tuning) для восстановления качества, затем квантизуют. Результат - sparse quantized модель. Llama.cpp использует похожую идею для запуска больших моделей на CPU.
Fill-in и перестановка: почему порядок строк важен
При LU-разложении разреженной матрицы нули в A становятся ненулями в L и U - это **fill-in**. Правильная перестановка строк и столбцов минимизирует fill-in. Алгоритм AMD (Approximate Minimum Degree) делает это автоматически.
**Для 3D FEM задач без хорошей перестановки**: fill-in делает L и U почти плотными, уничтожая все преимущества разреженности. Поэтому в промышленных пакетах (PARDISO, MUMPS, SuperLU) перестановка - критически важная часть алгоритма, иногда занимающая столько же времени, сколько само разложение.
Практика: разреженный PageRank
Зачем не хранить нули: форматы CSR, CSC, COO
Матрица называется разреженной, если доля ненулевых элементов мала - обычно $O(n)$ ненулей при размере $n \times n$. Плотное хранение всей матрицы требует $O(n^2)$ памяти и $O(n^3)$ для умножения. Разреженное хранение сокращает это до $O(\text{nnz})$, где $\text{nnz}$ - число ненулевых элементов.
**Три основных формата:** - **COO** (Coordinate): массивы `row`, `col`, `data` - прост для сборки - **CSR** (Compressed Sparse Row): эффективен для умножения $Ax$; хранит `data`, `indices` (col), `indptr` (начало строк) - **CSC** (Compressed Sparse Column): эффективен для $A^\top x$ и операций по столбцам
PageRank на разреженной матрице
Реальный масштаб
Веб-граф Google: $n \approx 50$ млрд страниц, средний out-degree ~10. Матрица переходов $M$: $50B \times 50B$, но только $5 \times 10^{11}$ ненулей. CSR-хранение: ~4 TB вместо $20 \times 10^{21}$ TB для плотной. Степенная итерация $r_{t+1} = M r_t$ работает через sparse matrix-vector multiply.
Формат CSR хранит три массива: `data`, `indices`, `indptr`. Что хранится в `indptr`?
`indptr[i]` - позиция первого ненулевого элемента $i$-й строки в массивах `data` и `indices`. Элементы строки $i$: `data[indptr[i]:indptr[i+1]]`. Это и есть "сжатие" строк в CSR.
Sparse Matrix-Vector Multiply и итерационные решатели
Ключевая операция разреженной линейной алгебры - умножение матрицы на вектор: $y = Ax$. Для CSR-матрицы с $\text{nnz}$ ненулями это требует $O(\text{nnz})$ операций вместо $O(n^2)$. Именно эта операция лежит в основе итерационных методов решения $Ax = b$.
**Итерационные методы** (не требуют явного обращения матрицы - только SpMV): - **CG** (Conjugate Gradient): для симметричных положительно определённых матриц; сходится за $O(\sqrt{\kappa})$ итераций, где $\kappa$ - число обусловленности - **GMRES**: для общих несимметричных матриц - **ARPACK/LOBPCG**: для поиска нескольких собственных векторов разреженной матрицы
TF-IDF и разреженные документ-терминные матрицы
sklearn в одну строку
Матрица $D \in \mathbb{R}^{n_{\text{docs}} \times n_{\text{terms}}}$ для Википедии: 6.7M статей, 10M уникальных слов. Плотная: $6.7 \times 10^{13}$ float64 = 536 TB. Разреженная: средняя статья - 500 слов, $\text{nnz} \approx 3.35 \times 10^9$, ~27 GB в CSR. TF-IDF SVD через ARPACK: топ-100 тем за минуты.
Метод CG (Conjugate Gradient) применим только к определённому классу матриц. К какому?
CG требует $A = A^\top$ и $x^\top A x > 0$ для всех $x \neq 0$. Это гарантирует, что все собственные значения положительны и алгоритм сходится. Для несимметричных систем используют GMRES.
| Формат | Структура | Лучшее применение |
|---|---|---|
| COO (Coordinate) | Три массива: row[], col[], data[] | Построение матрицы - просто append |
| CSR (Compressed Sparse Row) | data[], indices[] (столбцы), indptr[] (границы строк) | Матрично-векторное произведение A·x |
| CSC (Compressed Sparse Column) | data[], indices[] (строки), indptr[] (границы столбцов) | Произведение xᵀ·A и доступ к столбцам |
Матрица A: [ 5 0 0 1 ] [ 0 8 2 0 ] [ 0 0 3 0 ] CSR - три массива: data = [5, 1, 8, 2, 3] - ненулевые значения, строка за строкой indices = [0, 3, 1, 2, 2] - их столбцы indptr = [0, 2, 4, 5] - indptr[i] = начало строки i в data[] Строка 0: data[0:2] = [5, 1] в столбцах [0, 3] Строка 1: data[2:4] = [8, 2] в столбцах [1, 2] Строка 2: data[4:5] = [3] в столбце [2] Память: 3 массива по nnz + (n+1) вместо n² элементов
Dense attention (стандартный Transformer): Memory: O(n²) при n=4096 -> 64M float = 256 MB на слой Compute: O(n²·d) Sparse attention (Longformer, окно w=512): Memory: O(n·w) при n=4096, w=512 -> 2M float = 8 MB Compute: O(n·w·d) При n=16384 (длинные документы): Dense: 1 GB на слой -> не влезает в GPU Sparse: 32 MB -> работает torch.sparse поддерживает sparse матрично-матричное произведение на CUDA: torch.sparse.mm(sparse_mask, dense_scores)
| Метод | Матрица A | Сходимость | Применение |
|---|---|---|---|
| CG (Conjugate Gradient) | Симметричная PD | O(√κ) итераций | FEM, физические симуляции |
| GMRES | Произвольная | O(κ) итераций (без рестарта) | CFD, несимметричные системы |
| BiCGSTAB | Несимметричная | Меньше памяти чем GMRES | Задачи переноса (convection) |
- **FEM-симуляции (ANSYS, COMSOL, OpenFOAM)**: Дискретный Лапласиан, матрицы жёсткости
- **Graph Neural Networks (PyG, DGL)**: Матрица смежности как sparse тензор
- **Sparse Attention (Longformer, BigBird)**: Локальное окно + глобальные токены вместо плотного attention
- **NLP / Search (TF-IDF, BM25)**: Document-term матрица, scipy.sparse.csr_matrix
- **Network pruning (LLM compression)**: Sparse веса после pruning нейросетей
Упражнения
- Почему для матрично-векторного произведения A·x предпочтителен CSR, а не COO? — CSR хранит элементы строки последовательно в памяти - эффективный доступ при вычислении скалярного произведения строки с x; COO требует дополнительной сортировки или накопления результатов в случайных позициях; Для A·x нужно итерироваться по строкам - именно это CSR делает оптимально; CSC лучше для xᵀ·A, где нужен доступ к столбцам
- Почему sparse attention в Longformer позволяет обрабатывать документы в 8x длиннее, чем стандартный Transformer? — Стандартный attention: O(n²) память. При 8x длине = 64x больше памяти - не помещается в GPU; Sparse attention с окном w: O(n·w) память. При фиксированном w память растёт линейно с n; Качество сохраняется за счёт глобальных токенов (CLS) + локального окна; Longformer достигает n=16384 на одном GPU, где стандартный Transformer останавливается на ~512-2048
- Когда выбрать прямой sparse решатель (splu), а когда итерационный (cg)? — Прямой решатель: одна дорогая факторизация, потом быстрые решения для многих правых частей b - хорошо при n < 100k; Итерационный: дешёвле по памяти, масштабируется до миллионов уравнений, но требует хорошего предобусловителя; Если матрица плохо обусловлена (κ >> 1) без предобусловителя, CG сходится медленно; Для 3D FEM прямые методы обычно проигрывают из-за fill-in; для 1D/2D - часто выигрывают
Что унести из урока
- **COO → CSR → CSC**: строить в COO, умножать A·x в CSR, xᵀ·A в CSC - каждый формат для своей операции
- **GNN message passing** = A·H, где A - sparse матрица смежности; без sparse алгебры реальные графы не влезают
- **TF-IDF** в scikit-learn - автоматически CSR; заполнение < 0.1%, но операции полностью поддерживают sparse
- **Sparse attention** (Longformer) заменяет O(n²) на O(n·w) - линейная память, те же задачи
- **Fill-in** при LU: перестановка AMD снижает его с O(n²) до O(n·log n) для FEM-матриц
- **Предобусловитель ILU** уменьшает кондиционное число M⁻¹A и даёт 5-20x ускорение CG
- **torch.sparse** для pruning: 90% нулей = 10x меньше памяти при инференсе - основа LLM-компрессии
Связи
Разреженность - не изолированная тема, а инструмент поверх всех остальных
- Матричные уравнения — Уравнение Ляпунова для больших систем управления решается итерационно через sparse методы
- LU-разложение — Основа прямых sparse решателей; fill-in - ключевое отличие от плотного случая
- Собственные векторы — PageRank - степенной метод для sparse матрицы переходов; spectral clustering на sparse графах