在Oct文件中创建稀疏矩阵(GNU Octave(版本9.4.0))

下一个在Oct文件中使用稀疏矩阵前一个数组和稀疏类的差异上级Oct文件中的稀疏矩阵[目录][索引]

A.1.6.2在Oct文件中创建稀疏矩阵¶

创建稀疏矩阵有两种有用的策略。第一种是创建表示行索引、列索引和数据值的三个向量,然后根据这些向量创建矩阵。第二种选择是创建一个具有适当空间的稀疏矩阵,然后填充这些值。机器人技术有其优点和缺点。

下面是使用第一种技术创建小型稀疏矩阵的示例

int nz, nr, nc;
nz = 4, nr = 3, nc = 4;

ColumnVector ridx (nz);
ColumnVector cidx (nz);
ColumnVector data (nz);

ridx(0) = 1; cidx(0) = 1; data(0) = 1;
ridx(1) = 2; cidx(1) = 2; data(1) = 2;
ridx(2) = 2; cidx(2) = 4; data(2) = 3;
ridx(3) = 3; cidx(3) = 4; data(3) = 4;
SparseMatrix sm (data, ridx, cidx, nr, nc);

它创建了第节中给出的矩阵Storage of Sparse Matrices请注意,压缩矩阵格式在创建矩阵本身时不使用,而是在内部使用。

如稀疏矩阵一章中所述,稀疏矩阵的值以递增的列主序存储。尽管用户传递的数据不需要遵守这一要求,但对数据进行预排序将显著加快稀疏矩阵的创建。

这种用于创建稀疏矩阵的技术的缺点是存在数据的两个副本的时间很短。对于内存极为受限的问题,这可能不是创建稀疏矩阵的最佳技术。

另一种选择是首先创建一个具有所需数量的非零元素的稀疏矩阵,然后填充这些元素。示例代码:

int nz, nr, nc;
nz = 4, nr = 3, nc = 4;
SparseMatrix sm (nr, nc, nz);
sm(0,0) = 1; sm(0,1) = 2; sm(1,3) = 3; sm(2,3) = 4;

这将创建与以前相同的矩阵。同样,虽然不是严格必要的,但如果创建稀疏矩阵并按列主顺序添加元素,则速度会快得多。原因是,当元素插入到当前已知元素列表的末尾时,则不需要移动矩阵中的任何元素来插入新元素;只需要更新列索引。

关于这种创建稀疏矩阵的方法,还有几点需要注意。首先,可以创建一个稀疏矩阵,其中实际插入矩阵的元素较少。因此,

int nr, nc;
nr = 3, nc = 4;
SparseMatrix sm (nr, nc, 0);
sm(0,0) = 1; sm(0,1) = 2; sm(1,3) = 3; sm(2,3) = 4;

是完全有效的。然而,这是一个非常糟糕的想法,因为当每个新元素都被添加到稀疏矩阵中时,矩阵需要指定更多的空间和赋值内存。这是一个昂贵的操作,将大大减慢创建稀疏矩阵的速度。有可能创建具有多余存储的稀疏矩阵,因此nz在这个例子中大于4也是有效的。缺点是矩阵占用的内存比严格需要的要多。

当然,并不总是可以知道非零元素的数量来填充矩阵。因此,天冬氨酸矩阵的额外未使用存储可以在创建后使用maybe_compress作用除了解除赋值未使用的存储之外,maybe_compress也可以从矩阵中移除零元素。从矩阵中删除零元素是通过设置的参数来控制的maybe_compress要成为的函数true然而,移动零的成本很高,因为这意味着对元素进行重新排序。如果可能的话,用户最好先避免添加不必要的零。的使用示例maybe_compress是

int nz, nr, nc;
nz = 6, nr = 3, nc = 4;

SparseMatrix sm1 (nr, nc, nz);
sm1(0,0) = 1; sm1(0,1) = 2; sm1(1,3) = 3; sm1(2,3) = 4;
sm1.maybe_compress ();   // No zero elements were added

SparseMatrix sm2 (nr, nc, nz);
sm2(0,0) = 1; sm2(0,1) = 2; sm(0,2) = 0; sm(1,2) = 0;
sm1(1,3) = 3; sm1(2,3) = 4;
sm2.maybe_compress (true);  // Zero elements were added

的使用maybe_compress如果可能的话,应该避免函数,因为它会减缓矩阵的创建。

创建稀疏矩阵的第三种方法是直接使用数据未压缩的行格式。这种先进技术的一个例子可能是

octave_value arg;
...
int nz, nr, nc;
nz = 6, nr = 3, nc = 4;   // Assume we know the max # nz
SparseMatrix sm (nr, nc, nz);
Matrix m = arg.matrix_value ();

int ii = 0;
sm.cidx (0) = 0;
for (int j = 1; j < nc; j++)
  {
    for (int i = 0; i < nr; i++)
      {
        double tmp = m(i,j);
        if (tmp != 0.)
          {
            sm.data(ii) = tmp;
            sm.ridx(ii) = i;
            ii++;
          }
      }
    sm.cidx(j+1) = ii;
 }
sm.maybe_compress ();  // If don't know a priori the final # of nz.

这可能是创建稀疏矩阵的最有效的方法。

最后,有时可能会出现最初创建的存储量不足以完全存储稀疏矩阵的情况。因此,该方法change_capacity存在以重新赋值稀疏内存。然后将上述示例修改为

octave_value arg;
...
int nz, nr, nc;
nz = 6, nr = 3, nc = 4;   // Guess the number of nz elements
SparseMatrix sm (nr, nc, nz);
Matrix m = arg.matrix_value ();

int ii = 0;
sm.cidx (0) = 0;
for (int j = 1; j < nc; j++)
  {
    for (int i = 0; i < nr; i++)
      {
        double tmp = m(i,j);
        if (tmp != 0.)
          {
            if (ii == nz)
              {
                nz += 2;   // Add 2 more elements
                sm.change_capacity (nz);
              }
            sm.data(ii) = tmp;
            sm.ridx(ii) = i;
            ii++;
          }
      }
    sm.cidx(j+1) = ii;
 }
sm.maybe_compress ();  // If don't know a priori the final # of nz.

注意,增加和减少天冬氨酸矩阵中非零元素的数量都是昂贵的,因为这涉及到内存的重新赋值。此外,从于矩阵的某些部分,尽管不是全部,但同时作为新旧副本存在,因此需要额外的内存。因此,如果可能的话,避免改变容量。