稀疏矩阵简介

森之张卫东

稀疏矩阵

我们要学习三种数据类型：稀疏矩阵，单元阵列和结构。稀疏矩阵是矩阵的一种特殊形式，在这个矩阵中只对非零元素分配内存。单元阵列也是一种矩阵，它的每一个元素可以是MATLAB任何一种数据类型。

它们广泛应用于MATLAB用户图象界面（GUI）函数。最后，结构提供了一种在单个变量中存储了不同类型的数据的方法，在这个变量中的每一个数据项目都有一个独立的名字。

稀疏矩阵

我们已经学过了普通的MATLAB数组。当一个普通的数组被声明后，MATLAB将会为每一个数组元素分配内存。例如函数a = eye(10)要创建了100个元素，按10×10的结构分配，对角线上的元素均为1，其余的元素为0。注意这些数组其中的90个元素为0。这个包含有一百个元素的矩阵，只有10个元素包含非零值。这是稀疏矩阵或稀疏数组的一个例子。稀疏矩阵是指一个很大的矩阵，且大多数的元素为0。

>> a=2*eye(10)

a =

     2     0    0     0     0    0     0     0    0     0

     0     2    0     0     0    0     0     0    0     0

     0     0    2     0     0    0     0     0    0     0

     0     0    0     2     0    0     0     0    0     0

     0     0    0     0     2    0     0     0    0     0

     0     0    0     0     0    2     0    0     0     0

     0     0    0     0     0    0     2     0    0     0

     0     0    0     0     0    0     0     2    0     0

     0     0    0     0     0    0     0     0    2     0

     0     0    0     0     0    0     0     0     0    2

现在假如我们要创建一个10×10的矩阵，定义如下

b =

     1     0    0     0     0    0     0     0    0     0

     0     2    0     0     0    0     0     0    0     0

     0     0    2     0     0    0     0     0    0     0

     0     0    0     1     0     0    0     0     0    0

     0     0    0     0     5    0     0     0    0     0

     0     0    0     0     0    1     0     0    0     0

     0     0    0     0     0    0     1     0    0     0

     0     0    0     0     0    0     0     1    0     0

     0     0    0     0     0    0     0     0    1     0

     0     0    0     0     0    0     0     0    0     1

若a，b两矩阵相乘得到的结果为

>> c = a * b

c =

     2     0    0     0     0    0     0     0    0     0

     0     4    0     0     0    0     0     0    0     0

     0     0    4     0     0    0     0     0    0     0

     0     0    0     2     0    0     0    0     0     0

     0     0    0     0    10    0     0     0    0     0

     0     0    0     0     0    2     0     0    0     0

     0     0    0     0     0    0     2     0    0     0

     0     0    0     0     0    0     0     2    0     0

     0     0    0     0     0    0     0     0    2     0

     0     0    0     0     0    0     0     0    0     2

这两个稀疏矩阵相乘需要1900次相加和相乘，但是在大多数时侯相加和相乘的结果为0，所以我们做了许多的无用功。这个问题会随着矩阵大小的增大而变得非常的严重。例如，假设我们要产生两个200×200的稀疏矩阵，如下所示

a = 5 * eye(200);

b = 3 * eye(200);

每一个矩阵有20000个元素，其中19800个元素是0。进一步说，对这两个矩阵相乘需要7980000次加法和乘法。

我们可以看出对大规模稀疏矩阵进行存储和运算（其中大部分为0）是对内存空间和cpu资源的极大浪费。不巧的是，在现实中的许多问题都需要稀疏矩阵，我们需要一些有效的方示来解决这个问题。

大规模供电系统是现实世界中涉及到稀疏矩阵一个极好的例子。大规模供电系统可以包括上千条或更多的母线，用来产生，传输，分配电能到子电站。如果我们想知道这个系统的电压，电流和功率，我们必须首先知道每一条母线的电压。如果这个系统含有一千个母线，这就要用到含有1000个未知数的联立方程组，包括一个方程，也就是说我们要创建含有1000000个元素的矩阵。解出这个矩阵，需要上百万次的浮点运算。

但是，在这个系统中，一条母线平均只它的三条母线相连，而在这个矩阵中每一行其他的996个元素将为0，所以在这个矩阵的加法和乘法运算中将会产生0。如果在求解的过程中这些0可以忽略，那么这个电力系统的电压和电流计算将变得简单而高效。