-03-24 20:13发布 假设一个N*N的矩阵从a11开始编号，对于一个上三角矩阵按行优先方式进行存储，请写出压缩存储公式的推导过程

假设矩阵为：

$$A=\begin{pmatrix}
a_{11} & a_{12} & \cdots & a_{1n}\\
0 & a_{22} & \cdots & a_{2n}\\
\vdots&\vdots&\ddots&\vdots\\
0&0&\cdots&a_{nn}
\end{pmatrix}$$

对于上三角矩阵，下三角部分都是0，可以将它们省略掉，用一维数组存储矩阵中所有非零元素。可以发现，非零元素有$n+(n-1)+\cdots+2+1=\frac{n(n+1)}{2}$个，因此数组大小为$\frac{n(n+1)}{2}$。

按行优先存储，则将第一行中的元素按顺序存储，再将第二行中除去第一个元素的其他元素按顺序存储，依次类推。也就是存储顺序是：

$a_{11},a_{12},\cdots,a_{1n},a_{22},\cdots,a_{2n},\cdots,a_{nn}$

压缩存储的公式推导如下：

设压缩存储后的一维数组为$B$，$A_{i,j}$表示矩阵中第$i$行，第$j$列元素的值，$B_k$表示第$k$个非零元素的值，$n$为矩阵的阶数，则有：

$$k = \frac{i(i-1)}{2}+j$$

此式的推导可以从$i=1,j=1$开始，对矩阵中每一个非零元素进行编号，得到矩阵中任意一个非零元素的编号$k$。

因为按行优先存储，所以矩阵中第$i$行前面共有$i-1$行，每行有$i-1$个元素，因此前面共有$\sum_{m=1}^{i-1}m=\frac{i(i-1)}{2}$个元素。加上第$j$列，就是矩阵中第$i$行第$j$列元素的位置。

根据以上推导，可以得到压缩存储公式：

$$B_k = A_{i,j} = A_{\lfloor\frac{-1+\sqrt{8k+1}}{2}\rfloor+1,k-\frac{\lfloor\frac{-1+\sqrt{8k+1}}{2}\rfloor(\lfloor\frac{-1+\sqrt{8k+1}}{2}\rfloor+1)/2}+1}$$

其中，$\lfloor x\rfloor$表示不大于$x$的最大整数。此公式可以将一维数组中的第$k$个元素还原成矩阵中的元素。