数学建模社区-数学中国

标题: 稀疏矩阵简介 [打印本页]

作者: 森之张卫东 时间: 2015-9-26 22:50
标题: 稀疏矩阵简介
稀疏矩阵

我们要学习三种数据类型：稀疏矩阵，单元阵列和结构。稀疏矩阵是矩阵的一种特殊形式，在这个矩阵中只对非零元素分配内存。单元阵列也是一种矩阵，它的每一个元素可以是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可以忽略，那么这个电力系统的电压和电流计算将变得简单而高效。

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)