Pointers, memory allocation: index of rows in Matrix Multiplication (C Programming)

Question

I'm having trouble understanding what an "index of rows of a" in the problem is referring to... can you give me an example of that? Why does

sum = sum + a[(row * a_cols) + k] * b[k * b_cols + col]?

Thank you!

double dotProduct(double a[], const unsigned a_rows, const unsigned a_cols,
                  /* a is a matrix with a_rows rows and a_cols columns */
                  double b[], const unsigned b_cols,
                  /* b is also a matrix.  It has a_cols rows and b_cols columns */
                  unsigned row, // an **index of a row of a**
                  unsigned col) // an index of a column of b
{
    int k; // loop variable

    double sum = 0.0; // the result of the dot product is stored here
    k = 0;
    while (k < a_cols) { // recall: a_cols == b_rows
            /* we need to multiply a[row, k] and b[k, col] and add that to sum */
            sum = sum + a[(row * a_cols) + k] * b[k * b_cols + col];
            /* recall a[i,j] is stored at a[(i * a_cols) + j]
                  and b[i,j] is stored at b[(i * b_cols) + j] */
            k += 1;
    }

    return sum;
}

Answer 1

Edit my bad, forget my first answer, I misunderstood the question...

Answer: The 5th argument to the dotProduct() method, named row is given as an index of rows of a.
This means that it is a 0 to (a__rows -1) value to be used to designate one particular row of the "matrix" a. (Effectively it could be a 1 to a__rows value instead. This is merely a matter of convention; math folks tends to like the "1-based" indexes, programmers prefer the 0-Based values. See Adam Liss' funny comment on this topic in remarks)
Since the matrix a is implemented in a one dimensional array, you need to use simple arithmetic to address the all the cells of a that are on the row indexed by row.

The "formula" is to visit all these cells in order is

for (int c = 0; c < a_cols; c++)
{
    A_Cell_Value = a[row * a_cols + c];
}

A similar formula is to be applied to scan the cells of a given column of b. however in that case, col, the index, will be used as an offset and b_cols as a factor. Specifically,

// not an error this is a_cols which also corresponds to the number of rows of
// matrix b, so that these matrices would be compatible for multiplication    
for (int r = 0; r < a_cols; r++) 
{
     B_Cell_Value = b[(r * b_cols) + col];
}

I think the above provides you the necessary understanding to iterate trough the cells of a row or a column. I let you put this all together in your application.

A few hints: - do some parameter value checking. This will avoid getting out of bound errors on these matrices. - a good way to introduce abstraction in your program would be to introduce a function which returns the value of a single cell of a matrix, from the matrix dimension and two row and column index. For example:

// returns the matrix's cell value at RowIdx and colIdx
double GetCell(double matrix[], int nbOfRow, int nbOfColumns,
               int rowIdx, int colIdx)
{
   if (rowIdx < 0 || rowIdx >= nbOfRows ||
       colIdx <0 || colIdx >= nbOfColumns
      )
   {
      printf("bad arguments in GetCell()\n");
      return 0;   // print
    }
    return matrix[rowIdx * nbOfColumns + colIdx];
}

In this fashion you would abstract (=hide the details about) these ugly matrices stored linearly, and be able to address them in terms of row and column index at the level of the dot product formula.
In other words, the GetCell() function worries of finding the right cell, based on its knowledge of the structure of the matrix implementation. It doesn't have to know what this cell value is going to be used for. The DotProduct calculation logic worries about which series of cells of A to multiply with which series of cell of B, addressing each of these cells "naturally" in term of their row/column (i/j etc.) "coordonates" and it doesn't need to know how the data is effectively stored in the matrix implementation.

Answer 2

"row" is the row in the matrix a, which is done as a single-index array here. If you think of a as a matrix with a_cols columns and a_rows rows, then the element of a at row r and column c is a[r*a_cols+c]. Here k is the column index in matrix a and the row index in matrix b.

There is a comment right underneath the sum = sum line which explains this already.

Answer 3

One tricky part not so far explained by others is that if you have a vector (linear array) of, say, 24 elements, you can treat it as a two dimensional array - in fact, as a number of different two dimensional arrays.

As a 2 x 12 array:

 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11,
12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23,

As a 3 x 8 array:

 0,  1,  2,  3,  4,  5,  6,  7,
 8,  9, 10, 11, 12, 13, 14, 15,
16, 17, 18, 19, 20, 21, 22, 23,

As a 4 x 6 array:

 0,  1,  2,  3,  4,  5,
 6,  7,  8,  9, 10, 11,
12, 13, 14, 15, 16, 17,
18, 19, 20, 21, 22, 23,

As a 6 x 4 array:

 0,  1,  2,  3,
 4,  5,  6,  7,
 8,  9, 10, 11,
12, 13, 14, 15,
16, 17, 18, 19,
20, 21, 22, 23,

As an 8 x 3 array:

 0,  1,  2,
 3,  4,  5,
 6,  7,  8,
 9, 10, 11,
12, 13, 14,
15, 16, 17,
18, 19, 20,
21, 22, 23,

Or as a 12 x 2 array:

 0,  1,
 2,  3,
 4,  5,
 6,  7,
 8,  9,
10, 11,
12, 13,
14, 15,
16, 17,
18, 19,
20, 21,
22, 23,

The indexing expression a[row * a_cols + col] means you can identify the item in the vector corresponding to the 'row, col' value by multiplying the row number by the number of columns in the matrix (indexing rows from 0), and then adding the column number (also indexed from 0). Other languages, such as Fortran, index from 1 instead of zero, so you see faintly similar computations using 'row-1, col-1'.

The conditions that the matrix A has a_cols columns and a_rows rows and matrix B has a_cols rows and b_cols columns means that you can multiply the matrices A x B, of course.