矩 阵 压 缩

1. 对称矩阵压缩

[ a x x x x x b x x x x x c x x x x x d x x x x x e ]

⎣⎢⎢⎢⎢⎡​axxxx​xbxxx​xxcxx​xxxdx​xxxxe​⎦⎥⎥⎥⎥⎤​

[ a x b x x c x x x d x x x x e ]

⎡⎣⎢⎢⎢⎢⎢⎢axxxxbxxxcxxdxe⎤⎦⎥⎥⎥⎥⎥⎥$$\left[\begin{array}{ccccc}a& & & & \\ x& b& & & \\ x& x& c& & \\ x& x& x& d& \\ x& x& x& x& e\end{array}\right]$$

⎣⎢⎢⎢⎢⎡​axxxx​bxxx​cxx​dx​e​⎦⎥⎥⎥⎥⎤​

二维数组中$a_{ij}$在一维数组中的下标:
$$k=i(i-1)/2+j-1$$

对于对称矩阵我们可以只保存下三角（包括对角线上的元素），或上三角的元素

原来需要的存储单元个数 $n\times n$ 变成了$(n(n+1)/2)$

2. 上下三角矩阵压缩

2.1 下三角对称矩阵压缩

对于
[ a 11 a 21 a 22 a 31 a 32 a 33 a 41 a 42 a 43 a 44 a 51 a 52 a 53 a 54 a 55 ]

⎣⎢⎢⎢⎢⎡​a11​a21​a31​a41​a51​​a22​a32​a42​a52​​a33​a43​a53​​a44​a54​​a55​​⎦⎥⎥⎥⎥⎤​
将
[ a 11 . . . a i 1 . . . a i j . . . . . . a n 1 . . . a n j . . . a n n ]

⎡⎣⎢⎢⎢⎢⎢⎢a11...ai1...an1......aijanj......ann⎤⎦⎥⎥⎥⎥⎥⎥$$\left[\begin{array}{ccccc}{a}_{11}& & & & \\ ...\\ a_{i1}& ...& a_{ij}& ...& \\ ...\\ a_{n1}& ...& a_{nj}& ...& a_{nn}\end{array}\right]$$

\\ ⎣⎢⎢⎢⎢⎡​a11​...ai1​...an1​​......​aij​anj​​......​ann​​⎦⎥⎥⎥⎥⎤​
转化为
[ a 11 . . . a i 1 . . . a i j . . . a n 1 . . . a n j . . . a n n ]

[a11...ai1...aij...an1...anj...ann]$$\left[\begin{array}{cccccccccccc}{a}_{11}& ...& a_{i1}& ...& a_{ij}& ...& a_{n1}& ...& a_{nj}& ...& a_{nn}& \end{array}\right]$$

\\ [a11​​...​ai1​​...​aij​​...​an1​​...​anj​​...​ann​​​]
原矩阵中的下标$i,j$，对应于数组中的下标$k$

2.2 上三角对称矩阵压缩

对于
[ a 11 a 12 a 13 a 14 a 22 a 23 a 24 a 33 a 34 a 44 ]

⎣⎢⎢⎡​a11​​a12​a22​​a13​a23​a33​​a14​a24​a34​a44​​⎦⎥⎥⎤​
将
[ a 11 . . . a 1 j . . . a 1 n . . . . . . a i j . . . a i n . . . a n n ]

⎡⎣⎢⎢⎢⎢⎢⎢a11...a1j...aij......a1n...ain...ann⎤⎦⎥⎥⎥⎥⎥⎥$$\left[\begin{array}{ccccc}{a}_{11}& ...& a_{1j}& ...& a_{1n}\\ & & ...& & ...\\ & & a_{ij}& ...& a_{in}\\ & & & & ...\\ & & & & a_{nn}\end{array}\right]$$

\\ ⎣⎢⎢⎢⎢⎡​a11​​...​a1j​...aij​​......​a1n​...ain​...ann​​⎦⎥⎥⎥⎥⎤​
转化为
[ a 11 . . . a 1 j . . . a 1 n . . . a i j . . . a i n . . . a n n ]

[a11...a1j...a1n...aij...ain...ann]$$\left[\begin{array}{cccccccccccc}{a}_{11}& ...& a_{1j}& ...& a_{1n}& ...& a_{ij}& ...& a_{in}& ...& a_{nn}& \end{array}\right]$$

\\ [a11​​...​a1j​​...​a1n​​...​aij​​...​ain​​...​ann​​​]
原矩阵中的下标$i,j$，对应于数组中的下标$k$

即:
$$k=(i-1)(2n-i+2)/2+j-i$$

2. 对角矩阵压缩

将矩阵
[ a 11 a 12 0 0 0 a 21 a 22 a 23 0 0 0 a 32 a 33 a 34 0 0 0 a 43 a 44 a 45 0 0 0 a 54 a 55 ]

⎣⎢⎢⎢⎢⎡​a11​a21​000​a12​a22​a32​00​0a23​a33​a43​0​00a34​a44​a54​​000a45​a55​​⎦⎥⎥⎥⎥⎤​
压缩为一维矩阵
[ a 11 a 12 a 21 a 22 a 23 a 32 a 33 a 34 a 43 a 44 a 45 a 54 a 55 ]

[a11a12a21a22a23a32a33a34a43a44a45a54a55]$$\left[\begin{array}{ccccccccccccc}{a}_{11}& a_{12}& a_{21}& a_{22}& a_{23}& a_{32}& a_{33}& a_{34}& a_{43}& a_{44}& a_{45}& a_{54}& a_{55}\end{array}\right]$$

[a11​​a12​​a21​​a22​​a23​​a32​​a33​​a34​​a43​​a44​​a45​​a54​​a55​​]
原来$n\times n$个存储单元现在只要$3n-2$个

原矩阵中的下标$i,j$，对应于数组中的下标$k$

即
$$k=2i+j-3$$
已知$k$:
{ i = ⌊ ( k + 1 ) / 3 ⌋ + 1 j = k − 2 i + 3

{i=⌊(k+1)/3⌋+1j=k−2i+3​