乘以存储在一维数组算法中的上三角矩阵

Question

我正在用c++做上三角矩阵乘法。这些矩阵存储在一维数组中，而不是普通的二维数组中。该值逐行存储在数组中，底部的 0 将被忽略。我做了很多数学，试图找出一种模式，但我仍然想不出一种算法。假设我有 2 个矩阵，每个矩阵都是方形的，这两个值都存储在一维数组 A 和 B 中。我想将结果存储在数组 C 中。我认为最难的部分是添加不同数量的在 for 循环运行时更改元素。

谁能给我一些启发？

Answer 1

我的方法是从索引形式的矩阵乘法定义开始

(A B){i,j} = sum_k A{i,k} B{k, j}

现在您需要一种方法来将索引从 i,j 映射到您的一维数组

int toArrayIndex(tuple<int,int> ij); // return -1 if not in array
tuple<int,int> toMatrixIndex(int arrayIndex);

那么你的函数看起来就像

for(int arrayIndex=0; i<maxArrayIndex; ++arrayIndex ) {
  tuple<int,int> ij = toArrayIndex(arrayIndex);
  for(int k=0; k<matrixSize; ++k) {
    tuple<int,int> ik = make_tuple( std::get<0>(ij), k );
    tuple<int,int> kj = make_tuple( k, std::get<1>(ij) );
    int ik_index = toMatrixIndex(ik);
    int kj_index =  toMatrixIndex(kj);
    if(ik_index < 0 || kj_index < 0) continue;
    ab[arrayIndex] += a[ik_index] * b[kj_index];
  }
}

这不是最佳选择，因为可以减小内部 k 循环的大小。

Answer 2

假设整个矩阵的大小为 N x N。

第一行row = 0，有N个元素。
在第二行 row = 1 中，有 N - 1 个元素。

...

在 k-th 行中，row = k，有 N - k 个元素。

这是一个 ASCII 图：

|<-               N                    ->|

+--+--+--+       ---            +--+--+--+
|  |  |  |                      |  |  |  |  row = 0, N elements
+--+--+--+       ---            +--+--+--+
   |  |  |                      |  |  |  |  row = 1, N-1 elements
   +--+--+       ---            +--+--+--+
      |  |                      |  |  |  |  row = 2, N-2 elements
      +--+       ---            +--+--+--+


                 ---            +--+--+--+
                                |  |  |  |  row = k, N-k elements
                 ---            +--+--+--+


                                +--+--+--+
                                |  |  |  |  row = N-3, 3 elements
                                +--+--+--+
                                   |  |  |  row = N-2, 2 elements
                                   +--+--+
                                      |  |  row = N-1, 1 element
                                      +--+

一维数组中存储这样一个矩阵所需的元素个数是：

1 + 2 + ... + N = N*(N+1)/2

要访问矩阵的元素，我们需要将行索引和列索引映射到一维数组中的索引。

获取第一行的第 j 列（行索引 = 0，列索引 = j），

index = j

获取第二行第j列（行索引=1，列索引=j），

index = N + (j-1)

获取第三行第j列（行索引=2，列索引=j），

index = N + (N-1) + (j-2)

...

获取第i行的第j列（行索引=i，列索引=j），

index = N + (N-1) + ... + (N-(i-1)) + (j-i)
      = N + N     +  .. + N
          - ( 1   +        + (i-1) )  + j-i
      = N * i - (i-1)*i/2 + (j-i)

根据以上信息，您可以编写以下函数：

为上三角矩阵分配合适的内存量
给定行索引 (i) 和列索引 (j) 设置矩阵的值。
获取给定行索引 (i) 和列索引 (j) 的矩阵的值。

这应该足以将一个上三角矩阵与另一个上三角矩阵以及一个正则矩阵相乘。

乘以存储在一维数组算法中的上三角矩阵

Multiplying upper triangular matrix stored in 1D array alogrithm

c++

arrays

matrix

matrix-multiplication