Segmentierungsfehler bei der C-Programmierung über die Durchführung des Strassen-Algorithmus in der Matrixmultiplikation

Question

Ich schreibe einen Code, der die Multiplikation zweier dichter Matrizen mit Hilfe des Strassen-Algorithmus zum Ziel hat. Der Hauptcode ist eine rekursive Funktion, deren Grundfall ist, wenn die Größe der zwei Matrix 2x2 ist, daher ist die Multiplikation der Matrix nur die Multiplikation von reellen Zahlen. Wenn der Basisfall nicht erfüllt ist, berechne ich dann die Sieben-Matrix, die zur Berechnung des Endergebnisses der Multiplikation verwendet wird, indem ich die Rekursivfunktion erneut anrufe, wobei die Größe der Matrix durch die Hälfte geteilt wird. Beim Versuch, diesen Code auszuführen, erhalte ich jedoch einen Segmentierungsfehler, aber ich kann einfach nicht herausfinden, warum. Ich benutze den Debugger gdb, scheint irgendwann NULL temp1 und C1, aber ich habe keine Ahnung, warum das passiert. Außerdem wird der Zähler, den ich in der for-Schleife verwendet habe, weit über das Limit hinausgehen (sie sollten innerhalb von n/2 zurückgehalten werden). Ist dies der richtige Weg, um den Algorithmus von Strassen rekursiv durchzuführen? Hier ist mein Code.

#include "assignment2.h" 

void denseMatrixMult(int ** A, int ** B, int *** resultMatrix, int n) 
{ 
    if(n==2) 
    { 
     int M0,M1,M2,M3,M4,M5,M6; 
     M0=(A[0][0]+A[1][1])*(B[0][0]+B[1][1]); 
     M1=(A[1][0]+A[1][1])*B[0][0]; 
     M2=A[0][0]*(B[0][1]-B[1][1]); 
     M3=A[1][1]*(B[1][0]-B[0][0]); 
     M4=(A[0][0]+A[0][1])*B[1][1]; 
     M5=(A[1][0]-A[0][0])*(B[0][0]+B[0][1]); 
     M6=(A[0][1]-A[1][1])*(B[1][0]+B[1][1]); 
     int** temp; 
     initMatrix(&temp,2); 
     resultMatrix=&temp; 
     *(resultMatrix)[0][0]=M0+M3-M4+M6; 
     *(resultMatrix)[0][1]=M2+M4; 
     *(resultMatrix)[1][0]=M1+M3; 
     *(resultMatrix)[1][1]=M0-M1+M2+M5; 
     /*free(freeMatrix(temp);*/ 
     return; 
    } 
    else 
    { 
     int a,b,c,d,e,f,g,h; 
     int** N0; 
     int** N1; 
     int** N2; 
     int** N3; 
     int** N4; 
     int** N5; 
     int** N6; 
     int** zero; 
     int** C1; 
     int** C2; 
     int** C3; 
     int** C4; 
     initMatrix(&N0,n/2); 
     initMatrix(&N1,n/2); 
     initMatrix(&N2,n/2); 
     initMatrix(&N3,n/2); 
     initMatrix(&N4,n/2); 
     initMatrix(&N5,n/2); 
     initMatrix(&N6,n/2); 
     initMatrix(&zero,n/2); 
     denseMatrixMult(sum(A,A,0,0,n/2,n/2,n/2),sum(B,B,0,0,n/2,n/2,n/2),&N0,n/2); 
     denseMatrixMult(sum(A,A,n/2,0,n/2,n/2,n/2),sum(B,zero,0,0,0,0,n/2),&N1,n/2); 
     denseMatrixMult(sum(A,zero,0,0,0,0,n/2),sub(B,B,0,n/2,n/2,n/2,n/2),&N2,n/2); 
     denseMatrixMult(sum(A,zero,n/2,n/2,0,0,n/2),sub(B,B,n/2,0,0,0,n/2),&N3,n/2); 
     denseMatrixMult(sum(A,A,0,0,0,n/2,n/2),sum(B,zero,n/2,n/2,0,0,n/2),&N4,n/2); 
     denseMatrixMult(sub(A,A,n/2,0,0,0,n/2),sum(B,B,0,0,0,n/2,n/2),&N5,n/2); 
     denseMatrixMult(sub(A,A,0,n/2,n/2,n/2,n/2),sum(B,B,n/2,0,n/2,n/2,n/2),&N6,n/2); 
     C1=sum(sub(sum(N0,N3,0,0,0,0,n/2),N4,0,0,0,0,n/2),N6,0,0,0,0,n/2); 
     C2=sum(N2,N4,0,0,0,0,n/2); 
     C3=sum(N1,N3,0,0,0,0,n/2); 
     C4=sum(sum(sub(N0,N1,0,0,0,0,n/2),N2,0,0,0,0,n/2),N5,0,0,0,0,n/2); 
     int** temp1; 
     initMatrix(&temp1,n); 
     resultMatrix=&temp1; 
     for(a=0;a<n/2;a++) 
     { 
      for(b=0;b<n/2;b++) 
      { 
       (*resultMatrix)[a][b]=C1[a][b]; 
      } 
     } 
     for(c=n/2;c<n;c++) 
     { 
      for(d=0;d<n/2;d++) 
      { 
       (*resultMatrix)[c][d]=C3[c-n/2][d]; 
      } 
     } 
     for(e=0;e<n/2;e++) 
     { 
      for(f=n/2;f<n;f++) 
      { 
       (*resultMatrix)[e][f]=C2[e][f-n/2]; 
      } 
     } 
     for(g=n/2;g<n;g++) 
     { 
      for(h=n/2;h<n;h++) 
      { 
       (*resultMatrix)[g][h]=C4[g-n/2][h-n/2]; 
      } 
      } 
      /*freeMatrix(N0); 
      freeMatrix(N1); 
      freeMatrix(N2); 
      freeMatrix(N3); 
      freeMatrix(N4); 
      freeMatrix(N5); 
      freeMatrix(N6); 
      freeMatrix(C1); 
      freeMatrix(C2); 
      freeMatrix(C3); 
      freeMatrix(C4);*/ 


    } 
} 
int **sum(int ** A, int ** B, int x1, int y1, int x2, int y2, int n) 
{ 
    int i,j,k; 

    int ** res=(int**)malloc(n*sizeof(int*)); 
    if(res!=NULL) 
    { 
     for(i=0;i<n;i++) 
     { 
      res[i]=(int*)malloc(n*sizeof(int)); 
     } 

     for(j=0;j<n;j++) 
     { 
      for(k=0;k<n;k++) 
      { 
       res[j][k]=A[x1+j][y1+k]+B[x2+j][y2+k]; 
      } 
     } 
    } 
    return res; 

} 
int **sub(int **A, int **B, int x1, int y1, int x2, int y2, int n) 
{ 
    int i,j,k; 

    int ** res=(int**)malloc(n*sizeof(int*)); 
    if(res!=NULL) 
    { 
     for(i=0;i<n;i++) 
     { 
      res[i]=(int*)malloc(n*sizeof(int)); 
     } 

     for(j=0;j<n;j++) 
     { 
      for(k=0;k<n;k++) 
      { 
       res[j][k]=A[x1+j][y1+k]-B[x2+j][y2+k]; 
      } 
     } 
    } 
    return res; 
} 
void initMatrix(int ***mat,int n) 
{ 
    int i,j,k; 
    int ** Mat=(int**)malloc(n*sizeof(int*)); 
    for(i=0;i<n;i++) 
    { 
     Mat[i]=(int*)malloc(n*sizeof(int)); 
    } 
    for(j=0;i<n;i++) 
    { 
     for(k=0;k<n;i++) 
     { 
      Mat[j][k]=0; 
     } 
    } 
    *mat=Mat; 
} 

