Хранение и чтение n-мерных разреженных матриц

Question

Страница Wikipedia в формате Yale для хранения разреженных матриц охватывает 2D-матрицы, но как насчет более высоких измерений?Существуют ли какие-либо алгоритмы, такие как формат Yale (или расширения?), Которые могут хранить n> 2-мерных разреженных матриц?сырые матрицы.

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

Answer 1

Мы можем представить две крайности:

• В одном крайнем случае вы предполагаете, что большая доля элементов отлична от нуля, поэтому вы просто сохраняете значение каждого отдельного элемента (без оптимизации для разреженности)не нужно хранить дополнительную информацию о расположении элементов и получить общий размер mn .
• С другой стороны, вы предполагаете, что небольшая доля элементов не равна нулюТаким образом, вы храните только ненулевые элементы, но теперь вам также необходимо сохранить их позиции (строки и столбцы) и получить общий размер 3‌ x (где x - это числоненулевые значения).

Йельский формат является компромиссом между этими двумя, где мы предполагаем, что число ненулевых элементов больше, чем число строк, ¹ , но мало по сравнению собщее количество элементов;поэтому мы сохраняем указатель ² для каждой строки, а затем сохраняем значение и позицию каждого элемента в его строке, давая общий размер m + 2‌ x .

Имея более двух измерений, вы можете продолжать идти на тот же компромисс;вам просто нужно выбрать правильное измерение или правильную комбинацию измерений, чтобы число ненулевых элементов было меньше, чем число строк / гиперстрок / и т. д.

Например, для m × n × p массив, проиндексированный ( i , j , k ), выиметь два варианта компромисса: ³

• Если ожидается, что число ненулевых элементов превысит небольшую долю mn ,но намного меньше, чем mnp , тогда для каждого i и j вы можете хранить указатель на одномерный «срез» элементов, которые имеют этот i и j .Для каждого ненулевого элемента в этом срезе вы сохраняете его значение и k для общего размера mn + 2‌ x .
• Если ожидается, что число ненулевых элементов будет больше, чем небольшая доля m , но намного меньше, чем mn , то для каждого i можно сохранитьуказатель на двумерный «фрагмент» элементов, которые имеют это i .Для каждого ненулевого элемента в этом срезе вы сохраняете его значение, j и k , для общего размера m + 3‌ x.

В более широком смысле, d -мерный массив будет иметь d -1 компромиссных опций.,,или всего 2 ^d опций, если вы учитываете каждый возможный выбор размеров отдельно.

---

Примечания:

1. Я пишу здесь «строки», но вы также можете делать то же самое по столбцам.
2. Не обязательно «указатель» в очень строгом смысле;вы можете просто сохранить общее количество всех ненулевых элементов во всех предыдущих строках.
3. Не считая того факта, что вы можете использовать разные измерения;Если вы можете использовать формат Yale для строк или столбцов, вы можете использовать эти параметры для любого размера измерений.