如何存储对称矩阵？

Question

哪种是在内存中存储对称矩阵的最佳方法？

在不降低结构速度和复杂性的情况下节省一半空间将是一件好事.这是一个与语言无关的问题,但如果你需要做一些假设,只要假设它是一个很好的旧的简单编程语言,如C或C++.

只要有一种方法可以保持简单,或者只是当矩阵本身非常大时,这似乎是有道理的,我是对的吗？

仅仅为了形式,我的意思是这个断言对于我想要存储的数据总是如此

matrix[x][y] == matrix[y][x]

Answer 1

这是存储对称矩阵的好方法,它只需要N(N + 1)/ 2个内存:

int fromMatrixToVector(int i, int j, int N)
{
   if (i <= j)
      return i * N - (i - 1) * i / 2 + j - i;
   else
      return j * N - (j - 1) * j / 2 + i - j;
}

对于一些三角矩阵

0 1 2 3
  4 5 6
    7 8
      9

1D表示(std::vector例如存储在)中如下所示:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

并且调用fromMatrixToVector(1,2,4)返回5,因此矩阵数据是vector [5] - > 5.

有关更多信息,请参阅http://www.codeguru.com/cpp/cpp/algorithms/general/article.php/c11211/TIP-Half-Size-Triangular-Matrix.htm

Answer 2

我发现许多高性能软件包只存储整个矩阵,但只读取上三角形或下三角形.然后,他们可能会在计算过程中使用额外的空间来存储临时数据.

但是,如果存储确实是一个问题,那么只需将n(n+1)/2构成上三角形的元素存储在一维数组中.如果这使得访问变得复杂,只需定义一组辅助函数即可.

在C中访问矩阵,matA您可以定义一个宏:

#define A(i,j, dim) ((i <= j)?matA[i*dim + j]:matA[j*dim + i])

那么你几乎可以正常访问你的阵列.