列和行交换的最佳稀疏矩阵表示

Question

我正在寻找稀疏矩阵表示，允许有效的行和列交换。经典的表示(通过压缩行、压缩列或三元组)似乎只允许执行其中一种或另一种，而从不允许展位。有没有人知道一个好的数据结构？

--Edit--为了清楚起见，我希望能够交换行，比如交换行5和行7，还可以交换列，比如交换列6和列8。

Answer 1

您可能只想添加另一个间接层来处理效率不高的交换。例如，如果您有一个可以有效地交换行但不能交换列的稀疏表示，那么就有一个从真实列映射到有效列的数组。访问元素时，请使用数组查找适当的基础元素。

class SparseMatrix {
  public:
    Element& operator()(Index row,Index col)
    {
      return matrix(row,col_map[col]);
    }

    void swapRows(Index row1,Index row2)
    {
      matrix.swapRows(row1,row2);
    }

    void swapCols(Index col1,Index col2)
    {
      swap(col_map[col1],col_map[col2]);
    }

  private:
    FastRowSwapSparseMatrix matrix;
    vector<Index> col_map;
};

Answer 2

我的建议是

Eigen:线性代数运算的快速高效http://eigen.tuxfamily.org/

或

boost中的映射矩阵-->更灵活，但线性代数运算http://www.boost.org/doc/libs/1_39_0/libs/numeric/ublas/doc/matrix_sparse.htm速度较慢

对于您的情况，这两个库都允许您有效地操作行和列