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

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

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

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