带你了解两种线性规划的方法：稀疏矩阵存储和预处理

关注

发布于: 23 小时前

摘要：本文为大家带来线性规划的稀疏矩阵存储和数据预处理。

本文分享自华为云社区《线性规划--稀疏矩阵》，原文作者：Bale10 。

随着 AI 时代的发展，线性规划问题的规模越来越大是一种必然。面对大规模的线性规划问题，如何存储数据，使得存储空间节省以避免资源的浪费，并且使得数据的查询、修改和增删方便快捷，是一个急需解决的问题。本文为大家带来线性规划的稀疏矩阵存储和数据预处理。

稀疏矩阵

LP 的规模通常是由约束矩阵 A 的规模决定的，矩阵的元素通常用 8 个字节的 double 型储存，假设矩阵有 m 行，n 列，则直接储存 A 需要 8mn 字节。如果 A 有 10000 行，20000 列（不是特别大规模的），那么需要 1.6G 内存储存 A，一方面内存要求高，另一方面对矩阵 A 的操作困难。大规模 LP 通常含有大量的零元，非零元占比非常小，这个性质称为稀疏性，即 A 为稀疏矩阵。

稀疏矩阵储存

稀疏矩阵的数据结构设计应该考虑下面三个因素：

1. 仅存非零元，一个好的稀疏矩阵数据结构应该仅存 A 的非零元，而不存大量的零元。这样做的优点有三。首先，节省内存，使得大型稀疏矩阵能存在内存中。其次，若仅存非零元内存也放不下，则必须借助于外存，而从外存存取数据的速度一般比从内存存取数据慢得多，因此，在使用外存的情况我们也希望仅存非零元。第三，涉及零元的操作可以不执行，从而显著节约计算时间。

2. 非零元的产生--填入元，一个稀疏矩阵，在高斯消去(或 LU 分解）过程中，原来的零元可能要变成非零元。这种在消去过程中，由零元变成的非零元，叫做填入元；在整个消去过程中产生的填入元的个数，叫做填入量。如果一个十分稀疏的矩阵，经过上述消去运算后产生大量的填入元，则稀疏性就会消失，因此，保持矩阵的稀疏性是利用其稀疏性的前提。如何设法使消去过程中产生尽可能少的填入元是算法需要考虑的。稀疏矩阵是一个动态的数据结构，特别是经常需要插入非零元或删去非零元。因此，一个好的稀疏矩阵数据结构必须便于插入或删除。

3. 稀疏矩阵的数据结构和消去算法紧密相关，在考虑稀疏矩阵的数据结构时，必须同时考虑到消去算法，数据结构必须尽可能便于其算法的实现。

线性表

最简单的稀疏矩阵存储方案是线性表。为了具体起见，我们以下列稀疏矩阵 A_5 为例：

将非零元按列存放到数组 CE 中：

CE 中相应非零元的行号记录在数组 IROW 中：

为了给出每个非零元在的列号，引入一个指针数组 ICFR，ICFR(j)表示第 j 列第一个非零元在 CE 中的位置。

ICFR 的长度为 N+1，ICFR(N+1)表示最后一个元存放在第 $N$列末元位置加 1 的位置上，这是为了便于计算最后一列非零元个数而引入的。这种存储方案所需要存储量为 2NZ+N+1。它的优点是存储量小，结构简单，单缺点是不便于插入和删除，若要插入一个非零元，位于它下面的非零元必须向下移动一个位置，这是非常浪费时间的。

在程序中为了允许插入非零元，通常要说明一个较大的数组。上述是将 A 按列存放，当然也可以按行存放。经常的做法是先将 A 进行 LU 分解，然后将下三角形矩阵 L 按列存放，上三角矩阵 U 按行存放。