# 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 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