2

两个 typedef

std::vector<double> Matrix;
std::vector<Matrix> MatrixBlocks;

Matrix 由一维向量表示，MatrixBlocks 表示矩阵的向量。

问题是，鉴于矩阵块包含来自具有特定排序的较大矩阵的子矩阵，我需要用矩阵块重建大矩阵。所以例如

假设大矩阵（存储为std::vector<double>）具有以下数据：

 1  2  3  4 
 5  6  7  8
 9  10 11 12
 13 14 15 16

并且下面包含上述矩阵的子矩阵的 MatrixBlocks 具有以下数据：

索引 0：

1 2
5 6

索引 1：

3 4 
7 8

索引 2：

9 10 
13 14

索引 3：

11 12 
15 16

因此，鉴于 MatrixBlock 我需要重建 double 的原始向量；一维矩阵。有人有任何通用解决方案吗？

你可以假设如果大矩阵总是一个正方形大小的矩阵。

编辑：

对于 NxN 矩阵，它被分解为 K mxm 矩阵，其中 N 可被 m 整除，您可以假设 MatrixBlock 的排序如下：

索引 0：将包含从 [0,0] 到 (m,m) 的矩阵

索引 1：将包含从 [0,m] 到 (m, m + m) 的矩阵

索引 2：将包含从 [0,m+m] 到 (m, m + m + m) 的矩阵

...

直到最后一个索引包含从 [m*i - m,m*i - m] 到 [m,m] 的矩阵

例如，如果主矩阵是 512x512

1 2 3 4 ... 512
513 ...   1014
 ...

261632(512*512-512) ... 262144(512*512)

我们想拆分 512x512 矩阵 int 256 32x32 块，32 由用户选择，然后 MatrixBlock 将包含类似

index 0: 1 2 3 ... 32 513 ... 513 + 32 //..直到前 32 行的列长度为 32

索引 1: 33 34 ... (33+32) (513+32+1) ... (513 + 32 + 1 + 32) //... 同上

所以你可以看到它从索引（0,0）开始，从（0,0）到（31,31）提取第一个32x32元素；那是索引0。然后对于索引1，起始位置是（0,32），它从矩形（0,32），（0,63），（31,32），（31,63）中提取数据

希望这很清楚。因此，对于上面的 4x4 矩阵观察到的模式基本相同，对于任何矩阵大小都将是相同的模式，唯一的区别是主矩阵的大小并不总是 4x4，我们将其分割成的块大小也不总是 2x2。

4

2 回答 2

2

这基本上归结为正确索引。

#include <cmath>
#include <iostream>
#include <vector>

int main()
{
  std::vector<double> v(16);
  std::vector<std::vector<double> > m;
  std::vector<double> m1 {1,2,5,6};
  m.push_back(m1);
  std::vector<double> m2 {3,4,7,8};
  m.push_back(m2);
  std::vector<double> m3 {9,10,13,14};
  m.push_back(m3);
  std::vector<double> m4 {11,12,15,16};
  m.push_back(m4);

  size_t idx = 0;
  for (size_t big_row = 0; big_row < std::sqrt(m.size()); ++big_row)
  for (size_t small_row = 0; small_row < std::sqrt(m1.size()); ++small_row)
  for (size_t big_col = 0; big_col < std::sqrt(m.size()); ++big_col)
  for (size_t small_col = 0; small_col < std::sqrt(m1.size()); ++small_col)
  {
    v[idx] = m[big_col + std::sqrt(m.size()) * big_row][small_col + std::sqrt(m1.size()) * small_row];
    ++idx;
  }

  for (unsigned i = 0; i < 16; ++i)
    std::cout << v[i] << std::endl;
}

输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
于 2012-04-12T23:58:39.203 回答
1

假设原矩阵为大NxN，每个子矩阵为nxn。那么边的子矩阵的数量是（N / n）；让我们称之为k。

我们可以将大矩阵想象成一个长的、n*k*n*k 长度的列表。

我们可以将大矩阵索引映射到子矩阵编号和索引，反之亦然。前向映射看起来非常复杂，我只是先写出我想要的子矩阵索引作为一个系列，然后编写一个函数来生成该系列（以及时间测试的试错法，当然）。

一些演示第一种方法的代码（请原谅灰尘）：

#include <iostream>
#include <vector>

int main() {
  // Initialize the Vector and Set up the Matrices
  std::vector<double> v(36);
  std::vector<std::vector<double> > m;
  std::vector<double> m1 {1,2,7,8};
  m.push_back(m1);
  std::vector<double> m2 {3,4,9,10};
  m.push_back(m2);
  std::vector<double> m3 {5,6,11,12};
  m.push_back(m3);
  std::vector<double> m4 {13,14,19,20};
  m.push_back(m4);
  std::vector<double> m5 {15,16,21,22};
  m.push_back(m5);
  std::vector<double> m6 {17,18,23,24};
  m.push_back(m6);
  std::vector<double> m7 {25,26,31,32};
  m.push_back(m7);
  std::vector<double> m8 {27,28,33,34};
  m.push_back(m8);
  std::vector<double> m9 {29,30,35,36};
  m.push_back(m9);

  // These variables (see explanation above) take on these values for this example
  unsigned N = 6;
  unsigned n = 2;
  unsigned k = N/n;

  // Constructing the Big Matrix    
  for (unsigned i = 0; i < N*N; ++i) {
    int a = (i / (n * k * n)) * k + ((i / n) % k);
    int b = (i % (n * k * n)) % n + ((i % (n * k * n)) / (n * k) * n);
    v[i] = m[a][b];
    std::cout << a << "\t" << b << "\t" << v[i] << std::endl;
  }
}

我们还可以通过遍历子矩阵列表并将每个索引映射回大矩阵来使用反向映射。我还没有编码，但你明白了。

无论哪种方式，算法在所有情况下都应该花费 O(N^2) 时间（N 是大矩阵的一侧）。如果你让 N 是矩阵的大小，那么它就是线性时间。

这对您的应用程序是否足够有效？

于 2012-04-13T01:56:52.783 回答