Effectively store a triangular matrix

Question

I need to efficiently store the lower triangular matrix without storing all zeros in memory, so I thought of it this way: first I allocate memory for each row, then for each row I allocate + 1 byte, so I never need to worry about zero but something is wrong with the first distribution. What am I doing wrong? This is my code, and the compiler exits the program on line 8, immediately after reading the matrix dimension.

#include <stdio.h> #include <stdlib.h> int main () { int i, j, **mat1, dim; scanf("%d",&dim); *mat1 = (int**)calloc(dim, sizeof(int*)); for(i = 0; i<dim; i++) mat1[i] = (int*)calloc(i+1, sizeof(int)); for(i = 0; i < dim; i++) for(j = 0; j < i+1; j++) scanf("%d", &mat1[i][j]); for(i=0; i<dim; i++) for(j=0; j<(i+1); j++) printf("%d%c", mat1[i][j], j != (dim-1) ? ' ' : '\n'); return 0; } 

EDIT

ok, therefore, changing the code the way you helped me, I have to read the upper triangular and lower triangular matrix and show their product. The problem is that I do not store zeros in memory, so if I use the traditional 3-for algorithm, it will show some unwanted values. And if I initialize the rest of each of the matrices with 0, it is useless to allocate memory dynamically, because I will also have zeros, so I haven’t done anything to increase storage efficiency yet. I think I need to change the code somewhere or maybe time intervals, but in any case, I change the program outputs (for a 3x3 matrix) 2 values ​​of junk mail in the upper right corner. How can I do it?

 #include <stdio.h> #include <stdlib.h> int main () { int i,j,k,**mat1,**mat2,**prod,dim; printf("Give dimension: \n"); scanf("%d",&dim); mat1 = (int**)calloc(dim,sizeof(int*)); for(i=0; i<dim; i++) mat1[i] = (int*)calloc(i+1,sizeof(int)); mat2 = (int**)calloc(dim,sizeof(int*)); for(i=dim-1; i>-1; i--) mat2[i]=(int*)calloc(i+1,sizeof(int)); prod = (int**)calloc(dim,sizeof(int*)); for(i=0; i<dim; i++) prod[i] = (int*)calloc(dim,sizeof(int)); printf("Give lower triangular matrix(non 0 values only): \n"); for(i=0; i<dim; i++) for(j=0; j<i+1; j++) scanf("%d",&mat1[i][j]); printf("Give upper triangular matrix(non 0 values): \n"); for(i=0; i<dim; i++) for(j=i; j<dim;j++) scanf("%d",&mat2[i][j]); printf("Matrix A is: \n"); for(i=0; i<dim; i++) for(j=0; j<dim; j++) printf("%d%c",j<=i?mat1[i][j]:0,j!=dim-1?' ':'\n'); printf("Matrix B is: \n"); for(i=0; i<dim; i++) for(j=0; j<dim; j++) printf("%d%c",j>=i?mat2[i][j]:0,j!=dim-1?' ':'\n'); for(i=0; i<dim; i++) for(j=0; j<dim; j++) for(k=0; k<dim; k++) prod[i][j]+=mat1[i][k]*mat2[k][j]; printf("The product of the two matrix is: \n"); for(i=0; i<dim; i++) for(j=0; j<dim; j++) printf("%d%c",prod[i][j],j!=dim-1?' ':'\n'); return 0; 

}

Answer 1

 mat1 = calloc(dim,sizeof(int*)); 

mat1 is a double pointer. You need to allocate memory for your array of pointers, and then you need to allocate memory for each of your pointers individually. No need to allocate calloc()

Answer 2

If you want to save space and the overhead of allocating each row of the matrix, you can implement a triangular matrix using smart indexing of one array.

The lower triangular matrix (including diagonals) has the following properties:

  Dimension Matrix Elements / row Total elements
 1 x  .  .  eleven
 2 xx.  .  2 3
 3 xxx.  3 6
 4 xxxx 4 10
 ...

