Первое, что нужно попробовать, это всегда существующие библиотеки и решения.Это большая работа по созданию пользовательских форматов, работающих со всеми операциями, которые вы захотите в конце концов.Разреженные матрицы - это старая проблема, поэтому убедитесь, что вы читаете о существующем материале.
Предполагая, что вы не найдете ничего подходящего, я бы рекомендовал формат на основе строк.Не пытайтесь слишком увлекаться сверхкомпактными представлениями, у вас будет много обработки, необходимой для каждой маленькой операции и ошибок в вашем коде.Вместо этого попробуйте сжать каждый ряд отдельно.Вы знаете, что вам придется сканировать каждую строку для умножения матрицы на вектор, чтобы упростить себе жизнь.
Я бы начал с кодирования длин серий, посмотрим, как это работает в первую очередь.Как только это сработает, попробуйте добавить некоторые трюки, такие как ссылки на разделы предыдущего ряда.Таким образом, строка может быть закодирована как: 126 нулей, 8 единиц, 1000 записей, скопированных непосредственно из строки выше, 32 нуля.Похоже, что это может быть очень эффективно с вашим примером.