Strange performance of matdet

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

To: pari-dev@pari.math.u-bordeaux.fr
Subject: Strange performance of matdet
From: Jernej Azarija <stdazi@gmail.com>
Date: Fri, 7 Sep 2012 13:56:32 +0200
Delivery-date: Fri, 07 Sep 2012 13:56:40 +0200
Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:date:message-id:subject:from:to:content-type; bh=ap35Kx2y1Iz6HB+zX1z2TubpBfb7RcPTQzscnDpGNu4=; b=TW+tZ19KfaHDst2Yu87jzrxK0Xx6dLETzT6Mu+zT1coLu4AsVp2IJzCy9hTygG+AiW S6nX3e9P6ot8qFAUD1KExQ4+DpZJApYzvj1B1l75WG7M/Ulm88/2zzv3oIXi9npgMRWI D2vYDbBLltvOSqucB7iPEnHk5LTpH+Z72OxU96NP9DGt0a6V+qpEaK54Hj7+2jnubYNy N5+gEgjU9Qn1BPVykTrmbzHGiXdCkwg0/uBzTJ4iRx1emKMLdwUO4AD8joLxH94Q8lpJ u80DamBBAedOq5POOWR4DzZFafkMgMSeLm/q5axth7SM3vnxxKgYRK+K80uLo8f/fWR2 eyqA==

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

Follow-Ups:
- Re: Strange performance of matdet
  - From: Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr>

Prev by Date: Re: number of lines of matrices
Next by Date: matdet regression
Previous by thread: Re: number of lines of matrices
Next by thread: Re: Strange performance of matdet
Index(es):
- Date
- Thread