Error in <IntegerMatrix.det()>

[nbruin]

Discovered by Thea Gegenberg:

Something goes wrong here. A determinant equal to 0 is returned for a full rank matrix. An error message is printed: "ERROR in reconstruction ?" but no exception is raised.

L=[-32672924, 402859388, -140623668, 430658721, 106946787, 621276047,
-192782447, 431682021, 102255307, 94626176, -34905583, -95358049,
19932420, 123725915, 52076617, -202693998, -104950285, 75183320,
90638691, -10508577, -159993345, 544819075, -205041193, 530536794,
34425198, 812190067, -260981874, 580644585, 123763815, 100094135,
-69769038, -119580389, 66415448, 141833716, 62768834, -269408072,
-133259211, 100392022, 122810015, -14169559, -116742143, 255636730,
-101946387, 229909806, -23983454, 370713224, -122485286, 271167855,
52843557, 36798922, -40542776, -53268126, 45195782, 57579762, 26577120,
-124502451, -59510085, 46572885, 57450083, -6605856, 15000427,
-30582942, 12516546, -26821359, 4119829, -44014478, 14639368, -32285711,
-6171530, -4068360, 4862805, 6668897, -5647699, -6841120, -3067309,
14771590, 7115903, -5537058, -6739292, 775422, 7350404, 230921981,
-76923414, 258735233, 86438125, 362368415, -110372559, 248213386,
62007340, 60606320, -15120637, -56148382, 2793135, 76364724, 31673380,
-117264550, -61940375, 43368039, 52065723, -6050134, -151307549,
78679036, -46266959, 18647207, -117585287, 85433954, -37642136,
80027656, 2018840, -16574471, -34635562, -6981346, 53375886, -7793292,
519003, -33205642, -9545608, 12868856, 17687995, -1966305, -363614357,
1120703653, -426407076, 1075510629, 37584638, 1662076505, -536823334,
1193214389, 250295666, 197458670, -149948886, -243590352, 148290926,
284338202, 126789390, -552585008, -271574842, 206055077, 252487220,
-29112407, -24118132, 125489794, -45531102, 127679943, 19878772,
189727909, -59873328, 133891226, 30235317, 26062022, -13427908,
-28437884, 11088522, 35371542, 15314003, -62344332, -31541764, 23159538,
28169710, -3257928, 23875931, -55361113, 21777071, -50092756, 4072588,
-80196200, 26290253, -58432798, -11789547, -8211985, 8277760, 11589279,
-9463444, -12750488, -5909614, 26780705, 12871707, -9986858, -12330558,
1418788, -123640072, 350287850, -134402037, 331686546, 2311861,
516848375, -167690026, 372647615, 77107961, 59330726, -48837778,
-74960963, 49935779, 86475403, 39012673, -172208210, -84008378,
64235307, 78969119, -9098718, 29206401, -58665698, 23367942, -51628286,
7704232, -84008009, 27841118, -62026237, -12049237, -7882950, 9778971,
11364995, -11528692, -12326307, -6027486, 28258762, 13229006, -10541794,
-13232024, 1518814, -15226123, -162474710, 52643231, -186629243,
-70538436, -257338018, 77581589, -174915120, -44964751, -45100633,
8768165, 39990351, 1319955, -55787679, -23007336, 82911599, 44234087,
-30609520, -36691281, 4268583, -3067101, -187862053, 62406108,
-208934856, -67593203, -293436726, 89390112, -201449078, -50438313,
-48568925, 12749582, 44690794, -3756544, -61132699, -25770007, 94967436,
49821864, -35071658, -42392728, 4922722, -83860746, 387091065,
-141493308, 390611827, 53261700, 584183024, -185296915, 413534644,
91854856, 78421794, -44059309, -86512345, 37363320, 106897933, 46669076,
-192648548, -96693655, 71636948, 87410231, -10100657, -56763493,
123532651, -49071162, 111379401, -11435705, 179568616, -59393552,
131295311, 25428711, 17842335, -20018876, -25373934, 22014146, 27645710,
12901369, -60462971, -28718167, 22624087, 28023128, -3220309, 74635684,
42414796, -4598855, 80612787, 85891705, 84744646, -20275295, 47713903,
20441907, 28852448, 11300266, -16245887, -24534126, 30219206, 10703344,
-24779029, -16921909, 8890606, 9568309, -1154549, -129928022, 450121954,
-169305350, 439469539, 30630839, 672148465, -215901643, 479926644,
102311525, 83254236, -57276284, -99501795, 53823660, 117995313,
51970498, -222955007, -110479289, 83108429, 101494954, -11712185,
-144442660, 396456359, -153843052, 373857888, -1782212, 585684397,
-190815470, 422383108, 85815948, 66107666, -56349192, -86531733,
56862804, 97958280, 43498721, -195572942, -95613139, 73115455, 89344289,
-10295212, 10964325, -5070815, 2648146, -839025, 8356359, -4976355,
2255047, -5129380, -209043, 1262716, 2672540, -558453, -4261247,
1210201, -101067, 2031870, 246414, -752782, -1334683, 146103, 117556641,
-635133625, 229805379, -649558626, -106084208, -963569121, 304047081,
-678780364, -153015989, -133365649, 68083651, 144472798, -54146381,
-180316114, -77858131, 316948599, 160367139, -117807494, -143206514,
16562032]
M=Matrix(Integers(),20,20,L)
M.det()
M.rank()

