Matrix multiplication

[drew99]

I'm trying to multiply 16 square matrices 8 x 8 recursively.

    signed char matrices_64[16][8][8] = {};
    signed char matrices_result[16][8][8] = {};
    signed long long int tmp_matrix;


    for(BYTE M = 0; M < 16; M++)
    {
        for (BYTE x = 0; x < 8; x++)
        {
            for (BYTE y = 0; y < 8; y++)
            {
                tmp_matrix = matrices_64[M][x][i];
                for (BYTE m = 0; m < 16; m++)
                {
                    for (BYTE i = 0; i < 8; i++)
                    {
                        tmp_matrix *= matrices_64[(M + m + 1) % 16][i][y];
                    }
                    tmp_matrix %= 256;
                }
                matrices_result[M][x][y] = tmp_matrix;
            }
        }
    }

I'm not very sure about this code.

[Adak]

Of course, you have to give i a value before you use it:

tmp_matrix = matrices_64[M][x][i];

I don't see anything recursive about this code. Looks very iterative to me.

Try working it up - recursively multiply just two numbers, then a small 1D matrix, then 2 matrices, and be SURE they're working right. After that, jump up the number of matrices to 16 or whatever you want. You need to slip into that recursive way of thinking, imo.

[drew99]

I'm very sorry for my errors.

tmp_matrix = matrices_64[M][x]yi]; not tmp_matrix = matrices_64[M][x][i];

I don't need a recursively function, I meant that I tried not to indicate all 32 matrix and replace that long code with a cicle.

[Adak]

Now I am confused - and cicle is not a word.

[drew99]

Sorry, i meant cycles or iterations.

[Adak]

Ok, I was expecting matrix result value = matrix1 value * matrix2 value, and using integers, doubles or floats.

Why multiply chars?

Are you going to be doing REALLY BIG numbers, so you're using char arrays to hold every digit, maybe?

[drew99]

I don't need the result is the righ product of the matrices, but I need to determinate each element of the final matrix in this way, so I have to use the % operand, in order to be able to save the result in a char matrix.
I have to say I started from the standard code for matrix multiplication, but, expanding the multiplication to all the matrix for all the matrix, I made some mistakes.
Do you have any suggestions about how to correct the code(it produces only 0)?

[Click_here]

(Logically) Is this what you are trying to do?

matrix a, b, c, d;

a = mult( b, mult(c, mult(d, ...) ) );

Where "mult" is a matrix multiplication function which returns a matrix?

[drew99]

Yes, something similar to what you said.
I have 16 matrix and I have to multiply each one for each one.
For example, I have to multiply the forst matrix for the second one, then multiply the result for the third one and so on, then I have to multiply the second matrix for the third one, then multiply the result for the fourth one and so on.
I hope I explained the problem clearly.

[AndiPersti]

I guess you have heard of "abstraction" (in regard to programming/computer science) before, haven't you?

Instead of five nested for-loops, start with writing a function for multiplying two matrices. Then the rest should be rather easy.

As I understand it, you want this:

new_matrix1 = matrix1 * matrix2 * matrix3 * ... * matrix16
new_matrix2 = matrix2 * matrix3 * matrix4 * ... * matrix16
...
new_matrix15 = matrix15 * matrix16
new_matrix16 = matrix16

Correct?

Bye, Andreas

[drew99]

I knew the starting algorith used to multiply two matrices, but I can't transform it in order to multiply each matrix for each matrix.

new_matrix1 = matrix1 * matrix2 * matrix3 * ... * matrix16
new_matrix15 = matrix16 * matrix1 * matrix1 * ... * matrix15
new_matrix16 = matrix1 * matrix2 * matrix3 * ... * matrix15

[AndiPersti]

new_matrix1 = matrix1 * matrix2 * matrix3 * ... * matrix16
new_matrix15 = matrix16 * matrix1 * matrix1 * ... * matrix15
new_matrix16 = matrix1 * matrix2 * matrix3 * ... * matrix15

We are unable to help you if you can't provide clear and unambiguous descriptions. Why is "matrix1" used twice for calculating "new_matrix15"?

I can't see a pattern in the examples you have given.

Bye, Andreas

[Nominal Animal]

Let's start from scratch, please.

The naïve algorithm for multiplying an n-row, k-column matrix A and a k-row, m-column matrix B is

Cr,c = ∑i=1..k Ar,i Bi,c

and the result is an n-row, m-column matrix C.

For details and background, please look at the Wikipedia article on matrix multiplication. The Strassen algorithm is much more complicated, but only beats the naïve algorithm for larger matrices. In other words, the naïve approach is quite acceptable for this.

Given 16 eight-by-eight matrices M₁ to M₁₆, their product is

M1 × M2 × M3 × ... × M[sub]15[sub] × M16
= (((((((((((((((M1 × M2) × M3) × ... × M15) × M16

Or, in pseudocode:

T1 and T2 are temporary matrices, R is the result matrix

T1 = M1 × M2
T2 = T1 × M3
T1 = T2 × M4
T2 = T1 × M5
T1 = T2 × M6
T2 = T1 × M7
T1 = T2 × M8
T2 = T1 × M9
T1 = T2 × M10
T2 = T1 × M11
T1 = T2 × M12
T2 = T1 × M13
T1 = T2 × M14
T2 = T1 × M15
R  = T2 × M16

So, you only need a function which multiplies two matrices.

Assume you have

struct matrix8x8 {
    double  element[8][8];
};

you then only need

void multiply8x8(struct matrix8x8 *const result,
                 const struct matrix8x8 *const left,
                 const struct matrix8x8 *const right)
{
    double s;
    int r, c, i;

    for (r = 0; r < 8; r++) {
        for (c = 0; c < 8; c++) {
            s = left->element[r][0] * right->element[0][c];
            for (i = 1; i < 8; i++)
                s += left->element[r][i] * right->element[i][c];
            result->element[r][c] = s;
        }
    }
}

To implement the pseudocode above for any number of 8x8 matrices, you could use

void product8x8(struct matrix8x8 *const result,
                const struct matrix8x8 *const *const matrixarray,
                const int count)
{
    struct matrix8x8  temp1, temp2;
    int  n;

    if (count < 1)
        return;

    if (count == 1) {
        *result = *matrixarray[0];
        return;
    } else
    if (count == 2) {
        multiply8x8(result, matrixarray[0], matrixarray[1]);
        return;
    }

    multiply8x8(temp1, matrixarray[0], matrixarray[1]);

    for (n = 2; n + 2 < count; n += 2) {
        multiply8x8(temp2, temp1, matrixarray[n]);
        multiply8x8(temp1, temp2, matrixarray[n + 1]);
    }

    if (count & 1) {
        multiply8x8(result, temp1, matrixarray[count - 1]);
    } else {
        multiply8x8(temp2, temp1, matrixarray[count - 2]);
        multiply8x8(result, temp2, matrixarray[count - 1]);
    }

    return;
}

The loop does all even numbered multiplications except for the last one, and all odd numbered multiplications except the first and last. (I know that sounds odd, but if you look at the pseudocode, that's just the way it repeats.)

The final if statement takes care of the final multiplication (if odd number of matrices) or final two multiplications (if even number of matrices).

If the matrices were of different sizes, then it would be useful to pick the multiplication order in such a fashion to keep the total number of multiplications as small as necessary -- but I guess that is a subject for some other thread.

[drew99]

Thank you for you idea.
I'll elaborate your code.