三对角矩阵@带状矩阵的压缩存储与换源

三对角矩阵

对角矩阵也称带状矩阵。对 $n$ 阶矩阵 $A$ 中的任意一个元素 $a_{i,j}$，当 $|i-j|>1$ 时，若有 $a_{i,j}=0$ ($1\le i,j\le n$)，则称为三对角矩阵

在三对角矩阵中，所有非零元素都集中在以主对角线为中心的 3 条对角线的区域，其他区域的元素都为零。
$$A_n=\left[\begin{array}{ccccc}{a}_{1,1}& a_{1,2}& 0& \cdots & 0\\ a_{2,1}& a_{2,2}& a_{2,3}& \cdots & 0\\ 0& a_{3,2}& a_{3,3}& \cdots & 0\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& 0& 0& \cdots & a_{n,n}\end{array}\right]$$

$$\left[\begin{array}{cccccc}{a}_{1,1}& a_{1,2}& & & & \\ a_{2,1}& a_{2,2}& a_{2,3}& & 0& \\ & a_{3,2}& a_{3,3}& a_{3,4}& & \\ & & \ddots & \ddots & \ddots & \\ & 0& & a_{n-1,n-2}& a_{n-1,n-1}& a_{n-1,n}\\ & & & & a_{n,n-1}& a_{n,n}\end{array}\right]$$

三对角矩阵 $A$ 也可以采用压缩存储，将 3 条对角线上的元素按行优先方式存放在一维数组 $B$ 中，且 $a_{1,1}$ 存放于 $B[0]$ 中，其存储形式如图下
$$\begin{array}{ccccccccc}{a}_{1,1}& a_{1,2}& a_{2,1}& a_{2,2}& a_{2,3}& \cdots & a_{n-1,n}& a_{n,n-1}& a_{n,n}\end{array}$$

i=1	($Q_{-1}$)(虚拟)	$Q_0$	$Q_1$
2		$Q_2$	$Q_3$	$Q_4$
3			$Q_5$	$Q_6$	$Q_7$
4				$⋮$	…	$⋮$
					Q	Q	Q
						Q	Q

计算带状区域元素数量

带状区域指的是三对角线上的元素构成的区域

前$i-1$行的元素数量

