Пример формата столбца сжатия для матриц с недостатком ранга

Question

Я впервые имею дело с форматом хранения с сжатием столбцов (CCS) для хранения матриц. После небольшого приближения, если я прав, в матрице, содержащей n ненулевых элементов, CCS выглядит следующим образом:

-we define a vector A_v of dimensions n x 1 storing the n non-zero elements 
 of the matrix

- we define a second vector A_ir of dimensions n x 1 storing the rows of the 
  non-zero elements of the matrix

-we finally define a third vector A_jc whose elements are the indices of the 
 elements of A_v which corresponds to the beginning of new column, plus a 
 final value which is by convention equal t0 n+1, and identifies the end of 
 the matrix (pointing theoretically to a virtual extra-column). 

Так, например, если

M = [1 0 4 0 0;
     0 3 5 2 0;
     2 0 0 4 6;
     0 0 7 0 8]

мы получаем

A_v = [1 2 3 4 5 7 2 4 6 8];

A_ir = [1 3 2 1 2 4 2 3 3 4];

A_jc = [1 3 4 7 9 11];

мои вопросы

Я) это то, что я написал правильно, или я что-то не так понял?

II) что, если я хочу представить матри с некоторыми столбцами, которые являются нулями, например,

   M2 = [0 1 0 0 4 0 0; 
         0 0 3 0 5 2 0;
         0 2 0 0 0 4 6;
         0 0 0 0 7 0 8]

не будет ли представление M2 в CCS идентичным представлению M?

Спасибо за помощь!

Answer 1

Я) это то, что я написал правильно, или я что-то не так понял?

Вы совершенно правы. Однако вы должны позаботиться о том, чтобы при использовании библиотеки C или C++ смещения и индексы начинались с 0. Здесь, я полагаю, вы прочитали какой-то документ на Фортране, индексы которого начинаются с 1. Чтобы быть понятным, здесь ниже версия на С, которая просто переводит индексы вашего правильного ответа в стиле Фортрана:

A_v  = unmodified

A_ir = [0 2 1 0 1 3 1 2 2 4] (in short [1 3 2 1 2 4 2 3 3 4] - 1)

A_jc = [0 2 3 6 8 10] (in short [1 3 4 7 9 11] - 1)

II) что, если я хочу представить матрицу с некоторыми столбцами, которые являются нулями, например, M2 = [0 1 0 0 4 0 0; 0 0 3 0 5 2 0; 0 2 0 0 0 4 6; 0 0 0 0 7 0 8]

не будет ли представление M2 в CCS идентичным представлению M?

Если у вас есть пустой столбец, просто добавьте новую запись в таблицу смещений A_jc. Поскольку этот столбец не содержит элементов, это новое значение записи является просто значением предыдущей записи. Например, для M2 (с индексом, начинающимся с 0) у вас есть:

A_v  = unmodified
A_ir = unmodified
A_jc = [0 0 2 3 6 8 10]   (to be compared to [0 2 3 6 8 10])

Следовательно, два представления являются разными.

---

Если вы только начинаете изучать разреженные матрицы, здесь есть отличная бесплатная книга: http://www-users.cs.umn.edu/~saad/IterMethBook_2ndEd.pdf