Jernej Azarija on Fri, 07 Sep 2012 13:56:40 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Strange performance of matdet


Hello!

This question  is motivated by the following discussion on sage
https://groups.google.com/forum/?hl=en-GB&fromgroups=#!topic/sage-devel/uneXpZnRs-U
in which it was noted that there exist a symmetric integer 34x34
matrix such that it takes matdet  ~8minutes to compute the answer
while it takes less than a second to compute the determinant using the
classical Gaussian elimination.

The matrix in question is the following:

=====================================
M = [4, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, -1, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0;0, 4, -1, 0, 0, 0, 0, 0, -1,
-1, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0; 0, -1, 4, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, -1, -1, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0;0, 0, 0, 4, 0, 0, 0, -1, 0,
0, 0, -1, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0;-1, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1;0, 0, 0, 0, 0, 4, 0, 0, 0,
0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0,
0, -1, 0;0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, -1, 0, -1, 0, 0, 0,
0, -1, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0;0, 0, 0, -1, 0, 0, 0, 4, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0;0, -1, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0;0, -1, 0, 0, 0, 0, 0, 0, 0, 4,
0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -1,
0, 0;0, 0, -1, 0, 0, -1, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1,
0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0;0, 0, 0, -1, 0, 0, 0, 0, 0, -1,
0, 4, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0,
0;0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, -1, 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, 0, 4, 0, 0, 0, -1, 0, 0, 0, 0, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0;0, -1, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, -1, 0, 4, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1;0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, -1, 0, -1, 0, 0, -1, 0, -1, 0, 0,
0;0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, -1, 0, 0, 0, 0,
0, 0, 0, 0, -1, -1, 0, 0, 0, 0, 0, 0;-1, 0, -1, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, -1, 0, 0, -1, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0;0, 0, -1, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0,
0, 0, 0, -1, 0, 0, 0, -1, 0, 0, 0, 0;-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, -1, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, -1,
0;0, 0, 0, 0, -1, 0, 0, 0, 0, 0, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0,
0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0;0, 0, 0, 0, 0, -1, -1, -1, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 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, -1, 0, 0, 0, 0, 0, 0, 0, 0,
4, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, -1;0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0,
0, 0, -1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 4, -1, 0, 0, 0, 0, 0, 0, 0, 0,
0;0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0,
0, -1, 4, 0, 0, 0, 0, -1, 0, 0, 0, 0;0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, -1, 0, 0, -1, 0, 0, 0, 0, 0, 0, 4, 0, -1, 0, 0, 0, 0, 0,
-1;0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0,
0, 0, 0, 0, 4, 0, -1, 0, 0, -1, 0, 0;0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
-1, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 4, 0, 0, 0, 0, -1,
0;0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, -1, 0, 0, -1, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, -1, 0, 4, 0, 0, 0, 0, 0;0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, -1, -1, 0, 0, 0, 0, -1, 0, 0, 0, 0, 4, 0, -1, 0,
0;-1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0,
-1, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0;0, 0, 0, 0, 0, 0, 0, 0, 0, -1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, -1, 0, 0, -1, 0, 4,
0, 0;0, 0, 0, 0, 0, -1, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0,
0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 4, 0;0, 0, 0, 0, -1, 0, 0, 0, 0, 0,
0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, -1, 0, 0, 0, 0, 0, 0,
0, 4]
=====================================


As I have noticed in the documentation for pari it is usually better
to use classical Gaussian elimination for computing determinants of
matrices with integer entries but is such a difference in
computational time expected?

Could someone explain why it takes so long to compute the answer using
the default algorithm? Is this perhaps some kind of bug?

Best,

Jernej