Matrix multiplication

This is a discussion on Matrix multiplication within the C Programming forums, part of the General Programming Boards category; I'm trying to multiply 16 square matrices 8 x 8 recursively. Code: signed char matrices_64[16][8][8] = {}; signed char matrices_result[16][8][8] ...

  1. #1
    Registered User
    Join Date
    Sep 2011
    Posts
    78

    Matrix multiplication

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

    Code:
        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.

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Of course, you have to give i a value before you use it:
    Code:
    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.

  3. #3
    Registered User
    Join Date
    Sep 2011
    Posts
    78
    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.

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Now I am confused - and cicle is not a word.

  5. #5
    Registered User
    Join Date
    Sep 2011
    Posts
    78
    Sorry, i meant cycles or iterations.

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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?

  7. #7
    Registered User
    Join Date
    Sep 2011
    Posts
    78
    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)?

  8. #8
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,323
    (Logically) Is this what you are trying to do?
    Code:
    matrix a, b, c, d;
    
    a = mult( b, mult(c, mult(d, ...) ) );
    Where "mult" is a matrix multiplication function which returns a matrix?
    Fact - Beethoven wrote his first symphony in C

  9. #9
    Registered User
    Join Date
    Sep 2011
    Posts
    78
    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.
    Last edited by drew99; 11-07-2012 at 08:34 AM.

  10. #10
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    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:
    Code:
    new_matrix1 = matrix1 * matrix2 * matrix3 * ... * matrix16
    new_matrix2 = matrix2 * matrix3 * matrix4 * ... * matrix16
    ...
    new_matrix15 = matrix15 * matrix16
    new_matrix16 = matrix16
    Correct?

    Bye, Andreas

  11. #11
    Registered User
    Join Date
    Sep 2011
    Posts
    78
    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

  12. #12
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    Quote Originally Posted by drew99 View Post
    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

  13. #13
    Registered User
    Join Date
    Oct 2011
    Posts
    826
    Let's start from scratch, please.

    The nave algorithm for multiplying an n-row, k-column matrix A and a k-row, m-column matrix B is
    Code:
    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 nave algorithm for larger matrices. In other words, the nave approach is quite acceptable for this.

    Given 16 eight-by-eight matrices M1 to M16, their product is
    Code:
    M1  M2  M3  ...  M[sub]15[sub]  M16
    = (((((((((((((((M1  M2)  M3)  ...  M15)  M16
    Or, in pseudocode:
    Code:
    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
    Code:
    struct matrix8x8 {
        double  element[8][8];
    };
    you then only need
    Code:
    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
    Code:
    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.

  14. #14
    Registered User
    Join Date
    Sep 2011
    Posts
    78
    Thank you for you idea.
    I'll elaborate your code.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 6
    Last Post: 05-14-2011, 09:28 AM
  2. Matrix multiplication!!
    By Fatima Rizwan in forum C++ Programming
    Replies: 4
    Last Post: 10-18-2009, 04:09 PM
  3. Matrix multiplication???
    By sass208 in forum C Programming
    Replies: 2
    Last Post: 12-09-2006, 12:47 PM
  4. multiplication matrix
    By tmoney$ in forum C Programming
    Replies: 1
    Last Post: 05-13-2003, 02:06 PM
  5. matrix multiplication
    By fyodor in forum C Programming
    Replies: 2
    Last Post: 05-27-2002, 07:28 PM

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