数据结构:带对角矩阵

                     

贡献者: addis

预备知识 密矩阵

   在 CBLAS 中,我们可以用带对角矩阵(band diagonal matrix)的数据结构来储存矩阵,减少不必要的零元素的储存和运算。和密矩阵一样,带对角矩阵同样分为行主序和列主序两种。

   要把一个密矩阵转换成列主序带对角矩阵,就把每个对角线都排成一行,并保持每个元素的列标不变即可。同理,要转换成行主序带对角矩阵,就把每个对角线都排成一列,保持每个元素的行标不变。

   举一个例子,若列主序密矩阵(表 1 )中只有几个对角线不为零,当这样的矩阵很大时,就会在左下角和右上角出现大量的矩阵元为零,不仅占用内存,矩阵运算时也效率不高。为了方便我们不妨把不为零的矩阵元依次编号1

   列主序带对角矩阵如表 2 ,列主序带对角矩阵如表 3

表1:密矩阵
01 04
02 05 08
03 06 09 12
07 10 13 15
11 14 16 17
表2:列主序带对角矩阵
04 08 12 15 17
01 05 09 13 16
02 06 10 14
03 07 11
表3:行主序带对角矩阵
01 04
02 05 08
03 06 09 12
07 10 13 15
11 14 16 17

1. 索引转换

   令表 1 表 3 中矩阵的行数和列数分别为 $N_1, N_2$,行标分别为 $i, i_c, i_r$,列标分别为 $j, j_c, j_r$。单索引分别为 $k, k_c, k_r$。再令 $i_{diag}$ 为表 2 中对角线所在的行标,$j_{diag}$ 为表 3 中对角线所在的列标,那么有以下转换公式

\begin{equation} \left\{\begin{aligned} &i_c = i-j + i_{diag}\\ &j_c = j\\ &k_c = i_c + N_1 j_c = i + i_{diag} + (N_1-1) j \end{aligned}\right. ~.\end{equation}
\begin{equation} \left\{\begin{aligned} &i_r = i\\ &j_r = j-i + j_{diag}\\ &k_r = N_2 i + j = (N_2-1) i + j + j_{diag} \end{aligned}\right. ~.\end{equation}


1. ^ 这并不是标准的编号方式,只是这里为了讲解临时使用的。

                     

© 小时科技 保留一切权利