Total number of elements for a given dimension:

 size(d) = 1 + 2 + 3 + ... + d = (d+1)(d/2) 

If you put rows sequentially in one array, you can use the above formula to calculate the offset of a given row and column (both based on zero) inside the matrix:

 index(r,c) = size(r-1) + c 

The above formulas for the lower triangular matrix. You can access the upper matrix as if it were the lower matrix by simply changing the indices:

 index((d-1)-r, (d-1)-c) 

If you have problems changing the orientation of the array, you can develop a different offset calculation for the upper array, for example:

 uindex(r,c) = size(d)-size(dr) + cr 

Code example:

 #include <time.h> #include <stdio.h> #include <stdlib.h> #define TRM_SIZE(dim) (((dim)*(dim+1))/2) #define TRM_OFFSET(r,c) (TRM_SIZE((r)-1)+(c)) #define TRM_INDEX(m,r,c) ((r)<(c) ? 0 : (m)[TRM_OFFSET((r),(c))]) #define TRM_UINDEX(m,r,c,d) ((r)>(c)?0:(m)[TRM_SIZE(d)-TRM_SIZE((d)-(r))+(c)-(r)]) #define UMACRO 0 int main (void) { int i, j, k, dimension; int *ml, *mu, *mr; printf ("Enter dimension: "); if (!scanf ("%2d", &dimension)) { return 1; } ml = calloc (TRM_SIZE(dimension), sizeof *ml); mu = calloc (TRM_SIZE(dimension), sizeof *mu); mr = calloc (dimension*dimension, sizeof *mr); if (!ml || !mu || !mr) { free (ml); free (mu); free (mr); return 2; } /* Initialization */ srand (time (0)); for (i = 0; i < TRM_SIZE(dimension); i++) { ml[i] = 100.0*rand() / RAND_MAX; mu[i] = 100.0*rand() / RAND_MAX; } /* Multiplication */ for (i = 0; i < dimension; i++) { for (j = 0; j < dimension; j++) { for (k = 0; k < dimension; k++) { mr[i*dimension + j] += #if UMACRO TRM_INDEX(ml, i, k) * TRM_UINDEX(mu, k, j, dimension); #else TRM_INDEX(ml, i, k) * TRM_INDEX(mu, dimension-1-k, dimension-1-j); #endif } } } /* Output */ puts ("Lower array"); for (i = 0; i < dimension; i++) { for (j = 0; j < dimension; j++) { printf (" %2d", TRM_INDEX(ml, i, j)); } putchar ('\n'); } puts ("Upper array"); for (i = 0; i < dimension; i++) { for (j = 0; j < dimension; j++) { #if UMACRO printf (" %2d", TRM_UINDEX(mu, i, j, dimension)); #else printf (" %2d", TRM_INDEX(mu, dimension-1-i, dimension-1-j)); #endif } putchar ('\n'); } puts ("Result"); for (i = 0; i < dimension; i++) { for (j = 0; j < dimension; j++) { printf (" %5d", mr[i*dimension + j]); } putchar ('\n'); } free (mu); free (ml); free (mr); return 0; } 

Please note that this is a trivial example. You can expand it to wrap the pointer over the matrix inside the structure, which also stores the type of matrix (upper or lower triangle or square), as well as the dimensions and write access functions that work accordingly, depending on the type of matrix.

For any non-trivial use of matrices, you should probably use a third-party library that specializes in matrices.

Answer 3

You cast mat1 on line 8 before it is even set to a point anywhere. You allocate an array of pointers to int, but you do not assign it to mat1 , and to dereferencing mat1, which is not initialized, we do not know what it points to.

So this line:

 // ERROR: You are saying an unknown memory location should have the value of calloc. *mat1 = (int**)calloc(dim,sizeof(int*)); 

Should change to:

 // OK: Now you are assigning the allocation to the pointer variable. mat1 = (int**)calloc(dim,sizeof(int*));