22.1 Создание и обработка разреженных матриц

Размер математических задач, которые могут быть обработаны в любой конкретный момент, обычно ограничен доступными вычислительными ресурсами. Как скорость компьютера, так и доступная память накладывают ограничения на размер задачи.

Существует много классов математических задач, которые приводят к матрицам, где большое количество элементов равно нулю. В этом случае имеет смысл иметь специальный тип матрицы для обработки этого класса задач, где хранятся только ненулевые элементы матрицы. Это не только уменьшает объем памяти для хранения матрицы, но также означает, что операции над этим типом матрицы могут использовать априорное знание позиций ненулевых элементов для ускорения вычислений.

Тип матрицы, хранящий только ненулевые элементы, обычно называется разреженным. Цель данного документа — обсудить основы хранения и создания разреженных матриц и основные операции над ними.