int **readMatrix(char * filename) 
{ 
    int i,j,k; 
    int **mat=(int**)malloc(MATSIZE*sizeof(int*)); 
    for(i=0;i<MATSIZE;i++) 
    { 
     mat[i]=(int*)malloc(MATSIZE*sizeof(int)); 
    } 
    FILE *fp=fopen(filename,"r"); 
    for(j=0;j<MATSIZE;j++) 
    { 
     for(k=0;k<MATSIZE;k++) 
     { 
      fscanf(fp,"%d",&mat[j][k]); 
     } 
    } 
    fclose(fp); 
    return mat; 

} 
void freeMatrix(int n, int ** matrix) 
{ 
    int i; 
    for(i=0;i<n;i++) 
    { 
     free(matrix[i]); 
    } 
    free(matrix); 
} 

void printMatrix(int n, int ** A) 
{ 
    int i,j; 
    for(i=0;i<n;i++) 
    { 
     for(j=0;j<n;j++) 
     { 
      printf("%d",A[i][j]); 
     } 
    } 
} 
#include "assignment2.h" 

void p1(void) 
{ 
    int **matrix; 
    initMatrix(&matrix,MATSIZE); 
    printMatrix(MATSIZE,matrix); 
    freeMatrix(MATSIZE, matrix); 
} 

void p2(void) 
{ 
    int ** matrix1=readMatrix("matrix1.txt"); 
    printMatrix(MATSIZE,matrix1); 
    freeMatrix(MATSIZE, matrix1); 
} 

void p3a(void) 
{ 
    int ** matrix1=readMatrix("matrix1.txt"); 
    int ** matrix2=readMatrix("matrix2.txt"); 
    int ** sumMatrix = sum(matrix1, matrix2, 1, 1, 0, 1, 3); 
    printMatrix(MATSIZE,matrix1); 
    printMatrix(MATSIZE,matrix2); 
    printMatrix(3,sumMatrix); 
    freeMatrix(MATSIZE, matrix1); 
    freeMatrix(MATSIZE, matrix2); 
    freeMatrix(3, sumMatrix); 
} 

void p3b(void) 
{ 
    int ** matrix1=readMatrix("matrix1.txt"); 
    int ** matrix2=readMatrix("matrix2.txt"); 
    int ** subMatrix = sub(matrix1, matrix2, 1, 1, 0, 1, 3); 
    printMatrix(MATSIZE,matrix1); 
    printMatrix(MATSIZE,matrix2); 
    printMatrix(3,subMatrix); 
    freeMatrix(MATSIZE, matrix1); 
    freeMatrix(MATSIZE, matrix2); 
    freeMatrix(3, subMatrix); 
} 

