Calculation of determinant takes extremely long time.

Ananda Murthy R S rsamurti at sancharnet.in
Tue Jan 22 16:49:18 CET 2002


Hello:

Below I have given a program which tries to find the determinant of a matrix 
having real numbers and and symbols. The program compiles properly. But 
when I run the program it takes extremely long time to give the output. I 
have waited for nearly 4 hours before pressing Ctrl+C.

How can I find determinants of such matrices of larger sizes? 

What method does GiNaC employ to calculate the determinant of a matrix having 
symbols?

What method does GiNaC employ to calculate the characteristic polynomial of a 
matrix?

// This is Example-1 given in the paper ``Numerical Computation of
// Decentralized Fixed Modes'' by R.V.Patel and P.Misra, Automatica,
// Vol.27, No.2, pp.375-382, 1991.

#include <iostream>
#include <ginac/ginac.h>
using namespace GiNaC;
using namespace std;

int main()
{
   symbol F11("F11"), F12("F12"), F13("F13"),
          F21("F21"), F22("F22"), F23("F23"),
          F31("F31"), F32("F32"), F33("F33"),
          F44("F44"), F45("F45"), F46("F46"),
          F54("F54"), F55("F55"), F56("F56"),
          F64("F64"), F65("F65"), F66("F66"),
          F77("F77"), F78("F78"), F79("F79"),
          F87("F87"), F88("F88"), F89("F89"),
          F97("F97"), F98("F98"), F99("F99"), s("s");

   ex w1[8][8] = {
      {-2.902280128,   4.902280128,    3.698135576,   -1.091710896,
       -1.339597088,  -3.833588112,    0.1354525359,   0.1354525359},
      {14.57598539,    8.663631092,    4.471485536,   -6.163631092,
       -1.031929416,   1.692145555,  -11.85191042,     0.5280631913},
      {-13.01717766,   5.242845433,    6.808655713,    0.3658471056,
       -1.250335699,  -9.401666250,    5.593010537,   -0.1838540200},
      {-9.358517860,   9.358517860,    9.233430521,   -1.249825322,
       -1.102425449, -10.21076863,     0.9773381096,   0.9773381096},
      {10.90157850,   10.33803799,     6.577811264,   -6.527468755,
       -1.463336353,  -1.277505940,  -10.98858465,     1.391388959},
      { 7.438961098,   6.026323164,    4.365195826,   -4.228199859,
       -1.659477876,  -1.136995967,   -5.916479189,    0.6866298675},
      { 4.590977560,   7.475549489,    4.982190956,   -3.664980257,
       -2.282092104,  -2.544374131,   -5.126096156,    0.4770129007},
      {16.85292654,    5.785447163,    2.204831037,   -5.785447163,
       -1.798583916,   3.580616126,  -11.47372649,     1.906247120}};

   ex w2[8][9]={
      { -6.288091946, -8.384122594, -10.48015324,
        24.06096115,   8.869414499,   7.808913485,
        -2.620038311, -3.144045973, -13.10019155},
      {  6.989292416,  9.319056555,  11.64882069,
        16.40558839,  19.28474045,    8.940485304,
         2.912205174,  3.494646208,  14.56102587},
      {-13.54775782, -18.06367710,  -22.57959637,
        25.20750633,  18.08277192,   31.47867615,
        -5.644899094, -6.773878912, -28.22449547},
      { -5.198332933, -6.931110578,  -8.663888222,
        23.84960895,  19.94822168,   17.03165000,
        -2.165972056, -2.599166467, -10.82986028},
      { -7.648224421,-10.19763256,  -12.74704070,
        10.15737156,   9.939200440,   4.700713320,
        -3.186760175, -3.824112210, -15.93380088},
      { -5.899533404, -7.866044538,  -9.832555673,
        19.48795695,  26.58611759,   31.63366095,
        -2.458138918, -2.949766702, -12.29069459},
      {-6.288091946,  -8.384122594, -10.48015324,
       29.74830670,   25.04543540,   17.08815424,
       -2.620038311,  -3.144045973, -13.10019155},
      { 1.360132475,   1.813509966,   2.266887458,
       17.73934984,   17.02037591,   14.47725433,
        0.5667218645, 0.6800662374,  2.833609322}};

   ex w3[9][8]={
      {-2.632399367,  -0.8816532905,  0.2216458770,  0.8816532905,
        0.3060021972, -1.103299168,   1.223098002,   0.5276480743},
      { 0.6965370444, -0.6965370444, -0.6386855981,  0.0878917469,
        0.0698972579,  0.6507314098, -0.0120458116, -0.0120458116},
      { 0.1251321667,  0.7413375337,  3.578384236,  -0.2660527380,
       -0.0994345890, -3.687097343,  -3.700738679,   2.940754836},
      { 0.9728813679, -0.6824007787,  0.8321248154,  0.0737554812,
        0.0515436172, -0.8059427381, -1.726710642,   1.440410961},
      { 0.6338502954,  1.253223829,   1.874876846,  -0.7779391327,
       -0.2226901107, -1.471703558,  -0.7446180000,  1.113991924},
      { 0.0725179078, -0.0725179078, -0.4003742177,  0.6048139599,
       -0.1581541911,  0.5700763364, -0.1697021187, -0.1697021187},
      { 0.0952676686, -0.0687101141,  0.0066780601,  0.0905768308,
       -0.1072959550,  0.1535121891,  0.1560969942,  0.0472149362},
      {-0.2252498152,  0.0992129486,  0.1715238903,  0.1417124980,
       -0.0477814471, -0.0948070092,  0.1258808196,  0.0636080200},
      {-0.2314675213,  0.1207746598,  0.2092921292,  0.0112031403,
       -0.0280553044, -0.0858390289,  0.3357822914, -0.0594501770}};

   ex w4[9][9]={
      {F11, F12, F13,  0,   0,   0,   0,   0,   0 },
      {F21, F22, F23,  0,   0,   0,   0,   0,   0 },
      {F31, F32, F33,  0,   0,   0,   0,   0,   0 },
      { 0,   0,   0,  F44, F45, F46,  0,   0,   0 },
      { 0,   0,   0,  F54, F55, F56,  0,   0,   0 },
      { 0,   0,   0,  F64, F65, F66,  0,   0,   0 },
      { 0,   0,   0,   0,   0,   0,  F77, F78, F79},
      { 0,   0,   0,   0,   0,   0,  F87, F88, F89},
      { 0,   0,   0,   0,   0,   0,  F97, F98, F99}};

   ex w5[8][8]={
      {1,0,0,0,0,0,0,0},
      {0,1,0,0,0,0,0,0},
      {0,0,1,0,0,0,0,0},
      {0,0,0,1,0,0,0,0},
      {0,0,0,0,1,0,0,0},
      {0,0,0,0,0,1,0,0},
      {0,0,0,0,0,0,1,0},
      {0,0,0,0,0,0,0,1}};

   matrix A(8,8);
   matrix B(8,9);
   matrix C(9,8);
   matrix F(9,9);
   matrix I(8,8);

//This loop fills A matrix with values.
   for(unsigned r=0;r<8;r++)
   {
      for(unsigned c=0;c<8;c++)
      {
         A.set(r,c,w1[r][c]);
      }
   }

//This loop fills B matrix with values.
   for(unsigned r=0;r<8;r++)
   {
      for(unsigned c=0;c<9;c++)
      {
         B.set(r,c,w2[r][c]);
      }
   }

// This loop fills C matrix with values.
   for(unsigned r=0;r<9;r++)
   {
      for(unsigned c=0;c<8;c++)
      {
         C.set(r,c,w3[r][c]);
      }
   }

// This loop fills F matrix with values.
   for(unsigned r=0;r<9;r++)
   {
      for(unsigned c=0;c<9;c++)
      {
         F.set(r,c,w4[r][c]);
      }
   }

// This loop fills I matrix with values.
   for(unsigned r=0;r<8;r++)
   {
      for(unsigned c=0;c<8;c++)
      {
         I.set(r,c,w5[r][c]);
      }
   }


   matrix AplusBFC = A.add(B.mul(F.mul(C)));
   matrix Af = I.mul_scalar(s).sub(AplusBFC);

   ex e1=determinant(Af);
   ex e2=charpoly(AplusBFC,s);

   cout << "R V Patel et al EXAMPLE-1:" << endl;
   cout << "MATRIX [A] = " << endl;
   cout << A << endl << endl;
   cout << "MATRIX [B] = " << endl;
   cout << B << endl << endl;
   cout << "MATRIX [C] = " << endl;
   cout << C << endl << endl;
   cout << "MATRIX [F] = " << endl;
   cout << F << endl << endl;
   cout << "MATRIX [AplusBFC] = " << endl;
   cout << AplusBFC << endl << endl;
   cout << "MATRIX [Af] = " << endl;
   cout << Af << endl << endl;
   cout << "Determinant |sI-AplusBFC| = "  << endl;
   cout << e1  << endl;
   cout << "Characteristic polynomial of Af = "  << endl;
   cout << e2  << endl << endl << endl;
   return 0;
}

Thanks for helping me.

Sincerely,

Anand



More information about the GiNaC-list mailing list