数据结构：带对角矩阵

贡献者： addis

预备知识　密矩阵

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

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

　　举一个例子，若列主序密矩阵（表 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. ^ 这并不是标准的编号方式，只是这里为了讲解临时使用的。