对上/下三角矩阵和三对角矩阵压缩存储时元素存储地址的计算方法

前言

本文将给出在对【上三角矩阵】、【下三角矩阵】和【三对角矩阵】以【行主序】方式在【一维数组】中压缩存储时元素存储地址的计算方法以及图像示例,以作参考。

正文

Tips:
以下公式中所指的“矩阵”都是 $n \times n$ 阶的方阵。

上三角矩阵

上三角矩阵指的是主对角线以下(不包括主对角线)的元素全为 $0$ 或者同一个非零常数(记作 $C$),如图 1 所示。我们可以把这个数字 $C$ 存放到一维数组的【最后一个】存储单元中。

图 1.

该矩阵中除了 $C$ 之外,其他元素存储位置的计算公式为:

$$
LOC(A_{[i][j]}) =
$$

$$
LOC(A_{[1][1]}) +
$$

$$
前 i – 1 行的非零元素 +
$$

$$
第 i 行中 A_{[i][j]} 前的非零元素 =
$$

$$
LOC(A_{[1][1]}) + \frac{(i-1)(2n-i+2)}{2} + (j-i).
$$

下三角矩阵

下三角矩阵指的是主对角线以上(不包括主对角线)的元素全为 $0$ 或者同一个非零常数(记作 $C$),如图 2 所示。我们可以把这个数字 $C$ 存放到一维数组的【最后一个】存储单元中。

图 2.

该矩阵中除了 $C$ 之外,其他元素存储位置的计算公式为:

$$
LOC(A_{[i][j]}) =
$$

$$
LOC(A_{[1][1]}) +
$$

$$
前 i – 1 行的非零元素 +
$$

$$
第 i 行中 A_{[i][j]} 前的非零元素 =
$$

$$
LOC(A_{[1][1]}) + \frac{i(i-1)}{2} + (j-1).
$$

三对角矩阵

三对角矩阵指的是除了主对角线以及主对角线两侧之外的其他元素都为 $0$ 或者同一个非零常数(记作 $C$),如图 3 所示。我们可以把这个数字 $C$ 存放到一维数组的【最后一个】存储单元中。

图 3.

该矩阵中除了 $C$ 之外,其他元素存储位置的计算公式为:

$$
LOC(A_{[i][j]}) =
$$

$$
LOC(A_{[1][1]}) +
$$

$$
3 ( i – 1 ) – 1 + j – i + 1 =
$$

$$
LOC(A_{[1][1]}) + 2 ( i – 1 ) + ( j – 1 ).
$$

Tips:
可以结合上文中的图示多计算几遍,辅助对公式的记忆。