• 第1行到$i-1$行每行都有有三个元素(补上的虚拟元素$Q_{-1}$后面再$-1$,则$s_{i-1}=3(i-1)-1$

第$i$行有$j-(i-1)$个元素

• 三对角矩阵的斜对角区域的第$i$行的三个元素可以表示为:$a_{i,i-1},a_{i,i},a_{i,i+1}$

• 对于带状区域内的第$i$行元素$a_{ij}$,有 j ∈ {   i − 1 , i , i + 1   } j\in\set{i-1,i,i+1} j∈{i−1,i,i+1}

• 所以第$i$行前$a_{ij}$前有$j-(i-1)=j-i+1$个元素,如果算上$a_{ij}$自身,则有$j-(i-1)+1$=$j-i+2$个元素

所以带状区域内,第$a_{ij}$前有$3(i-1)-1+j-i+1$=$2i+j-3$个元素

如果从0计数,那么$a_{ij}$将恰好计数为$2i+j-3$

压缩公式

将三对角矩阵的带状区域依次存入数组$B$,则$a_{ij}$存在数组$B$的索引为

• $k(i,j)$=$2i+j-3$,$|j-i|⩽1$
• $k(i,j)$=$0$,$|j-i|>1$

由$k$确定$i,j$

若已知三对角矩阵中的某个元素$a_{ij}$存放在一维数组$B$的第$k$个位置(索引$k$),则$i,j$的取值分别为多少?

$a$的下标$i,j$都是$1\cdots n$,而不是从0开始计数,但是数组$B$中的元素索引从0开始计数

例如$a_{1,1}$在数组$B$中的索引为$k=0$,也就是$B[0]=a_{1,1}$,现在要求更一般的情况$B[k]=a_{i(k),j(k)}$

也就是确定两个函数$i(k),j(k)$的表达式

根据压缩公式$k=2i+j-3$难以确定$i,j$关于$k$的表达式

先绘制对应的矩阵示意图
$$\left[\begin{array}{ccccc}{a}_{1,1}& a_{1,2}& 0& \cdots & 0\\ a_{2,1}& a_{2,2}& a_{2,3}& \cdots & 0\\ 0& a_{3,2}& a_{3,3}& \cdots & 0\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& 0& 0& \cdots & a_{n,n}\end{array}\right]$$
第一行三对角线上元素为 0, 1，第二行为 2, 3, 4，依此类推。使用省略号来表示中间的元素，以适应任意大小的矩阵。

$$A=\left[\begin{array}{cccccc}0& 1& 0& 0& \cdots & 0\\ 2& 3& 4& 0& \cdots & 0\\ 0& 5& 6& 7& \cdots & 0\\ 0& 0& 8& 9& \ddots & ⋮\\ ⋮& ⋮& ⋮& \ddots & \ddots & n-1\\ 0& 0& 0& \cdots & n& n+1\end{array}\right]A=\left[\begin{array}{cccccc}0& 1& & & & \\ 2& 3& 4& & & \\ & 5& 6& 7& & \\ & & 8& 9& 10& \\ & & & \ddots & \ddots & \ddots \end{array}\right]$$

确定$i(k)$

$i(k)$的表达式形式不是唯一的,只要正确映射$B[k]$对应的元素在三对角矩阵中的位置即可

容易观察到,矩阵A除了第一行以外,每一行都有3个元素,如此排列下去,问题和$B[k]$排列在几行相关;

设矩阵B第一层存放1,2,3,第二层存放4,5,6,依次类推,第$i$层存放的就是$i-2,i-1,i$;或者$3(i-1)+1,3(i-1)+2,3i$

显然第$x$个元素所在的层数为$i=\lceil x/3\rceil$;

现在回到矩阵$A$,可以发现,相对于矩阵B存放$x$的位置变成存放$x-2$,这相当于第一层的前两个存储空间损坏,存放的位置要往后移动2个位置,现在第$x$个元素需要存放到原来存放$x+2$的位置;因此为了计算此时的元素存放层号$i$,可以计算$\lceil (x+2)/3\rceil$

由此得到$k=1,2,\cdots$在矩阵$A$中的行号,$i(k)=\lceil (k+2)/3\rceil$(1)

可以验证$k=0$也满足此公式

另一种表达式

仔细观察矩阵$A$,其第$i$行$(i=1,2,\cdots )$的第2个元素为$3(i-1)$,也就是说第$i$行三对角线上存储的元素分别是索引$3(i-1)-1,3(i-1),3(i-1)+1$;它们的行号都是$i$;将这三个值记为序列$S$

事实上,任意一个合法的$k,(k=0,1,2,\cdots )$,都能找到一个整数$i$使得$k\in S$

如果能找到一种映射关系 f ( {   3 ( i − 1 ) − 1 , 3 ( i − 1 ) , 3 ( i − 1 ) + 1   } ) f(\set{3(i-1)-1,3(i-1),3(i-1)+1}) f({3(i−1)−1,3(i−1),3(i−1)+1})= {   i , i , i   } \set{i,i,i} {i,i,i}就相当于找到$i(k)$函数表达式

令$S$中的三个值分别都加1,得$3(i-1),3(i-1)+1,3(i-1)+2$,这三个数除以3向下取整结果都是$i-1$;

也就是$\lfloor (k+1)/3\rfloor$=$i-1$;从而$i$关于$k$的函数$i(k)$=$\lfloor (k+1)/3\rfloor +1$=$\lfloor (k+1)/3+1\rfloor$(2)

考虑到取整号的性质(无论是向下取整还是向上取整,$[a+z]=[a]+z$,其中$z\in \mathbb{Z}$,因为任何数和整数相加减不会改变小数部分,计算顺序自然不会影响取整结果)

确定$j(k)$

$j(k)$的确定比$i(k)$更容易些,需要用到$i(k)$

首先计算$i(k)$,得知$B[k]$会被排列到第几行($i=i(k)$)

然后计算$B[k]$在第$i$行的第几个位置(从1开始计数)

矩阵$A$的前$i-1$行元素个数为$s_{i-1}=3(i-1)-1$(末尾减1是因为第一行只有2个元素)

那么三对角线第$i$行上剩下$k+1-s_{i-1}$,(其中加1是因为$k$是从0计数的,$B[0]$到$B[k]$共有$k+1$个元素)

而第$i$行三对角线前的元素$i-2$个(注意第$i$行第一个三对角线上的元素列号为$i-1$,再前一号是$i-2$),所以$j=i-2+k+1-s_{i-1}$=$k-2i+3$(3)

公式总结

注意公式中的$i,j$都是从$1$开始计算,如果要从0开始计算,需要各自减去1

三对角线上的元素解压:

• $i(k)$=$\lceil (k+2)/3\rceil$=$\lfloor (k+1)/3\rfloor +1$=$\lfloor (k+1)/3+1\rfloor$
• $j(k)$=$k-2i+3$=$k-2(\lfloor \frac{k+1}{3}+1\rfloor )+3$

其他位置元素全部填充0

应用举例

计算$k=4$时,$a_{ij}$中$i,j$

$i(k)$=$[(4+1)/3+1]$=$2$

$j(k)$=$4-2\times 2+3$=$3$

所以$B[4]=a_{2,3}$

原文地址：https://blog.csdn.net/xuchaoxin1375/article/details/144335763

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！