1

I have written a header file declares a function using three multidimension array as parameters and defined it in another .cpp file.It looks well but failed to find that function at linking time.Here is header file:

#ifndef StrassenAlgorithms_Algorithm_h
#define StrassenAlgorithms_Algorithm_h
template<int size>
void strassen_matrix_multiplication(int A[size][size], int B[size][size], int C[size][size]);

#endif

and then is the corresponding .cpp file:

#include "Algorithm.h"

template<int size>
void strassen_matrix_multiplication(int (*A)[size], int (*B)[size], int (*C)[size]){
if (size == 1) {
    return;
}

const int n = size / 2;
int A11[n][n];
int A12[n][n];
int A21[n][n];
int A22[n] [n];
for (int i=0; i<n; i++) {
    for (int j=0; j<n; j++) {
        A11[i][j] = A[i][j];
        A12[i][j] = A[i + n][j];
        A21[i][j] = A[i][j + n];
        A22[i][j] = A[i + n][j + n];
    }
}

int B11[n][n], B12[n][n], B21[n][n], B22[n][n];
for (int i=0; i<n; i++) {
    for (int j=0; j<n; j++) {
        B11[i][j] = A[i][j];
        B12[i][j] = A[i + n][j];
        B21[i][j] = A[i][j + n];
        B22[i][j] = A[i + n][j + n];
    }
}

/** S1 = B12 - B22 */
int S1[n][n];
for (int i=0; i<n; i++) {
    for (int j=0; j<n; j++) {
        S1[i][j] = B[i + n][j] - B[i + n][j + n];
    }
}

/** S2 = A11 + A12 */
int S2[n][n];
for (int i=0; i<n; i++) {
    for (int j=0; j<n; j++) {
        S2[i][j] = A[i][j] + A[i + n][j];
    }
}

/** S3 = A21 + A22 */
int S3[n][n];
for (int i=0; i<n; i++) {
    for (int j=0; j<n; j++) {
        S3[i][j] = A[i][j + n] + A[i + n][j + n];
    }
}

/** S4 = B21 - B11 */
int S4[n][n];
for (int i=0; i<n; i++) {
    for (int j=0; j<n; j++) {
        S4[i][j] = B[i][j + n] - B[i][j];
    }
}

/** S5 = A11 + A22 */
int S5[n][n];
for (int i=0; i<n; i++) {
    for (int j=0; j<n; j++) {
        S5[i][j] = A[i][j] + A[i + n][j + n];
    }
}

/** S6 = B11 + B22 */
int S6[n][n];
for (int i=0; i<n; i++) {
    for (int j=0; j<n; j++) {
        S6[i][j] = B[i][j] + B[i + n][j + n];
    }
}

/** S7 = A12 - A22 */
int S7[n][n];
for (int i=0; i<n; i++) {
    for (int j=0; j<n; j++) {
        S7[i][j] = A[i + n][j] - A[i + n][j + n];
    }
}

/** S8 = B21 + B22 */
int S8[n][n];
for (int i=0; i<n; i++) {
    for (int j=0; j<n; j++) {
        S8[i][j] = B[n][j + n] + B[i + n][j + n];
    }
}

/** S9 = A11 - A21 */
int S9[n][n];
for (int i=0; i<n; i++) {
    for (int j=0; j<n; j++) {
        S9[i][j] = A[i][j] - A[i][j + n];
    }
}

/** S10 = B11 + B12 */
int S10[n][n];
for (int i=0; i<n; i++) {
    for (int j=0; j<n; j++) {
        S10[i][j] = B[i][j] + B[i + n][j];
    }
}

int P1[n][n];
strassen_matrix_multiplication(A11, S1, P1);

int P2[n][n];
strassen_matrix_multiplication(S2, B22, P2);

int P3[n][n];
strassen_matrix_multiplication(S3, B11, P3);

int P4[n][n];
strassen_matrix_multiplication(A22, S4, P4);

int P5[n][n];
strassen_matrix_multiplication(S5, S6, P5);

int P6[n][n];
strassen_matrix_multiplication(S7, S8, P6);

int P7[n][n];
strassen_matrix_multiplication(S9, S10, P7);

/** C11 = P5 + P4 - P2 + P6 **/
for (int i=0; i<n; i++) {
    for (int j=0; j<n; j++) {
        C[i][j] = P5[i][j] + P4[i][j] - P2[i][j] + P6[i][j];
    }
}

/** C12 = P1 + P2 **/
for (int i=0; i<n; i++) {
    for (int j=0; j<n; j++) {
        C[i + n][j] = P1[i][j] + P2[i][j];
    }
}

/** C21 = P3 + P4 **/
for (int i=0; i<n; i++) {
    for (int j=0; j<n; j++) {
        C[i][j + n] = P3[i][j] + P4[i][j];
    }
}

/** C22 = P5 + P1 - P3 - P7 **/
for (int i=0; i<n; i++) {
    for (int j=0; j<n; j++) {
        C[i + n][j + n] = P5[i][j] + P1[i][j] - P3[i][j] - P7[i][j];
    }
}

return;    
}

and the last is the main file:

#include <iostream>
#include "Algorithm.h"
using namespace std;

int main(int argc, const char * argv[])
{
const int size = 2;
int A[size][size] = {{1, 2}, {3, 4}};
int B[size][size] = {{1, 2}, {3, 4}};
int C[size][size] = {0, 0, 0, 0};
strassen_matrix_multiplication<2>(A, B, C);
for(int i=0; i<size; i++){
    for (int j=0; j<size; j++) {
        cout << C[i][j] << "\t";
    }
    cout << endl;
  }
}

It has not compilation error but failed at linking time saying

Undefined symbols for architecture x86_64:
"void strassen_matrix_multiplication<2>(int (*) [2], int (*) [2], int (*) [2])", referenced from:
      _main in main.o
ld: symbol(s) not found for architecture x86_64
clang: error: linker command failed with exit code 1 (use -v to see invocation)

how can I resolve this problem? Thanks for any help. Waiting online.

Mat
  • 202,337
  • 40
  • 393
  • 406
tuan long
  • 605
  • 1
  • 9
  • 18
  • I won't add this as an answer, but basically you have to define your template method in the header file - http://stackoverflow.com/questions/495021/why-can-templates-only-be-implemented-in-the-header-file – pstrjds Dec 22 '12 at 15:21
  • @pstrjds:sorry, I got a compilation error saying "no matching function to strassen_matrix_multiplication" at the line of a reverse call of itself after defining it in the header file.What else modification do I need to do? – tuan long Dec 22 '12 at 15:36
  • Then you have something not quite correct with your templates. You are missing some braces on your definition of `C`. That should cause other compilation errors though. Check your template and the compiler error. It should tell you what function it could not generate/call due to lack of a matching template or implementation. – pstrjds Dec 22 '12 at 15:51

1 Answers1

1

Your issue is that template methods and classes cannot be implemented in an object file, but have to be implemented in the header so that the compiler can do it's template expansion. Beyond that, even if you could, those method signatures don't seem to precisely line up too me.

Linuxios
  • 34,849
  • 13
  • 91
  • 116