数据结构：带对角矩阵

贡献者： 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. ^ 这并不是标准的编号方式，只是这里为了讲解临时使用的。

致读者：小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。因此，我们请求广大读者热心打赏 ，使网站得以健康发展。如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损，并在接下来的一年里向所有读者继续免费提供优质内容。但遗憾的是只有不到 1% 的读者愿意捐款，他们的付出帮助了 99% 的读者免费获取知识，我们在此表示感谢。