Recursion with matrix parts

[ onako @ 01.04.2010. 15:37 ] @

As a part of the project I'm working on, the input matrix needs to be deflated, meaning split into 2 parts. These parts are the upper left and lower right portions of the original matrix, and certain operation needs to be performed there. When in the process of deflation(splitting) we encounter a 1x1` matrix, we should stop and print that matrix. Take a look at the following code:

Code:

void ImplicitQRdeflatedAll(Matrix Dmatrix, VecDouble& EigenValues) {
        if(Dmatrix.rowNo==1) {
         PrintMatrix(Dmatrix);
          return;
        } else {
                 for(int i=1;i<=20;i++) {
                 Dmatrix=forImplicitQR(Dmatrix);
                 if(i%3==0) {
                  int k=checkConvDominant(Dmatrix);
                 if(k!=-1) {
                    std::pair<Matrix, Matrix> myLRpair=deflate(Dmatrix, k);
                   ImplicitQRdeflatedAll(myLRpair.first, EigenValues);
                   ImplicitQRdeflatedAll(myLRpair.second, EigenValues);
                  return;
                }
           }
       }
   }
}

The idea is to print out n(where n is the number of rows/columns of the input matrix) 1x1 matrices, but the code above sometimes reaches n print outs, but more frequently less than n printouts. Any idea why this happens? Thanks

[ onako @ 01.04.2010. 15:39 ] @

I've rewritten the code, in order to get what's going on more clearly:

Code:

void ImplicitQRdeflatedAllRAM(MatrixRAM Dmatrix);
void splittingMethodRAM(MatrixRAM t1, MatrixRAM t2) {
      if(t1.rowNo==1 && t2.rowNo==1) {
        std::cout<<"Cond 1:"<<t1.mat[0]<<std::endl;
        std::cout<<"Cond 1:"<<t2.mat[0]<<std::endl;
      } else if (t1.rowNo==1 && t2.rowNo!=1) {
        std::cout<<"Cond 2:"<<t1.mat[0]<<std::endl;
        ImplicitQRdeflatedAllRAM(t2);
      } else if (t1.rowNo!=1 && t2.rowNo==1) {
        std::cout<<"Cond 3:"<<t2.mat[0]<<std::endl;
        ImplicitQRdeflatedAllRAM(t1);
      } else {
        ImplicitQRdeflatedAllRAM(t1);
        ImplicitQRdeflatedAllRAM(t2);
      }
}
void ImplicitQRdeflatedAllRAM(MatrixRAM Dmatrix) {
  for(int i=1;i<=20;i++) {
          Dmatrix=forImplicitQR_RAM(Dmatrix);
          if(i%3==0) {
              int k=checkConvDominantRAM(Dmatrix);
              if(k!=-1) {
                   std::pair<MatrixRAM, MatrixRAM> myLRpair=deflateRAM(Dmatrix, k);
           displayMatrixRAM(myLRpair.first);
           displayMatrixRAM(myLRpair.second);
                   splittingMethodRAM(myLRpair.first, myLRpair.second);
           break;
              }
          }
     }
}

This is the sample output (execution 1):

Code:

23.69576914

-3.537866479 0.1513080256 -2.524960609e-16 -2.506805929e-16 -8.999473823e-17 -3.28069668e-17
0.1513080256 -2.657773649 0.5516137251 1.034959735e-16 6.084075703e-17 7.224027212e-17
-1.255177787e-17 0.5516137251 -2.593802287 0.3667046744 -7.525384817e-17 -1.058456459e-16
-7.855743689e-18 3.002372497e-18 0.3667046744 -1.892084595 0.2455554104 9.020562075e-17
-1.563849581e-18 -2.549194837e-17 2.35747981e-17 0.2455554104 -1.947101501 0.1002610174
-5.210227644e-18 2.280112503e-17 -3.450402403e-17 1.387778781e-17 0.1002610174 -1.283769202

Cond 2:23.69576914

Note that the size of the second matrix is more than 1X1, and that ImplicitQRdeflatedAllRAM(t2); from the first else if statement should be executed(splitting further the matrix). However, the program stops here. But on some other execution, I get the following output:

Code:

23.69576914

-3.262118558 0.1637324253 6.68950829e-17 6.180268921e-17 4.243345686e-17 1.565355317e-17
0.1637324253 -3.087526486 0.6684337753 -3.071079334e-16 -1.512251779e-16 -5.584501028e-17
8.660922781e-19 0.6684337753 -2.435240634 0.2545919516 8.662132137e-17 2.839714523e-17
-3.568173353e-18 -3.450598481e-17 0.2545919516 -1.828971387 0.3103821624 -4.163336342e-17
-1.07389778e-17 2.661498469e-17 -3.28059203e-17 0.3103821624 -1.557021983 0.2934575252
-6.219060656e-18 1.853667482e-17 -1.385474889e-17 6.938893904e-18 0.2934575252 -1.687626971

Cond 2:23.69576914
-3.543672409 0.1062454639
0.1062454639 -3.241790696

-2.219674091 0.02745130302 1.185696483e-16 1.870220652e-16
0.02745130302 -1.962574437 0.02332143798 -2.093120057e-16
-5.189155563e-18 0.02332143798 -1.685130584 0.001669833018
-1.084473558e-17 -5.393905808e-18 0.001669833018 -1.205663802

-2.221203145 -0.01894417801 -1.24367854e-16
-0.01894417801 -1.962220104 0.0147521074
5.090329784e-18 0.0147521074 -1.683960903

-1.205658762

Cond 3:-1.205658762
-2.222568222 -0.002008037457
-0.002008037457 -1.961633638

-1.683182292

Cond 3:-1.683182292
-2.222580222

-1.961621638

Cond 1:-2.222580222
Cond 1:-1.961621638

Note that here the second matrix is of the same dimension as in the first output, but the program here continues with the execution. Any clues how to allow the program the complete execution?

[ onako @ 01.04.2010. 18:36 ] @

Any thoughts?

[ Mihajlo Cvetanović @ 01.04.2010. 19:56 ] @

There is not enough information to produce a meaningful answer. The code is incomplete, so we can't test it and see the problem for ourselves. The only advice I can give you is try to debug the code step by step, and look for the point in code where the behavior differs from expected.

Maybe the operator= or copy operator are copying something wrong. Maybe the printing function is printing wrong.

Citat:

onako:
Note that the size of the second matrix is more than 1X1, and that ImplicitQRdeflatedAllRAM(t2); from the first else if statement should be executed(splitting further the matrix). However, the program stops here.

Does it stop here, or does it go into the function, doing something inside, and then returns without doing what is was supposed to do? If you debug it step by step then you would know for sure.

[ onako @ 03.04.2010. 19:18 ] @

The issue has been resolved. Increasing the number of iterations (more than 20, in my code) would allow for convergence. This would be an elegant solution for dominant eigenvalues. Thanks anyway

[ kiklop74 @ 05.04.2010. 19:48 ] @

A sto engleski?

[ Mihajlo Cvetanović @ 05.04.2010. 20:49 ] @

Možda je Albanac.

[ kiklop74 @ 05.04.2010. 21:27 ] @

da, ima smisla.