7 稀疏矩阵
稀疏矩阵是一种特殊类型的矩阵，即矩阵包含较多的零元素。 针对稀疏矩阵的这一特点，可以只保存矩阵中的非零元素以及非零元素在矩阵中的位置。 在使用稀疏矩阵进行计算时，可以通过消除零元素来减少计算时间。
7.1 稀疏矩阵的存储方法
对于一般矩阵来说，保存的是矩阵中的每个元素。 矩阵中的零元素需要与其他元素占用相同大小的内存空间。 但对于稀疏矩阵，只存储非零元素及其在稀疏矩阵中对应的位置，其他空位置在访问时简单地用默认的零元素填充。 对于包含大量零元素的大矩阵，使用这种方法可以大大减少数据占用的内存空间。
使用3个内部数组来存储元素为实数的稀疏矩阵。
稀疏矩阵也可用于存储复数。 当稀疏矩阵用于存储复数数据时，需要第四个内部数组来存储非零复数的虚部。 如果复数的实部或虚部至少之一非零，则复数非零。
【例2-16】稀疏矩阵与一般矩阵的内存使用情况比较。
>> = 魔法(1100); % 创建一个1100´1100矩阵
>> (>50) = 0; % 将 >50 的元素设置为 0
>> = (); % 创建稀疏矩阵
>> 是谁
名称大小字节
9608
在这个例子中，两个变量实际上存储了相同的矩阵。 但由于两者使用的存储形式分别是普通矩阵和稀疏矩阵，因此占用的内存量相差近1000倍。 由于版本和操作系统的不同（如32位和64位），内部存储格式也会发生变化，但总体占用的内存空间比一般矩阵要小得多。
7.2 稀疏矩阵的创建
稀疏矩阵永远不会自动创建，由用户决定是否使用稀疏矩阵。 在创建矩阵之前，用户需要根据矩阵是否包含较多的零元素以及使用稀疏矩阵技术是否有利来决定是否使用稀疏矩阵的形式。 矩阵中非零元素的数量除以所有元素的数量称为矩阵的密度。 密度越小，矩阵采用稀疏矩阵格式越有利。
要将一般矩阵转换为稀疏矩阵，可以使用函数，如s=(A)，它是指将矩阵A转换为稀疏矩阵。 另外，可以使用函数full将稀疏矩阵转换为通用矩阵。
[例2-17] 普通矩阵与稀疏矩阵转换示例。
>> A=[0 0 0 1;0 1 0 0;1 2 0 0;0 0 3 0]
A=
0 00 1
0 10 0
1 20 0
0 03 0
>> s=(A)
s =
(3,1)1
(2,2)1
(3,2)2
(4,3)3
(1,4)1
>> B=满
B=
0 00 1
0 10 0
1 20 0
0 03 0
从这个例子的结果中，我们可以看到s的所有非零元素列表及其对应的行号和列号。 所有非零元素都存储在列中，反映数据的内部结构。
稀疏矩阵通常通过以下方式创建。
1.直接创建稀疏矩阵
使用函数，您可以直接从一组非零元素创建稀疏矩阵。 函数调用格式为：
S=(i,j,s,m,n)
其中，i和j都是向量，分别指矩阵中非零元素的行数和列数。 s是所有非零元素组成的向量，元素在矩阵中排列的位置为(i,j)。 m是输出稀疏矩阵的行数，n是输出稀疏矩阵的列数。
[例2-18] 稀疏矩阵的创建。
>> S=([1 3 2 1 4],[3 1 4 1 4],[1 2 3 45],4,4)
S =
(1,1) 4
(3,1)2
(1,3)1
(2,4)3
(4,4)5
>> 全(S)
答案=
4 01 0
0 00 3
2 00 0
0 00 5
在这个例子中，稀疏矩阵S是直接通过函数创建的。 函数中前两个输入变量[1 3 2 1 4]和[3 1 4 1 4]是矩阵中元素的位置，第三个输入变量[1 2 3 4 5]是前两个输入稀疏矩阵的变量。 输入变量中位置对应的元素的值，最后两个输入变量4表示输出稀疏矩阵的行数为4，输出稀疏矩阵的列数为另外4.通过全函数将稀疏矩阵转换为一般矩阵，这样就可以清楚地看到函数输入和输出之间的关系。
应该指出的是，该函数还有一个变体，可以设置非零元素的最大数量。 如果需要的话，可以在函数中添加第六个输入参数，用于设置稀疏矩阵中非零元素的最大数量，这样以后如果向矩阵中添加非零元素，就不需要修改矩阵的结构。 具体使用方法请参考帮助文档。
2.从对角线元素创建稀疏矩阵
要将矩阵的对角线元素保存在稀疏矩阵中，可以使用该函数。 其调用格式为：
S=(B,d,m,n)
该函数用于创建大小为 m 行和 n 列的稀疏矩阵 S。 其非零元素来自矩阵B中的元素并且对角排列。 参数 d 指定用于生成稀疏矩阵 B 的矩阵 B 中的对角线位置。 矩阵的主对角线可以视为第 0 个对角线。 每向右上方移动一条对角线，数字就加1，向左下移动一条对角线，数字就减少1。也就是说，B中的第j列填充了向量d 。 元素，j 指定对角线。
[例2-19] 稀疏矩阵的创建。
>> B=[1 2 3;4 5 6;7 8 9;10 11 12]
B=
1 23
4 56
7 89
10 1112
>>d=[-3 0 2]
d =
-3 02
>> A=(B,d,7,4)
A=
(1,1)2
(4,1)1
(2,2)5
(5,2)4
(1,3)9
(3,3)8
(6,3)7
(2,4) 12
(4,4)11
(7,4) 10
>> 完整(A)
答案=
2 09 0
0 50 12
0 08 0
1 00 11
0 40 0
0 07 0
0 00 10
此示例生成一个 7 行 4 列的稀疏矩阵 A。 B 的第 1 列中的元素排列在主对角线下方的第 3 个对角线上，第 2 列中的元素排列在主对角线上，第 3 列中的非零元素排列在主对角线上方的第 3 个对角线上。 在第二个对角线上。 这里需要注意的是，B中的第三列并不是全部分布在第二条对角线上，而是最后两个元素9和12排列在这条对角线上。
3.从外部文件导入稀疏矩阵
使用外部文件创建的文本文件。 如果文件中的数据排列为 3 或 4 列，则可以将文本文件加载到内存中并用于创建稀疏矩阵。
[例2-20] 稀疏矩阵的创建。
如果有这样一个文件.dat（用户可以通过记事本打开并编辑其内容），该文件包含以下数据：
1 1 1.0000
1 2 0.5000
2 2 0。
1 3 0。
2 3 0.2500
3 3 0.2000
1 4 0.2500
2 4 0.2000
3 4 0.6667
4 4 0.7143
4 4 0.0000
然后就可以使用load命令加载这个数据文件，然后对其进行操作。 实际中，用户可以在命令窗口中输入：
>> load .dat % 使用load命令将数据文本文件.dat加载到工作区中
>> H = ()
H =
(1,1) 1.0000
(1,2) 0.5000
(2,2)0.3333
(1,3)0.3333
(2,3)0.2500
(3,3) 0.2000
(1,4)0.2500
(2,4) 0.2000
(3,4)0.1667
(4,4)0.1429
>> 全(H)
答案=
1.0000 0.5000 0.33330.2500
0 0.3333 0.25000.2000
0 0 0.20000.1667
0 0 00.1429
此示例首先使用 load 函数导入包含 3 列数据的文本文件 .dat。 用户可以通过在命令行中输入变量名来查看数据中的具体内容，验证数据是否读取正确，然后调用将其转换为对应的稀疏矩阵H。生成的稀疏矩阵可以直观地看到通过调用完整函数。
使用load函数导入外部数据文件。 具体使用请参见第10章。
7.3 稀疏矩阵的运算
大多数内置数学函数都可用于处理稀疏矩阵。 在这种情况下，稀疏矩阵可以被视为一般矩阵。 还有一些专门针对稀疏矩阵的函数。 处理稀疏矩阵时，计算复杂度与稀疏矩阵中非零元素的数量成正比，也与矩阵的行和列维度有关。 例如稀疏矩阵的乘法和幂运算、包含一定次数的线性方程组等都是比较复杂的运算。
使用函数处理稀疏矩阵时，计算结果必须遵循以下原则。
(1)函数处理矩阵时，无论该矩阵是一般矩阵还是稀疏矩阵，返回值都是数值或矩阵。 返回值以通用矩阵格式保存，基于接受的参数是稀疏矩阵，结果不会保存为稀疏矩阵。
（2）当函数处理数值或向量并返回矩阵时，如果矩阵是零矩阵、所有元素为1的矩阵、随机矩阵或单位矩阵，这些矩阵都是以下形式的一般矩阵。 对于零矩阵，有类似于稀疏矩阵的存储方法。 由于零矩阵中没有非零元素，因此零矩阵无法转换为稀疏矩阵，但可以使用指令zeros(m,n)和(m,n)。 的。 对于单位矩阵和随机矩阵，可以使用类似于稀疏矩阵的运算指令，即speye和。 对于元素全为1的矩阵，没有类似的运算指令。
(3) 以矩阵为参数并返回矩阵或向量的一元函数。 返回值的存储类型与参数的存储类型相同。 例如，在矩阵S的分解中，如果S是一般矩阵，则结果也是一般矩阵； 如果 S 是稀疏矩阵，则结果也是稀疏矩阵。 对于按列方向处理矩阵的函数，例如求每列最大值的函数 max、求每列和的函数 sum 等，它们也返回与参数相同的存储类型。 如果参数是稀疏矩阵，即使返回的矩阵或向量具有所有非零元素，它也会以稀疏方式表示。 唯一的例外是 和 full，因为它们用于一般矩阵和稀疏矩阵之间的转换。
(4) 对于两个输入参数都是矩阵的情况，如果两个输入矩阵都是稀疏矩阵，则输出仍然是稀疏矩阵； 都是一般矩阵，结果也是一般矩阵。 如果输入参数之一是稀疏矩阵，另一个是一般矩阵，则结果通常是一般矩阵，但在能够保证矩阵稀疏性不变的运算中，结果是稀疏矩阵。
(5) 使用方括号组合矩阵时，如果组合矩阵中存在稀疏矩阵，则结果将为稀疏矩阵。
(6) 右侧子矩阵的赋值操作的返回值为右侧子矩阵的存储类型。 左侧子矩阵的赋值不会改变其存储类型。
[例2-21] 稀疏矩阵的组合。
>> A=[1 0 0;0 0 1;1 2 0]
A=
1 00
0 01
1 20
>> B=(A)
B=
(1,1)1
(3,1)1
(3,2)2
(2,3) 1
>> C=[A(:,1),B(:,2)]
C=
(1,1)1
(3,1)1
(3,2)2
在这个例子中，矩阵A的第一列和矩阵B的第二列组成了一个新的矩阵C。从结果中我们可以看出C是一个稀疏矩阵。
[例2-22] 稀疏矩阵子矩阵的赋值。
>> A=[1 0 0;0 0 1;1 2 0];
>> B=(A);
>> C=(猫(1,满(B),A))
C=
(1,1)1
(3,1)1
(4,1)1
(6,1)1
(3,2)2
(6,2)2
(2,3) 1
(5,3)1
>> i=[1 2 3];
>> j=[1 2 3];
>> T=C(i,j)
T=
(1,1)1
(3,1)1
(3,2)2
(2,3) 1
>> C(j,i)=full(T) % 将一般矩阵赋值给稀疏矩阵，仍然返回稀疏矩阵
C=
(1,1)1
(3,1)1
(4,1)1
(6,1)1
(3,2)2
(6,2)2
(2,3) 1
(5,3)1
7.4 稀疏矩阵的交换和重新排序
稀疏矩阵S的行交换和列交换可以用以下两种方法表示。
(1) 对于交换矩阵P，稀疏矩阵S的行交换可以表示为P*S，列交换可以表示为P*S'。
(2) 对于交换向量p，p是包含1到n个自然数的一般向量的排列。 在稀疏矩阵上执行行交换可以表示为 S(p,:)。 S(:,p) 是列交换形式。 矩阵S的某一列的行交换可以表示为S(p,n)。 例如，S(p,1)是第一列的交换。
[例2-23]稀疏矩阵S的交换。
>> p=[1 3 2 4];
>> S=眼睛(4,4)
S =
1 00 0
0 10 0
0 01 0
0 00 1
>> P=S(p,:)
P=
1 00 0
0 01 0
0 10 0
0 00 1
>> V=S(p,2)
V =
矩阵 P 的第 1 行是 S 的第 1 行，第 2 行是 S 的第 3 行，依此类推。 也就是说，矩阵 S 的行按照向量 p 指定的顺序进行调整。
>> S1=斯佩(4,4)
S1=
(1,1)1
(2,2)1
(3,3)1
(4,4)1
>> P1=S1(p,:) % 对于稀疏矩阵的行和列的交换，返回的形式仍然是稀疏矩阵
P1 =
(1,1)1
(3,2)1
(2,3) 1
(4,4)1
对于稀疏矩阵S1，交换行和列，返回的P1仍然是稀疏矩阵。 对稀疏矩阵的列重新排序有时可以使矩阵分解更快。 最简单的矩阵排序是基于矩阵中非零元素的数量。 该方法对于元素极其不规则的矩阵非常有效，特别适合行或列中非零元素数量变化较大的矩阵。 提供了一个非常简单的函数可以实现这种排序方法。 该函数的M文件只有以下几行：
p=(S)
if ~(S) % 判断输入变量是否为矩阵
错误（（'：：'））; % 如果不满足条件则返回错误信息
结尾
[~,p] = 排序(完整(sum(S ~= 0, 1)));
程序第5行实现了以下四个函数。
(1)调用S~=0判断矩阵中每个元素是否为0。 如果不是，则返回逻辑值 1。
(2) 函数 sum 求上一步创建的矩阵每一列的和，即每一列中非零元素的数量。
(3) 函数full将上一步创建的向量转换为通用向量格式。
(4) 使用函数sort对上一步创建的向量元素进行升序排序。 函数 sort 的第二个输出参数 p 是交换向量，用于对矩阵 S 的每列中非零元素的数量进行重新排序。
[例2-24] 对于下面的矩阵A，首先使用函数得到交换向量p，然后根据向量p对矩阵A的各列按照非零元素的个数升序排序。
>> A=[0 1 2 3;3 2 1 0;0 0 2 0;1 0 0 2]
A=
0 12 3
3 21 0
0 02 0
10 0 2
>>p=(A)
p =
1 24 3
>> B=A(:,p)
B=
0 13 2
3 20 1
0 00 2
1 02 0
结果表明，矩阵B是将A的各列按照非零元素个数升序排序的结果。
7.5 稀疏矩阵视图
提供了间谍函数来观察稀疏矩阵的非零元素的分布视图。 本节举例说明spy函数的使用。
[示例 2-25] 稀疏矩阵视图示例。 此示例使用间谍函数绘制网格圆顶的 60×60 邻接矩阵视图。 该矩阵还可用于表示碳 60 模型和足球。
>>B=巴基；
>>间谍(B)
得到的结果如图2-2所示。 该图显示了稀疏矩阵 B 的非零元素分布视图。
