陣列-sparse matrix的generation

// sparse matrix structure
typedef struct spm {
   int row; // row position
   int col; // column position
   int val; // value
}spm;

// generate a sparse matrix from a
void generate_spm(int *a, spm *s)
{
   // row, column index and counting
   // for nonzero elements
   int r, c, count = 0;
   // initialize first row
   s[0].row = M;
   s[0].col = N;

   for (r = 0; r < M; r++)
      for (c = 0; c < N; c++)
         // if there is an nonzero element
         if (a[r*N + c] != 0) {
            count++;
            s[count].row = r;
            s[count].col = c;
            s[count].val = a[r*N + c];
         }
   s[0].val = count;
}

int main()
{
   int i = 0;
   printf("Enter the matrix elements:\n");
   unsigned size = 0;
   int val;
   while (scanf("%d", &val) != EOF)
      put_to_tail(val);
   size = show_list_and_size();

   int *a = (int*)malloc(sizeof(int)*size);
   list_to_array(a);

   // input M
   FILE *file_in_M;
   file_in_M = fopen("M_size", "r");
   fscanf(file_in_M, "%d", &M);
   if (size % M != 0) {
      fprintf(stderr,"size % M != 0\n");
      exit(1);
   }
   fclose(file_in_M);
   N = size / M;


   int count_non_zero = 0;
   // counting nonzero elements of a
   for (i = 0; i < size; ++i)
      if (a[i] != 0)
         count_non_zero++;
   // allocating s with size of nonzero elements+1
   spm *s = (spm*) malloc(sizeof(spm)*(count_non_zero+1));

   // generate sparse matrix a to s
   generate_spm(a, s);
   //print out the result
   printf("   row  col  val\n---------------\n");
   for (i = 0; i <= count_non_zero; ++i)
      printf("%5i%5i%5i\n", s[i].row, s[i].col, s[i].val);
   return 0;
}   

首先這程式要能work，就先要把sorting的準備的這些function放進去。

這是陣列的一個應用。把一個sparse matrix(也就是matrix的elements有非常多都是0)轉成一個更精簡的matrix，使得：
1. 比較省記憶體空間
2. 處理矩陣運算速度能夠更快

有使用matlab的人如果有研究過的話，應該會曉得這軟體在處理sparse matrix是採用精簡matrix。你可以把它看成是一個對應表格。首先這種表格第一行就是這個矩陣的相關資料。如果這矩陣是M*N的大小，並且有100個非零項的話，那麼這個精簡表格的第一行會是如此的表示：
M   N   100。
接下來的每一行都會是根據非零項的相關位置來對應其值：
原矩陣：
0  3  0  0  1
0  2  1  0  3
7  0  9  0  1
表格矩陣：
3  5  8
0  1  3
0  4  1
1  1  2
1  2  1
1  4  3
2  0  7
2  2  9
2  4  1

看起來好像似乎資料量變多，但其實真正的sparse matrix的非零項會是更多的，假設有一個1000* 1000的matrix，非零項只有10，那麼資料型態若是int的話，原本的矩陣所需要的記憶體空間量將會是sizeof(int) * 1000*1000 但使用這種精簡矩陣的空間量將會大幅減少為sizeof(int)*(10+1) 減少了機乎是100,000倍的空間量。flop次數也更不用講了。

因此先從大方向的main開始講解其架構：

put_to_tail會從io那邊得來的資料放入link list中。接著show_list_and_size會show出link list的資料，來確認放入link list的資料是對的，並同時會回傳資料的筆數。而以此資料的筆數我們就能夠memory allocate資料的大小，並使用list_to_array把link list放入array a以內。

因為筆者的研究本身都是巨量資料，因此是需要memory allocate在記憶體中的，所以這種方式是用一維的陣列來儲存矩陣的資料。因此需要矩陣的input的size M*N。所以開了檔案，input進去M之後check看看這是不是合法的矩陣便能夠了解大小N。

而在generate_spm內我們把矩陣a把它弄成只收集非零項的資料，但即使如此我們還是必須要事先知道大小，因此我們需要一個變數count_non_zero去先了解矩陣有幾個非零項，然後才去mem. allocate我們要的精簡後的matrix s。

把sparse matrix a轉成s後就把s的elements印出來確認無誤。以上就是主要的操作流程。

所以我們需要自訂資料型態spm(sparse matrix的簡寫)，有三個elements：

// sparse matrix structure
typedef struct spm {
   int row; // row position
   int col; // column position
   int val; // value
}spm;

這三個資料就會是我們精簡表格每一個row各自代表的資料，你可以把這矩陣想像成類似坐標那樣，我們需要一個點的資料就必須知道他的坐標，row就像是y坐標，而col就類似x坐標，而val就是這個點的值。這個資料型態將會儲存非０項的位置和其值。

接著generate_spm就將會把sparse matrx(一個1D的array)轉換成表格s。首先這個表格的第一行資料將會是這個sparse matrix的Ｍ，Ｎ，以及非零項的個數，於是我們就先輸入M和N：

   s[0].row = M;
   s[0].col = N;

接著當然我們也可以從外面的count_non_zero來輸入s[0].val。只是目前這邊沒有這樣子做。

然後r，c迴圈去做a的每一個elements的尋訪，找出非零項之後各自輸入到s上：

   for (r = 0; r < M; r++)
      for (c = 0; c < N; c++)
         // if there is an nonzero element
         if (a[r*N + c] != 0) {
            count++;
            s[count].row = r;
            s[count].col = c;
            s[count].val = a[r*N + c];
         }

最後輸入counting的大小，精簡矩陣ｓ就這樣轉換完成了。