hi,i'm triyng to modify the code write in that post:
http://cboard.cprogramming.com/c-programming/118820-adding-sparse-matrices.html
i want to implements also, the product between A and B.
please, can anyone suggest me how to implement a function to multiply the two matices?
thank's a lot
Sort the left-side matrix nodes by row and column, so that entries on the same row are consecutive in the list. Sort the right-side matrix so that all entries in the same column are consecutive in memory, with those sets in increasing column number. Find the maximum row number on the left-side matrix, and the maximum column number on the right side matrix, and initialize a 2D array of results of that many rows and columns to zeros. (You can afterwards pick the nonzero elements into a sparse result matrix.)
I do believe that the actual product-and-sum loop is as follows, but I haven't verified it by writing the actual code:
Your outer loop is over the rows in the left matrix. You initialize a pointer to the first nonzero element on that row in the left matrix. The inner loop loops over the entire right matrix, from beginning to the end. Whenever the element in the right matrix changes to a new row, you reset the left matrix pointer back to the beginning of the row (the current row in the left matrix). You skip the nodes in the left matrix with column less than the row in the current node in the right matrix. When they match, you add their product to the result matrix (row from left matrix node, column from right matrix node). Be careful to not run to the next row in the left matrix node.
How does this work? Let's look at a 3×4 and 4×5 matrices:
The result matrix is 3×5, and the elements Rrc are:Code:0 A 0 0 a 0 0 0 0 B 0 C D × 0 b c 0 d 0 E F 0 e 0 f 0 0 0 g h 0 0
R11 = 0·a + A·0 + 0·e + 0·0 = 0and so on.
R12 = 0·0 + A·b + 0·0 + 0·g = A·b
:
R21 = B·a + 0·0 + C·e + D·0 = B·a + C·e
R22 = B·0 + 0·b + C·0 + D·g
:
If we do one full pass over the right matrix, with a pointer in the left matrix initially starting, and restarting whenever the column changes in the right matrix, to the beginning of the top row in the left matrix, we can compute the entire top row of the result at once.
(Hey, I guess you could get away with just one full row as a buffer, if you pack it into sparse nodes and clear between left matrix rows.)
The actual multiplications and additions to the result matrix (which I am assumed is initialized to zeros) would then be, for the top row in the left matrix, and the full matrix on the right, as follows:
R12 += A·b
R13 += A·c
R15 += A·d
For the second row in the left matrix, and the full matrix on the right, the additions are
R21 += B·a
R21 += C·e
R22 += D·g
R23 += C·f
R24 += D·h
Hmm. Yes, I do believe this should work.
Sorry i'm new in c, have you got an example of implementati in of this function ? Thank's a lot
No, as I said, I haven't written the code.
Even if I did, I don't think it would be of much use to you. For efficiency reasons, I would use something like the following structures to speed up the processing (as the cache behaviour will likely be the limiting factor in real world cases):
One struct right_matrix and its struct right_matrix_col will be constructed for the right-side matrix for the duration of the multiplication.Code:struct right_matrix_column { size_t count; /* Number of nonzero elements in this column */ unsigned int *row; /* row[count]: row numbers of elements */ double *value; /* value[count]: values of elements */ }; struct right_matrix { size_t cols; /* Number of columns in the matrix */ struct right_matrix_col **column; /* Array of [cols] pointers */ }; struct left_matrix_row { size_t max; /* Number of elements allocated */ size_t count; /* Number of elements in this row */ unsigned int *col; /* col[count]: column numbers of elements */ double *value; /* value[count]: values of elements */ };
The struct left_matrix_row is built for one left matrix row at a time.
The row/column numbers are in a packed array, because most of the work is scanning for matching pairs in one col and one row array.
It does mean a rather large amount of memory used for such a simple operation, but it ensures compact and linear scanning in memory, and therefore should really help with the cache behaviour/memory bandwidth issues.
The multiplication function can even have a set of flags, indicating whether the source matrices have elements sorted by rows and/or columns or not.
What I am wondering, is whether this approach would work well for dense matrices, too. For those, chunking (calculating rectangular submatrices) is used, but analysing the cache behaviour for variously sized matrices is .. hard; you end up making too many simplifications or assumptions. Real world tests tend to give better insight.
Originally Posted by Nominal Animal
i solve with writing this function but im not sure tha works, can anyone help me what was wrong?
Code:int * get_row_vector(element *matrix[],int index){ int row_vector[3]; int i=0; element * tmp = matrix[index]; while ( tmp->next != NULL){ row_vector[i] = tmp->value; i++; tmp = tmp->next; } return row_vector; } int * get_col_vector(element * matrix[],int index){ int col_vector[3]; int i; for (i=0;i<3;i++){ element * tmp = matrix[i]; while (tmp->next != NULL){ if (tmp->column == index){ col_vector[i]= tmp->value; } tmp = tmp->next; } } return col_vector; } int vector_product(int row_vector[], int col_vector[]){ int sum; int i; for(i=0;i<3;i++){ sum += row_vector[i] * col_vector[i] ; } return sum; } /* product A X B*/ void product(element *a[],element *b[],element *product[]){ int res; int i; int j; for(i=0;i<3; i++){ for ( j=0;j<3;j++){ res = vector_product( get_row_vector(a,i), get_col_vector(a,j)); Insert(product, i, j, res); } } Printout(product); }
You should let your compiler help you find issues by compiling with (all) warnings enabled, and deal with every warning. Only add new code when it compiles (and works thus far) without errors, so you can concentrate on that added bit of code.
No, you cannot return a pointer to the local array, because the local array vanishes when the function returns. You need to allocate the memory dynamically. Also, you're very confident that the matrix only has three rows and three columns. I wouldn't be; sparse matrices are usually much, much larger.
If speed or efficiency is not an issue, then the following approach should work:
Of course, the above is slower than a pickled carrot in tar, and I didn't even bother to check if it compiles.Code:#include <stdlib.h> #include <stdio.h> struct node { struct node *next; int row; int col; double value; }; /* Create a new matrix element. */ struct node *matrix_new(const int row, const int col, const double val, struct node *const next) { struct node *element; element = malloc(sizeof *element); if (!element) { fflush(stdout); fprintf(stderr, "new_node(): Out of memory.\n"); exit(EXIT_FAILURE); } element->next = next; element->row = row; element->col = col; element->value = value; return element; } /* Return the value of a matrix element. */ double matrix_element(const struct node *matrix, const int row, const int col, const double not_found) { while (matrix) if (matrix->row == row && matrix->col == col) return matrix->value; else matrix = matrix->next; return not_found; } /* Find the size of a matrix. * Returns 0 if valid size, nonzero if error. */ int matrix_size(const struct node *matrix, int *const maxrowto, int *const maxcolto) { int maxrow = -1; int maxcol = -1; while (matrix) { if (maxrow < matrix->row) maxrow = matrix->row; if (maxcol < matrix->col) maxcol = matrix->col; matrix = matrix->next; } if (maxrow < 0 || maxcol < 0) return 1; if (maxrowto) *maxrowto = maxrow; if (maxcolto) *maxcolto = maxcol; return 0; } struct node *matrix_multiply(const struct node *const left, const struct node *const right) { struct node *result = NULL; int left_maxrow, left_maxcol; int right_maxrow, right_maxcol; int maxrow, maxcol, maxn; int row, col, n; /* Find out matrix sizes. */ if (matrix_size(left, &left_maxrow, &left_maxcol) || matrix_size(right, &right_maxrow, &right_maxcol)) return NULL; maxrow = left_maxrow; maxcol = right_maxcol; /* Technically, the matrices should have * left_maxcol == right_maxrow * but since these are sparse, they may have * zero rows or columns as necessary, * so we just use the larger one. */ maxn = left_maxcol; if (maxn < right_maxrow) maxn = right_maxrow; /* We do the loops in inverse order, so that when we * prepend new elements to the list, the final matrix * will have them in the correct order. */ for (row = maxrow; row >= 0; row--) { for (col = maxcol; col >= 0; col--) { double sum = 0.0; for (n = maxn; n >= 0; n--) { double left_value, right_value; left_value = matrix_element(left, row, n, 0.0); if (left_value == 0.0) continue; right_value = matrix_element(right, n, col, 0.0); if (right_value == 0.0) continue; sum += left_value * right_value; } if (sum != 0.0) result = matrix_new(row, col, sum, result); } } /* Note: result == NULL, if the matrix is a zero matrix. * If you want, you can avoid that by adding * if (!result) * result = matrix_new(maxrow, maxcol, 0.0); */ return result; }
