Разреженные матрицы

Матрица переходов PageRank Google - 10⁹ × 10⁹. Плотное хранение потребует 8 × 10¹⁸ байт - больше всей памяти всех серверов мира. CSR-формат с 10 ненулями на строку занимает ~100 ГБ и позволяет вычислять PageRank за несколько минут.

• **Рекомендательные системы:** матрица оценок пользователь-товар разрежена (99.9%+ нулей); ALS в implicit-feedback CF использует scipy.sparse
• **Graph Neural Networks:** матрица смежности графа - разреженная; torch.sparse.mm и DGL используют CSR/CSC для эффективной передачи сообщений
• **PageRank:** sparse power iteration на матрице переходов 10⁹ × 10⁹; SpMV - единственная реалистичная операция

Предварительные знания

• Iterative Methods for Linear Systems

Форматы хранения

Разреженная матрица - матрица, в которой большинство элементов равны нулю. Хранение нулей - расточительство. Форматы CSR, CSC, COO хранят только ненулевые элементы, а разреженная арифметика работает только с ними.

**Основные форматы:** **COO (Coordinate):** хранит три массива: (row, col, data). Прост для сборки. **CSR (Compressed Sparse Row):** индексированный по строкам. - data: ненулевые элементы - indices: номера столбцов - indptr: indptr[i]..indptr[i+1] - диапазон элементов строки i Оптимален для A·x (умножение на вектор). **CSC (Compressed Sparse Column):** аналогично, но по столбцам. Оптимален для Aᵀ·x и решателей.

SpMV и заполнение при LU

Умножение разреженной матрицы на вектор (SpMV) - центральная операция итерационных методов. Для CSR-матрицы с nnz ненулями это O(nnz) вместо O(n²). Но LU-разложение разреженной матрицы может создавать **заполнение** (fill-in): нулевые элементы становятся ненулевыми.

**SpMV сложность:** - Плотная матрица: O(n²) умножений - CSR с nnz ненулями: O(nnz) умножений - Для типичного лапласиана: nnz = 5n (2D сетка) → O(n) вместо O(n²) **Заполнение при LU:** При LU-разложении разреженной матрицы нулевые элементы могут стать ненулевыми. Порядок переупорядочивания (AMD, nested dissection) минимизирует заполнение. - Плохой порядок: O(n²) заполнения - AMD (Approximate Minimum Degree): O(n^{1.5}) для 2D задач

При LU-разложении разреженной матрицы без переупорядочивания заполнение может полностью уничтожить разреженность. Всегда используйте `scipy.sparse.linalg.spsolve` (с AMD переупорядочиванием) вместо `numpy.linalg.solve` для разреженных матриц.

Граф-лапласианы и PageRank

Граф-лапласиан - разреженная матрица L = D − A, где D - диагональная матрица степеней вершин, A - матрица смежности. Для графа с n вершинами и m рёбрами: L имеет только 2m + n ненулей. Системы с лапласианом возникают повсюду: спектральная кластеризация, PageRank, GNN.

**PageRank** Google - решение системы (I − αAᵀD⁻¹)p = (1−α)/n·1 для разреженной матрицы переходов. При n = 10⁹ страниц и ~10 ссылок на страницу: матрица 10⁹ × 10⁹ с ~10¹⁰ ненулями. Итерации власти (power iteration) + разреженный SpMV решают это за ~50 итераций.

Ключевые идеи

• **COO:** три массива (row, col, data); удобен для сборки; плохой для вычислений
• **CSR:** сжатые строки; оптимален для SpMV (A·x); стандарт для итерационных методов
• **CSC:** сжатые столбцы; оптимален для Aᵀ·x и LU-разложения; `scipy.sparse.linalg.spsolve`
• **Заполнение (fill-in):** LU разреженной матрицы без переупорядочивания - O(n²) ненулей; AMD/nested dissection снижает до O(n^{1.5})

Связанные темы

Разреженные матрицы лежат в основе эффективных итерационных методов:

• Итерационные методы — CG, GMRES работают через SpMV - разреженное хранение делает каждую итерацию O(nnz) вместо O(n²)
• Численное вычисление собственных значений — Lanczos и Arnoldi алгоритмы для разреженных матриц - основа scipy.sparse.linalg.eigs

Вопросы для размышления

• Как выбрать между CSR и CSC для алгоритма ALS (Alternating Least Squares) в рекомендательных системах?
• Почему граф-лапласиан симметричен и положительно полуопределён - и что это означает для выбора солвера?
• Как переупорядочивание AMD уменьшает заполнение при LU? (подсказка: минимальная степень в остаточном графе)

Связанные уроки

• la-01-vectors-intro