Error in determinant (serious!)
Nils Bruin
integer matrix. Sometimes, 0 is returned for a full rank matrix. This
is accompanied by some printed error warning, but no exception is
raised. A bug has been filed:
http://sagetrac.org/sage_trac/ticket/498
but given that this actually makes sage return wrong answers, I
thought some extra attention might be due.
mabshoff
[I am CCing Clement Pernet directly (despite him being subscribed) and
adjust the subject to catch his attention. Clement, if you were
following this anyway: my bad ;)]
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
mabshoff
http://linalg.org/projects/linalg/ticket/3
I have updated our ticket description with a link to the LinBox
ticket.
Cheers,
Michael
mabshoff
On Aug 28, 10:31 am, mabshoff <Michael.Absh...@fsmath.mathematik.uni-
dortmund.de> wrote:
> This is actually an open ticket at the LinBox trac: seehttp://linalg.org/projects/linalg/ticket/3
>
> I have updated our ticket description with a link to the LinBox
> ticket.
>
> Cheers,
>
> Michael
With the knowledge that I am about to become annoying (for posting too
often), but I did a little more digging: The determinant of the 8x8
matrix from LinBox's ticket #3 is now computed correctly. So that
ticket can be closed. But with the new problem Matrix from Sage's
ticket #498 valgrind tells me the following:
==30596== Invalid write of size 8
==30596== at 0x1FCFAA6A: void
LinBox::create_MatrixQadic<LinBox::PID_integer,
LinBox::DenseMatrix<LinBox::PID_integer> >(LinBox::PID_intege
r const&, LinBox::DenseMatrix<LinBox::PID_integer> const&, double*,
unsigned long, Integer const&) (in /tmp/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> >::setup(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> >::LiftingContainerBase
<Integer, std::vector<Integer, std::allocator<Integer> >
>(LinBox::PID_integer const&, LinBox::DenseMatrix<LinBox::PID_integer>
const&, std::v
ector<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_intege
r>, 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_integer> const&,
LinBox::BlasBlackbox<LinBox::Modular<doub
le> > const&, std::vector<Integer, std::allocator<Integer> > const&,
Integer const&) (in /tmp/Work2/sage-2.8.1/sage-2.8.1/local/lib/
liblinboxw
rap.so.0.0.0)
==30596== by 0x1FD0583B: LinBox::SolverReturnStatus
LinBox::RationalSolver<LinBox::PID_integer, LinBox::Modular<double>,
LinBox::RandomPrim
eIterator,
LinBox::DixonTraits>::solveNonsingular<LinBox::DenseMatrix<LinBox::PID_integer>,
std::vector<Integer, std::allocator<Integer> >, st
d::allocator<Integer> >(std::vector<Integer, std::allocator<Integer>
>&, Integer&, LinBox::DenseMatrix<LinBox::PID_integer> const&,
std::alloc
ator<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_integer, LinBox::Modu
lar<double>, LinBox::RandomPrimeIterator, LinBox::DixonTraits>
>::lastInvariantFactor1<LinBox::DenseMatrix<LinBox::PID_integer>,
std::vector<I
nteger, std::allocator<Integer> > >(std::vector<Integer,
std::allocator<Integer> >, std::vector<Integer,
std::allocator<Integer> >&, LinBox::D
enseMatrix<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_5Field7ElementES8_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_14RingCa
tegories10IntegerTagERKT0_ (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 /tm
p/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
So the problem is a different one than the once fixed.
On another note: William, didn't you merge my valgrind support patch
for Sage 2.8.2? A build from source complains about:
[mabshoff@m940 sage-2.8.2]$ ./sage
----------------------------------------------------------------------
| SAGE Version 2.8.2, Release Date: 2007-08-22 |
| Type notebook() for the GUI, and license() for information. |
----------------------------------------------------------------------
sage:
Exiting SAGE (CPU time 0m0.00s, Wall time 0m1.01s).
[mabshoff@m940 sage-2.8.2]$ ./sage -valgrind
Unknown option: -valgrind
usage: sage [options]
Try 'sage -h' for more information.
Cheers,
Michael
mabshoff
Hello,
Clement Pernet did post a quick workaround for the problem. A new
linbox.spkg is at
http://sage.math.washington.edu/home/mabshoff/linbox-20070828.spkg
It computes the determinant as follows:
sage: M=Matrix(Integers(),20,20,L)
sage: M.det()
3951360
sage: M.rank()
20
Can anybody verify that this is the correct result?
I am rerunning sage -testall at the moment to make sure that nothing
else is negatively affected by the fix.
Once more: kudos to Clement.
Cheers,
Michael
William Stein
> It computes the determinant as follows:
>
> sage: M=Matrix(Integers(),20,20,L)
> sage: M.det()
> 3951360
> sage: M.rank()
> 20
> Can anybody verify that this is the correct result?
Yep, via PARI (also in SAGE):
sage: gp(M).matdet()
3951360
or via the charpoly command:
sage: M.charpoly()[0]
3951360
Thanks!!
>
> I am rerunning sage -testall at the moment to make sure that nothing
> else is negatively affected by the fix.
>
> Once more: kudos to Clement.
>
> Cheers,
>
> Michael
>
>
> >
>
--
William Stein
Associate Professor of Mathematics
University of Washington
http://www.williamstein.org
mabshoff
On Aug 28, 9:16 pm, "William Stein" <wst...@gmail.com> wrote:
> On 8/28/07, mabshoff <Michael.Absh...@fsmath.mathematik.uni-dortmund.de> wrote:
>
> > It computes the determinant as follows:
>
> > sage: M=Matrix(Integers(),20,20,L)
> > sage: M.det()
> > 3951360
> > sage: M.rank()
> > 20
> > Can anybody verify that this is the correct result?
>
> Yep, via PARI (also in SAGE):
>
> sage: gp(M).matdet()
> 3951360
>
> or via the charpoly command:
> sage: M.charpoly()[0]
> 3951360
>
> Thanks!!
>
Great. I should actually use Sage more instead of just hacking around
it. Than I could have done that in a second, too.
>
>
> > I am rerunning sage -testall at the moment to make sure that nothing
> > else is negatively affected by the fix.
>
sage -testall passed.
> > Once more: kudos to Clement.
>
> > Cheers,
>
> > Michael
>
Cheers,
Michael