2

2つのtypedef

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

マトリックスは1Dベクトルで表され、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の元のベクトルを再構築する必要があります。1Dマトリックス。誰かが一般的な解決策を手に入れましたか？

大きな行列が常に正方形サイズの行列である場合は、次のように想定できます。

編集：

Nがmで割り切れるKmxm行列に分解されるNxN行列の場合、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マトリックスを25632x32ブロックに分割したかったのですが、32はユーザーによって選択され、MatrixBlockには次のようなものが含まれます。

インデックス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要素を抽出することがわかります。次に、インデックス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 に答える