CODEWITHSUNDEEP
c++arraysmatrixmatrix-multiplication
alsjinus
alsjinus

Reputation: 77

Multiplying upper triangular matrix stored in 1D array alogrithm

I am doing the upper triangular matrix multiplication in c++. Those matrices are stored in 1D array instead of normal 2D arrays. The value are stored inside the array from row to row and the 0's at the bottom part are ignored. I did a lot of mathematics, trying to find out a pattern, but I still cannot think of an algorithm. Suppose I have 2 matrices and each one is in the square shape and both of those values are stored in the 1D array A and B. And I want to store the results in an array C. I think The hardest part is adding varying number of changing elements as the for loop runs.

Anyone could give me some inspirations?

Upvotes: 0

Views: 3516

Answers (2)

R Sahu
R Sahu

Reputation: 206577

Let's say the full matrix is of size N x N.

In the first row, row = 0, there are N elements.
In the second row, row = 1, there are N - 1 elements.

...

In the k-th row, row = k, there are N - k elements.

Here's an ASCII diagram:

|<-               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
                                      +--+

The number of elements needed in the 1D array to store such a matrix is:

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

To access an element of the matrix, we need to map a row index and column index to an index in the 1D array.

To get the j-th column of the first row (row index = 0, column index = j),

index = j

To get the j-th column of the second row (row index = 1, column index = j),

index = N + (j-1)

To get the j-th column of the third row (row index = 2, column index = j),

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

...

To get the j-th column of the i-th row (row index = i, column index = 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)

With the above information, you can write functions that:

  1. Allocate the right amount of memory for the upper triangular matrix
  2. Set the value of the matrix given a row index (i) and column index (j).
  3. Get the value of the matrix given a row index (i) and column index (j).

That should be adequate to be able to multiply an upper triangular matrix with another upper triangular matrix as well as a regular matrix.

Upvotes: 3

Michael Anderson
Michael Anderson

Reputation: 73480

The way I'd approach this is by starting with the definition of matrix multiplication in index form

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

Now you need a way to map to and from indices into your 1D array from i,j

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

Then your function looks simply like

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];
  }
}

It's not optimal as the inner k loop can be reduced in size.

Upvotes: 0

Related Questions