Component: linear algebra

Issue created by migration from https://trac.sagemath.org/ticket/498

[sagetrac-mabshoff]

comment:1

For the matching discussion in sage-devel see http://groups.google.com/group/sage-devel/t/813495b9968f3ed5

Hello Nils,

a quick grep revealed that this is very likely a problem in LinBox,
specifically somewhere in

linbox/algorithms/rational-reconstruction.h

If LinBox returns an error and if Sage doesn't catch that error I
cannot tell you.

Cheers,

Michael

[sagetrac-mabshoff]

comment:2

This is actually an open ticket at the LinBox trac: see http://linalg.org/projects/linalg/ticket/3

Cheers,

Michael

[sagetrac-mabshoff]

comment:3

Ticket #3 in the LinBox trac has been fixed. This problem is different (even though it also computes a determinant):

==30596== Invalid write of size 8
==30596==    at 0x1FCFAA6A: void LinBox::create_MatrixQadic<LinBox::PID_integer, LinBox::DenseMatrix<LinBox::PID_integer> >(
LinBox::PID_integer const&, LinBox::DenseMatrix<LinBox::PID_integer> const&, double*, unsigned long, Integer const&) (in /tm
p/Work2/sage-2.8.1/sage-2.8.1/local/lib/liblinboxwrap.so.0.0.0)
==30596==    by 0x1FD00819: LinBox::BlasMatrixApplyDomain<LinBox::PID_integer, LinBox::DenseMatrix<LinBox::PID_integer> >::s
etup(Integer) (in /tmp/Work2/sage-2.8.1/sage-2.8.1/local/lib/liblinboxwrap.so.0.0.0)
==30596==    by 0x1FD01BA7: LinBox::LiftingContainerBase<LinBox::PID_integer, LinBox::DenseMatrix<LinBox::PID_integer> >::Li
ftingContainerBase<Integer, std::vector<Integer, std::allocator<Integer> > >(LinBox::PID_integer const&, LinBox::DenseMatrix
<LinBox::PID_integer> const&, std::vector<Integer, std::allocator<Integer> > const&, Integer const&) (in /tmp/Work2/sage-2.8
.1/sage-2.8.1/local/lib/liblinboxwrap.so.0.0.0)
==30596==    by 0x1FD01F41: LinBox::DixonLiftingContainer<LinBox::PID_integer, LinBox::Modular<double>, LinBox::DenseMatrix<
LinBox::PID_integer>, LinBox::BlasBlackbox<LinBox::Modular<double> > >::DixonLiftingContainer<Integer, std::vector<Integer,
std::allocator<Integer> > >(LinBox::PID_integer const&, LinBox::Modular<double> const&, LinBox::DenseMatrix<LinBox::PID_inte
ger> const&, LinBox::BlasBlackbox<LinBox::Modular<double> > const&, std::vector<Integer, std::allocator<Integer> > const&, I
nteger const&) (in /tmp/Work2/sage-2.8.1/sage-2.8.1/local/lib/liblinboxwrap.so.0.0.0)
==30596==    by 0x1FD0583B: LinBox::SolverReturnStatus LinBox::RationalSolver<LinBox::PID_integer, LinBox::Modular<double>,
LinBox::RandomPrimeIterator, LinBox::DixonTraits>::solveNonsingular<LinBox::DenseMatrix<LinBox::PID_integer>, std::vector<In
teger, std::allocator<Integer> >, std::allocator<Integer> >(std::vector<Integer, std::allocator<Integer> >&, Integer&, LinBo
x::DenseMatrix<LinBox::PID_integer> const&, std::allocator<Integer> const&, bool, int) const (in /tmp/Work2/sage-2.8.1/sage-
2.8.1/local/lib/liblinboxwrap.so.0.0.0)
==30596==    by 0x1FD05BE5: Integer& LinBox::LastInvariantFactor<LinBox::PID_integer, LinBox::RationalSolver<LinBox::PID_int
eger, LinBox::Modular<double>, LinBox::RandomPrimeIterator, LinBox::DixonTraits> >::lastInvariantFactor1<LinBox::DenseMatrix
<LinBox::PID_integer>, std::vector<Integer, std::allocator<Integer> > >(std::vector<Integer, std::allocator<Integer> >, std:
:vector<Integer, std::allocator<Integer> >&, LinBox::DenseMatrix<LinBox::PID_integer> const&) const (in /tmp/Work2/sage-2.8.
1/sage-2.8.1/local/lib/liblinboxwrap.so.0.0.0)
==30596==    by 0x1FD06494: _ZN6LinBox11lif_cra_detINS_11DenseMatrixINS_11PID_integerEEENS_15HybridSpecifierEEERNT_5Field7El
ementES8_RKS5_RKNS_14RingCategories10IntegerTagERKT0_ (in /tmp/Work2/sage-2.8.1/sage-2.8.1/local/lib/liblinboxwrap.so.0.0.0)
==30596==    by 0x1FD06DB5: _ZN6LinBox3detINS_11DenseMatrixINS_11PID_integerEEENS_15HybridSpecifierEEERNT_5Field7ElementES8_
RKS5_RKNS_14RingCategories10IntegerTagERKT0_ (in /tmp/Work2/sage-2.8.1/sage-2.8.1/local/lib/liblinboxwrap.so.0.0.0)
==30596==    by 0x1FD06DEF: _ZN6LinBox3detINS_11DenseMatrixINS_11PID_integerEEENS_15HybridSpecifierEEERNT_5Field7ElementES8_
RKS5_RKT0_ (in /tmp/Work2/sage-2.8.1/sage-2.8.1/local/lib/liblinboxwrap.so.0.0.0)
==30596==    by 0x1FD06E1B: _ZN6LinBox3detINS_11DenseMatrixINS_11PID_integerEEEEERNT_5Field7ElementES7_RKS4_ (in /tmp/Work2/
sage-2.8.1/sage-2.8.1/local/lib/liblinboxwrap.so.0.0.0)
==30596==    by 0x1FC6FCD2: linbox_integer_dense_det (in /tmp/Work2/sage-2.8.1/sage-2.8.1/local/lib/liblinboxwrap.so.0.0.0)
==30596==    by 0x1F98FDAE: __pyx_f_6linbox_20Linbox_integer_dense_det(_object*, _object*, _object*) (linbox.cpp:1351)
==30596==  Address 0x27A9F6C8 is not stack'd, malloc'd or (recently) free'd

I have reported this to linbox-use.

Cheers,

Michael

[sagetrac-mabshoff]

comment:5

Clement Pernet is investigating the issue. Once he has a patch we will probably just patch the current LinBox.spkg.

Cheers,

Michael

[sagetrac-mabshoff]

comment:7

Due to some oversight the new spkg never made it in the 2.8.3 release. We now have an updated spkg with a proper fix (the one above was just a workaround which reduce performance significantly). For more see ticket #581.

Cheers,

Michael