Разреженные матрицы и их хранение: форматы CSR, CSC и COO
Экономия памяти в гигантских системах
В задачах математического моделирования, о которых мы многократно упоминали (метод конечных элементов для прочностных расчетов, метод конечных разностей в гидродинамике, расчет графов в социальных сетях), возникают матрицы колоссальных размеров. Матрица системы из миллиона уравнений содержит триллион элементов. Если попытаться сохранить ее в оперативной памяти компьютера в обычном плотном двумерном формате (каждое число типа double precision занимает 8 байт), потребуется 8 терабайт оперативной памяти! Таких ресурсов нет у обычных серверов.
Однако природа приходит на помощь. Матрицы, возникающие при моделировании физических процессов, являются сверхразреженными. Это означает, что 99,99% элементов в такой матрице — это нули. Каждое уравнение связывает только несколько соседних физических узлов. Хранить миллиарды нулей в памяти и умножать на них (тратя процессорное время впустую) — невероятная глупость. Поэтому в вычислительной линейной алгебре разработаны специализированные форматы упаковки и хранения данных, которые игнорируют нули, радикально сжимая объем требуемой памяти.
Координатный формат (COO)
Самым интуитивно понятным и простым способом сохранения разреженной матрицы является координатный формат (Coordinate format, COO). В этом формате матрица хранится в виде трех одномерных массивов одинаковой длины (равной количеству ненулевых элементов, NNZ). Первый массив хранит сами значения (ненулевые числа). Второй массив хранит индексы строк для этих значений. Третий массив хранит индексы столбцов.
Например, если число 5.4 находится во 2-й строке и 3-м столбце, то в массив значений пишется 5.4, в массив строк — 2, в массив столбцов — 3. Этот формат великолепно подходит для первоначальной сборки матрицы по частям (например, при агрегации конечных элементов), так как в него очень легко добавлять новые числа. Однако для быстрого матричного умножения он не является оптимальным из-за недостаточной структурированности.
Форматы сжатого хранения строк (CSR) и столбцов (CSC)
Индустриальным стандартом для быстрых вычислений (решения СЛАУ и умножения матрицы на вектор) стал Формат Сжатого Хранения Строк (Compressed Sparse Row, CSR). Этот формат также использует три одномерных массива, но упаковывает индексы строк гораздо умнее, чем COO. Массив значений и массив индексов столбцов остаются такими же (хранятся элементы, перебираемые слева направо и сверху вниз). Но массив строк заменяется на массив «указателей на начало строк» (row_ptr).
Массив row_ptr имеет размер, равный количеству строк в матрице плюс один. Каждый элемент этого массива показывает, на каком индексе в массиве значений начинается новая строка матрицы. Вычисляя разность между соседними элементами массива row_ptr, компьютер мгновенно узнает, сколько ненулевых элементов содержится в конкретной строке. Это обеспечивает феноменально быстрый доступ к элементам при умножении. Абсолютно симметричным является Формат Сжатого Хранения Столбцов (Compressed Sparse Column, CSC), где сжимаются индексы столбцов, а элементы записываются сверху вниз и слева направо. CSR оптимизирован для умножения y = A*x, а CSC — для y = A^T*x. Все современные библиотеки линейной алгебры (Intel MKL, SciPy.sparse, cuSPARSE на видеокартах) построены на глубокой аппаратной оптимизации этих форматов упаковки.