0

I am working on implementing Straussen's Multiplication. Below is my method for multiplying them in a Divide and Conquer Approach.

public static double[][] multiply(double[][] A, double[][] B)

    {        

        int n = A.length;

        double[][] R = new double[n][n];

        /** base case **/

        //if (n == 1){

          //  R[0][0] = A[0][0] * B[0][0];
       // }

        //else{
        
            double[][] A11 = new double [n/2][n/2];

            double[][] A12 = new double [n/2][n/2];

            double[][] A21 = new double [n/2][n/2];

            double[][] A22 = new double [n/2][n/2];

            double[][] B11 = new double [n/2][n/2];

            double[][] B12 = new double [n/2][n/2];

            double[][] B21 = new double [n/2][n/2];

            double[][] B22 = new double [n/2][n/2];

 

            /** Dividing matrix A into 4 halves **/

            split(A, A11, 0 , 0);

            split(A, A12, 0 , n/2);

            split(A, A21, n/2, 0);

            split(A, A22, n/2, n/2);

            /** Dividing matrix B into 4 halves **/

            split(B, B11, 0 , 0);

            split(B, B12, 0 , n/2);

            split(B, B21, n/2, 0);

            split(B, B22, n/2, n/2);

 

            /** 

              M1 = (A11 + A22)(B11 + B22)

              M2 = (A21 + A22) B11

              M3 = A11 (B12 - B22)

              M4 = A22 (B21 - B11)

              M5 = (A11 + A12) B22

              M6 = (A21 - A11) (B11 + B12)

              M7 = (A12 - A22) (B21 + B22)

            **/

 

            double [][] M1 = multiply(add(A11, A22), add(B11, B22));

            double [][] M2 = multiply(add(A21, A22), B11);

            double [][] M3 = multiply(A11, sub(B12, B22));

            double [][] M4 = multiply(A22, sub(B21, B11));

            double [][] M5 = multiply(add(A11, A12), B22);

            double [][] M6 = multiply(sub(A21, A11), add(B11, B12));

            double [][] M7 = multiply(sub(A12, A22), add(B21, B22));

 

            /**

              C11 = M1 + M4 - M5 + M7

              C12 = M3 + M5

              C21 = M2 + M4

              C22 = M1 - M2 + M3 + M6

            **/

            double [][] C11 = add(sub(add(M1, M4), M5), M7);

            double [][] C12 = add(M3, M5);

            double [][] C21 = add(M2, M4);

            double [][] C22 = add(sub(add(M1, M3), M2), M6);

 

            /** join 4 halves into one result matrix **/

            join(C11, R, 0 , 0);

            join(C12, R, 0 , n/2);

            join(C21, R, n/2, 0);

            join(C22, R, n/2, n/2);

        

        /** return result **/    
        
        return R;

    }

In order to implement this code, I am reading in 2 txt files, one for matrix A and one for matrix B. For terms of testing I have the two matrices being the exact same:

5

3.250 6.130 3.180 7.680 9.060

5.450 1.660 6.790 6.650 4.250

4.460 8.260 7.870 7.880 1.890

1.460 8.510 8.510 3.510 1.440

1.590 7.160 4.400 3.310 1.970

Where the first line is n, and the following lines are the matrix.

My problem is that I am getting a stack overflow error on the line

int n = A.length;

Which I can't seem to figure out why or where to look. So my question is, does the problem lie in this algorithm? Or would the problem be in my main method?

Community
  • 1
  • 1
user2580
  • 25
  • 6
  • Don't see much of a problem in `multiply()` (const correctness - what language is this, anyway? Are `A` and `B` guaranteed to be equal power-of-2-size and square?). What about `split()` and `join()`? How big is `n`, what is the run time environment, and how much stack is allowed for? – greybeard Jul 25 '16 at 19:03
  • @greybeard This program is in java. A and B should be guaranteed equal power of 2 sized. Not sure what you are asking about the rest though – user2580 Jul 25 '16 at 20:38
  • (Please put clarifications and additional information in the question, not in comments. Please paste in (relevant parts of) the error message. (while at it, please remove the extra blank lines.)) You presented `multiply()` and mentioned `main()` - do either `split()` or `join()` call `multiply()`, even indirectly? Now that you specified _Java_: what is the output of `java -XshowSettings:vm -version`? (Higher versions of oracle's VM don't show the/a stack size limit any more?!) How big is `n` (`A.length`), what memory occupancy is to be expected? – greybeard Jul 26 '16 at 01:33
  • Do you use an IDE, such as Eclipse? Are you aware of [What is a stack trace, and how can I use it to debug my application errors?](http://stackoverflow.com/questions/3988788/what-is-a-stack-trace-and-how-can-i-use-it-to-debug-my-application-errors)? – greybeard Jul 26 '16 at 01:35
  • (Wait - do you run into this problem with the base case commented out? What is the idea?) – greybeard Jul 26 '16 at 02:14

0 Answers0