[GiNaC-list] Bug report: Problem with matrix inversions

[Dorel, Mathurin]

Hello,

Using GiNaC, I recently encountered problems with the symbolic inversion of matrices,
the inversion does not occur (or take more than 2h, which is the time I let the program run).

I wrote a minimum code that exhibits the problem (the source code is in the zip file
ginac_inversion_error_dorel.zip with a Makefile and my version compiled on
Debian GNU/Linux 7.10 (wheezy)). The script simply build an symbolic matrix, with -1 in
the diagonal and tries to invert it.
Usage: ./ginac_testing < adjacency_list
I ran my test script on a Debian GNU/Linux 7.10 (wheezy) machine with 16Gb of RAM
and 8 i7-3770 processors, so the computation power and the memory shouldn't be the problem
(and I checked, the memory is faaar from being full).

The input file represents a directed graph.
I joined several representative examples (in examples_ginac.zip):
    - network_colonet.tab: does not work;
    - lesscJun_network_colonet.tab: does not work;
    - MEK-ERK_network_colonet.tab: does the inversion in 45s, it is only 'network_colonet.tab' with
one entry removed (but which removal removes a cycle in the graph);
    - plusdummy_MEK-ERK_network_colonet.tab: does the inversion in 52s, it's the previous network with
a link that does not add any cycle;
    - IKK-ERK_onlyEGF.tab: does the inversion in 830s/1400s !!, it is 'network_colonet.tab' with several entry removed, but with no
cycles removed;
    - onlyEGF.tab: does the inversion in 35~45s, it is the previous network with the IKK->ERK link remove,
which removes a cycle;
    - noTABK_EGF.tab: does the inversion in 43s, it is the 'onlyEGF' with extra-links removed

Is this an expected behaviour ? Did I reach some limit of GiNaC on the size or complexity of the expression ?
In my real program, I also need to evaluate the expressions in the inverted matrix, which also seems to take some time
for the examples that are long to invert.
I also tried the inversions in Mathematica, and those matrices are perfectly invertible (you can check by converting
the input files to an adjacency matrix with the python script and executing the commands in 'script_mathematica').
I find surprising that it takes so long, given that the matrices are not that big (and quite sparse)

Thanks for any help regarding this problem,
Mathurin Dorel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.cebix.net/pipermail/ginac-list/attachments/20160509/9d52b37b/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ginac_inversion_error_dorel.zip
Type: application/zip
Size: 54193 bytes
Desc: ginac_inversion_error_dorel.zip
URL: <http://www.cebix.net/pipermail/ginac-list/attachments/20160509/9d52b37b/attachment-0002.zip>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: examples_ginac.zip
Type: application/zip
Size: 2766 bytes
Desc: examples_ginac.zip
URL: <http://www.cebix.net/pipermail/ginac-list/attachments/20160509/9d52b37b/attachment-0003.zip>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: to_mathematica_adm.py
Type: text/x-python
Size: 570 bytes
Desc: to_mathematica_adm.py
URL: <http://www.cebix.net/pipermail/ginac-list/attachments/20160509/9d52b37b/attachment-0001.py>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: script_mathematica
Type: application/octet-stream
Size: 196 bytes
Desc: script_mathematica
URL: <http://www.cebix.net/pipermail/ginac-list/attachments/20160509/9d52b37b/attachment-0001.obj>