void p4(void) 
{ 
    char dataFileMat1[]="matrix1.txt"; 
    char dataFileMat2[]="matrix2.txt"; 
    int ** matrix1=readMatrix(dataFileMat1); 
    int ** matrix2=readMatrix(dataFileMat2); 
    int ** resultingMatrix; 
    denseMatrixMult(matrix1, matrix2, &resultingMatrix, MATSIZE); 
    printMatrix(MATSIZE,resultingMatrix); 
    freeMatrix(MATSIZE,resultingMatrix); 
    freeMatrix(MATSIZE,matrix1); 
    freeMatrix(MATSIZE,matrix2); 
} 

int main(int argc, char *argv[]) 
{ 
    if(argc < 2) 
    { 
     printf("Expecting at least one argument. Please try again\n"); 
    } 
    else if(argc==2) 
    { 
     if(atoi(argv[1])==3) 
     { 
      printf("Expecting two arguments for this part. Please try again.\n"); 
     } 
     else 
     { 
      if(atoi(argv[1])==1) 
      { 
       p1(); 
      } 
      else if(atoi(argv[1])==2) 
      { 
       p2(); 
      } 
      else if(atoi(argv[1])==4) 
      { 
       p4(); 
      } 
      else 
      { 
       printf("Incorrect argument supplied.\n"); 
      } 
     } 
    } 
    else if(argc==3) 
    { 
     if(atoi(argv[1])!=3) 
     { 
      printf("Expecting two arguments only for Part 3. Please try again.\n"); 
     } 
     else 
     { 
      if(atoi(argv[2])==1) 
      { 
       p3a(); 
      } 
      else if(atoi(argv[2])==2) 
      { 
       p3b(); 
      } 
     } 
    } 
    else 
    { 
     printf("The argument supplied is %s\n", argv[1]); 
    } 
} 

Answer 1

Der Fehler free lässt vermuten, dass die Speicherverwaltung beschädigt ist. Möglicher Grund hierfür ist ein Schreibzugriff außerhalb des zulässigen Bereichs auf den zugewiesenen Speicher. Warum vereinfachen Sie nicht die Zuweisung von Matrizen?

Es ist nur ein malloc() erforderlich, um zuzuordnen. Dazu können Sie ein eindimensionales Array von geeigneter Größe zuweisen.

1. Sie können das zugeordnete Array verwenden, um Matrixelemente (Reihe für Reihe) nacheinander zu speichern. Lese- und Schreibzugriffe müssen in Form i * N + j (i ... Zeilenindex, j ... Spaltenindex, N ... Anzahl der Spalten) erfolgen.
2. Sie können C-Cast-Magic anwenden und es sogar als zweidimensionales Array verwenden.

vorbereitet I eine kleine Probe dieses zu demonstrieren:

#include <stdio.h> 
#include <stdlib.h> 

enum { N = 4 }; 

int main(int argc, char **argv) 
{ 
    int i, n; 
    /* allocation of an array with size NxN: */ 
    double *arr = (double*)malloc(N * N * sizeof (double)); 
    /* initialization of array (with some illustrative values) */ 
    for (i = 0, n = N * N; i < n; ++i) { 
    int row = i/N, col = i % N; 
    arr[i] = (double)(row + col * 0.1); 
    } 
    /* show contents */ 
    printf("arr[]:\n"); 
    for (i = 0; i < N; ++i) { 
    int j; 
    for (j = 0; j < N; ++j) { 
     printf("%s%.1f", j ? "\t" : "", arr[i * N + j]); 
    } 
    printf("\n"); 
    } 
    /* how this is used as two-dimensional array */ 
    { double (*mat)[N] = (double(*)[N])arr; 
    printf("mat[][]:\n"); 
    for (i = 0; i < N; ++i) { 
     int j; 
     for (j = 0; j < N; ++j) { 
     printf("%s%.1f", j ? "\t" : "", mat[i][j]); 
     } 
     printf("\n"); 
    } 
    } 
    /* clean-up */ 
    free(arr); 
    /* done */ 
    return 0; 
} 

Kompiliert und mit gcc auf cygwin getestet:

$ gcc -o test-mat test-mat.c 

$ ./test-mat 
arr[]: 
0.0  0.1  0.2  0.3 
1.0  1.1  1.2  1.3 
2.0  2.1  2.2  2.3 
3.0  3.1  3.2  3.3 
mat[][]: 
0.0  0.1  0.2  0.3 
1.0  1.1  1.2  1.3 
2.0  2.1  2.2  2.3 
3.0  3.1  3.2  3.3 

Der Typ double (*)[N] als „Adresse eines einem zu lesenden hat Matrix mit der Größe N ". Die Klammern können überraschend aussehen, sind aber notwendig. (Ohne, der Compiler würde dies als "eindimensionales Array von Adressen" lesen, was nicht meine Absicht ist.)