Matrix multiplication using 1Dimensional arrays


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 4 of 4

Thread: Matrix multiplication using 1Dimensional arrays

  1. #1
    Join Date
    Mar 2005
    Posts
    1

    Question Matrix multiplication using 1Dimensional arrays

    hi, I need to multiply two NxN matrices without using 2Dimentional Arrays.... any Ideas of how to do it with only 1D arrays.? (i.e. A 2x2 matrix should look like this: M1[4]={1,1,0,1} ). Thanks for any help.

  2. #2
    Join Date
    Dec 2003
    Posts
    3,366
    Well you can hack on it... the malloc/free thing should probably use some sort of allocated (passed in, or whatever) swap space for speed, you can do calloc instead to zero the memory, but this covers the technique pretty well even if its sloppy C code.

    double*multiply(double *a,int ar,int ac,double*b,int br,int bc)
    /*ar = a's rows, ac = a's cols, etc*/
    {/*returns null for bad dimensions and ab for good ones.*/

    double *product;
    int i,j,k,dx;

    if(ac != br)/*then its not valid.*/
    return(NULL);

    product = (double*)malloc(sizeof(double)*ar*bc);
    memset(product,0,sizeof(double)*ar*bc);
    /*set up zeros to use += later.*/
    dx = 0;/*index into 1d array...*/
    for(i = 0; i<ar;i++)
    for(j = 0; j<bc;j++)
    {
    for(k = 0; k<ac;k++)
    {
    product[dx]+= a[i*ac+k]*b[k*bc+j];
    }
    dx++;
    }
    return(product);
    }

  3. #3
    Join Date
    Dec 2003
    Posts
    3,366
    theoretically, you can do a multiply in N^2.XX instead of the N^3 but the method is messy, and so bloated (its recursive, for one thing) that you have to have a pretty big matrix to justify it, as in thousands of entries.

    You can also toss out whole (value * row or value * col depending on how you look at it) if you find a zero, but you will have to re-order the loops to do that. All in all this is just the brute force method.

    Note that an x,y pair for a 2d array is really
    desired_row * Max_cols + desired_col (in c, because memory is rows of columns)
    -- thats what the index magic is doing.
    Last edited by jonnin; 03-30-2005 at 08:22 PM.

  4. #4
    Join Date
    Dec 2003
    Posts
    3,366
    That was so bad I decided to fix it myself. I had never bothered to fix it because I don't use it much.

    double *multiply(const double *a, const int ar, const int ac, const double *b, const int br, const int bc)
    {
    /*skips inner loop if the constant is zero
    returns null for bad dimensions*/

    static double * product = swap_space; /*provide a place for the result*/
    static int bcols;
    static int brows;
    register int arows;

    memset(product,0,ar*bc*sizeof(double));
    if(ac != br) return 0;
    for(brows = 0; brows < br; brows++)
    {
    for(bcols = 0; bcols < bc; bcols++)
    {
    register double con;
    if(con = b[brows*bc+bcols]); /*if con != 0.0*/
    {
    for(arows = 0; arows < ar; arows++)
    {
    product[ arows*bc+bcols] += a[arows*ac + brows] * con;
    }
    }
    }
    }
    return product;
    }

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center