5.3矩阵的压缩存储 在科学与工程计算问题中,矩阵是一种常用的 数学对象,在高级语言编制程序时,简单而又自 矩阵在这种存储表示之下,可以对其元素进行随 机存取,各种矩阵运算也非常简单,并且存储的 密度为1。但是在矩阵中非零元素呈某种规律分 布或者矩阵中岀现大量的零元素的情況下,看起 来存储密度仍为1,但实际上占用了许多单元去 存储重复的非零元素或零元素,这对高阶矩阵会 造成极大的浪费,为了节省存储空间,我们可 以对这类矩阵进行压缩存储:即为多个相同的非 零元素只分配一个存储空间;对零元素不分配空 可
5.3 矩阵的压缩存储 在科学与工程计算问题中，矩阵是一种常用的 数学对象，在高级语言编制程序时，简单而又自 然的方法，就是将一个矩阵描述为一个二维数组。 矩阵在这种存储表示之下，可以对其元素进行随 机存取，各种矩阵运算也非常简单，并且存储的 密度为1。但是在矩阵中非零元素呈某种规律分 布或者矩阵中出现大量的零元素的情况下，看起 来存储密度仍为1，但实际上占用了许多单元去 存储重复的非零元素或零元素，这对高阶矩阵会 造成极大的浪费，为了节省存储空间， 我们可 以对这类矩阵进行压缩存储：即为多个相同的非 零元素只分配一个存储空间；对零元素不分配空 间
5.3.1特殊矩阵 所谓特殊矩阵是指非零元素或零元素的分布有 定规律的矩阵,下面我们讨论几种特殊矩阵的压 缩存储。 1、对称矩阵 在一个n阶方阵A中,若元素满足下述性质 dii=aii n 则称A为对称矩阵。 对称矩阵中的元素关于主对角线对称,故只要存 储矩阵中上三角或下三角中的元素,让每两个对 称的元素共享一个存储空间,这样,能节约近 半的存储空间。不失一般性,我们按“行优先
5.3.1特殊矩阵 所谓特殊矩阵是指非零元素或零元素的分布有一 定规律的矩阵，下面我们讨论几种特殊矩阵的压 缩存储。 1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij=aji 1≦i,j≦n 则称A为对称矩阵。 对称矩阵中的元素关于主对角线对称，故只要存 储矩阵中上三角或下三角中的元素，让每两个对 称的元素共享一个存储空间，这样，能节约近一 半的存储空间。不失一般性，我们按“行优先
顺序”存储主对角线(包括对角线)以下的元素,其 存储形式如图所示: 15137 50800 a 3025 70613 图51对称矩阵 在这个下三角矩阵中,第行恰有元素,元素总 数为 1+2+.+n=n(n+1)/2 因此,我们可以按图中箭头所指的次序将这些元素 存放在一个向量sa0n(n+1)2-1]中。为了便于访 问对称矩阵A中的元素,我们必须在ai和sak]
顺序”存储主对角线（包括对角线）以下的元素，其 存储形式如图所示： 1 5 1 3 7 a11 5 0 8 0 0 a21 a 22 1 8 9 2 6 a31 a32 a33 3 0 2 5 1 ……………….. 7 0 6 1 3 an 1 a n 2 a n 3 …a n n 图 5.1 对称矩阵 在这个下三角矩阵中，第i行恰有i个元素，元素总 数为： 1+2+…+n=n(n+1)/2 因此，我们可以按图中箭头所指的次序将这些元素 存放在一个向量sa[0..n(n+1)/2-1]中。为了便于访 问对称矩阵A中的元素，我们必须在aij和sa[k]
之间找一个对应关系。 若三j,则a在下三角形中。a;之前的1行(从第1 行到第行)一共有1+2++i1-=1)2个元素,在第i 行上,a1之前恰有j1个元素(即a1a2,a1n),因此 有 k=i*(-1)2+-10至kn(n+1)2 若,则a是在上三角矩阵中。因为a=a1,所以只要 交换上述对应关系式中的和j可得到 k亍j*(j-1)2+1 0三k<n(n+1)2 令Fmax(ij),J=min(ij),则和j的对应关系可统 为 k=*(-1)2+J- 0三k<n(n+1)2
之间找一个对应关系。 若i≧j，则ai j在下三角形中。 ai j之前的i-1行（从第1 行到第i-1行）一共有1+2+…+i-1=i(i-1)/2个元素，在第i 行上， ai j之前恰有j-1个元素（即ai1,ai2,…,ai j-1），因此 有： k=i*(i-1)/2+j-1 0≦k<n(n+1)/2 若i<j，则aij是在上三角矩阵中。因为aij=aji，所以只要 交换上述对应关系式中的i和j即可得到： k=j*(j-1)/2+i-1 0≦ k<n(n+1)/2 令 I=max(i,j)， J=min(i,j)，则k和 i, j的对应关系可统 一为： k=I*(I-1)/2+J-1 0≦ k<n(n+1)/2
因此,a的地址可用下列式计算 LOC(aij=loc(sak) LOC(Sa[0D+k*L=LOC(Sa[0+[ (I-1)/2+J-I*L 有了上述的下标交换关系,对于任意给定一组下标 i,j),均可在sak中找到矩阵元素a,反之,对所有 的k=0,1,2,…,n(n-1)2-1,都能确定sak]中的元素在矩阵 中的位置(ij)。由此,称sann+1)2]为阶对称矩阵A的 压缩存储,见下图 a21a22 n, n k=0123 n(n-1)/2|….n(n+1)/2
因此，aij的地址可用下列式计算： LOC(aij)=LOC(sa[k]) =LOC(sa[0])+k*L=LOC(sa[0])+[I*(I-1)/2+J-1]*L 有了上述的下标交换关系，对于任意给定一组下标 (i，j)，均可在sa[k]中找到矩阵元素aij，反之，对所有 的k=0,1,2,…n(n-1)/2-1，都能确定sa[k]中的元素在矩阵 中的位置(i,j)。由此，称sa[n(n+1)/2]为阶对称矩阵A的 压缩存储，见下图： k=0 1 2 3 n(n-1)/2 n(n+1)/2-1 a11 a21 a22 a31 …… an 1 … … an,n