Sage 3.0.5/3.0.6.alpha0: doctest failure in ssmod.py

[mabshoff]

Hi,

I hit the following doctest failure in Sage 3.0.5/3.0.6.alpha0:

sage -t -long devel/sage/sage/modular/ssmod/ssmod.py
**********************************************************************
File "/scratch/mabshoff/release-cycle/sage-3.0.6.alpha0/tmp/ssmod.py",
line 14:
sage: D[:3]
Expected:
[
(Vector space of degree 33 and dimension 1 over Finite Field of
size 97
Basis matrix:
[ 0 0 0 1 96 96 1 96 96 0 2 96 96 0 1 0 1 2 95 0 1
1 0 1 0 95 0 96 95 1 96 0 2], True),
(Vector space of degree 33 and dimension 1 over Finite Field of
size 97
Basis matrix:
[ 0 1 96 75 16 81 22 17 17 0 0 80 80 1 16 40 74 0 0 96 81 23
57 74 0 0 0 24 0 23 73 0 0], True),
(Vector space of degree 33 and dimension 1 over Finite Field of
size 97
Basis matrix:
[ 0 1 96 90 90 7 7 6 91 0 0 91 6 13 7 0 91 0 0 84 90
6 0 6 0 0 0 90 0 91 7 0 0], True)
]
Got:
[
(Vector space of degree 33 and dimension 0 over Finite Field of
size 97
Basis matrix:
[], True),
(Sparse vector space of degree 33 and dimension 12 over Finite
Field of size 97
Basis matrix:
[ 1 0 0 0 0 0 0 0 0 0 0 0 65 15 3 52 25 45 94 79 81 74
65 88 29 13 2 8 38 69 23 75 80]
[ 0 1 0 0 0 0 0 0 0 0 0 0 93 65 51 90 69 12 16 63 86 58
11 60 64 1 73 81 21 6 63 53 49]
[ 0 0 1 0 0 0 0 0 0 0 0 0 5 90 42 3 83 95 4 22 44 54
32 12 89 17 41 18 67 30 3 70 94]
[ 0 0 0 1 0 0 0 0 0 0 0 0 19 89 93 10 17 95 59 8 59 90
69 9 61 23 74 76 17 86 87 5 36]
[ 0 0 0 0 1 0 0 0 0 0 0 0 29 10 12 37 78 20 64 60 33 25
24 14 59 85 4 61 34 51 60 30 86]
[ 0 0 0 0 0 1 0 0 0 0 0 0 19 71 82 94 82 35 95 10 49 56
25 60 59 1 27 60 90 37 70 29 50]
[ 0 0 0 0 0 0 1 0 0 0 0 0 49 32 61 16 26 5 29 87 59 91
86 14 41 37 58 69 80 59 5 46 56]
[ 0 0 0 0 0 0 0 1 0 0 0 0 3 11 85 67 70 42 30 37 24
21 0 74 54 28 17 30 37 86 27 22 46]
[ 0 0 0 0 0 0 0 0 1 0 0 0 25 49 19 4 53 89 56 76 13 6
57 10 37 90 81 9 53 74 48 74 13]
[ 0 0 0 0 0 0 0 0 0 1 0 0 3 77 83 63 11 76 52 72 61 60
56 47 60 56 81 93 86 28 65 48 59]
[ 0 0 0 0 0 0 0 0 0 0 1 0 73 1 72 85 92 48 84 24 31 95
84 24 93 35 22 46 23 7 46 55 66]
[ 0 0 0 0 0 0 0 0 0 0 0 1 9 26 59 64 33 6 59 80 2 79
79 35 38 10 34 90 27 11 75 39 73], True),
(Sparse vector space of degree 33 and dimension 20 over Finite
Field of size 97
Basis matrix:
20 x 33 sparse matrix over Finite Field of size 97, True)
]
**********************************************************************
File "/scratch/mabshoff/release-cycle/sage-3.0.6.alpha0/tmp/ssmod.py",
line 26:
sage: len(D)
Expected:
9
Got:
3
**********************************************************************
1 items had failures:
2 of 17 in __main__.example_0
***Test Failed*** 2 failures.

Andrezj did also hit it once with Sage 3.0.4 or 3.0.5, but he could
not reproduce it. I am also unable to reproduce this reliably, but I
ran the ssmod.py doctest about 110 times and hit it twice. So could
somebody with the mathematical background tell me if this is a bad,
very bad or very, very bad. Any ideas if FLINT could be involved here?
We ship 1.0.11 which according to Bill Hart has a known buglet/corner
case we could hit. There is a new 1.0.12 release out there which fixes
that bug, so I am not sure how much time I should investigate here to
attempt to find something.

Thoughts?

Cheers,

Michael

[Craig Citro]

This is bad, in the sense that it's wrong. What machine was this
happening on? Did you try running this same test 100 or so times with
3.0.3 (before the new FLINT)?

It might be worth upgrading FLINT anyway -- someone else could be
hitting the same corner case, maybe in a non-doctest fashion ...

-cc

[Andrzej Giniewicz]

Hi,

On Thu, Jul 17, 2008 at 2:39 AM, Craig Citro <craig...@gmail.com> wrote:
>
> This is bad, in the sense that it's wrong. What machine was this
> happening on?

in my case it's AMD Athlon from "Barton age", there's cpuinfo:

processor : 0
vendor_id : AuthenticAMD
cpu family : 6
model : 10
model name : AMD Athlon(tm) XP 2600+
stepping : 0
cpu MHz : 2091.162
cache size : 256 KB
fdiv_bug : no
hlt_bug : no
f00f_bug : no
coma_bug : no
fpu : yes
fpu_exception : yes
cpuid level : 1
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge
mca cmov pat pse36 mmx fxsr sse syscall mmxext 3dnowext 3dnow up ts
bogomips : 4186.95
clflush size : 32

Operating system is current Arch Linux 32 bit, so:
GCC 4.3.1 (patched to snapshot from 2008 06 26), GlibC 2.8, Kernel 2.6.25.11

if there is anything I can do to help test it some more, you can count on me,

cheers,
Andrzej.

[mabshoff]

On Jul 16, 6:49 pm, "Andrzej Giniewicz" <ggi...@gmail.com> wrote:
> Hi,

Hi,

> On Thu, Jul 17, 2008 at 2:39 AM, Craig Citro <craigci...@gmail.com> wrote:
>
> > This is bad, in the sense that it's wrong. What machine was this
> > happening on?
>
> in my case it's AMD Athlon from "Barton age", there's cpuinfo:

I think it is independent of the CPU type. I ran ssmod.py 150 times on
sage.math with 3.0.4 (my valgrind special) and I got two failures:


3.0.4-vg: twice in 150 runs

sage -t -long devel/sage/sage/modular/ssmod/ssmod.py
**********************************************************************

File "/scratch/mabshoff/release-cycle/sage-3.0.4-vg/tmp/ssmod.py",

line 14:
sage: D[:3]
Expected:
[
(Vector space of degree 33 and dimension 1 over Finite Field of
size 97
Basis matrix:
[ 0 0 0 1 96 96 1 96 96 0 2 96 96 0 1 0 1 2 95 0 1
1 0 1 0 95 0 96 95 1 96 0 2], True),
(Vector space of degree 33 and dimension 1 over Finite Field of
size 97
Basis matrix:
[ 0 1 96 75 16 81 22 17 17 0 0 80 80 1 16 40 74 0 0 96 81 23
57 74 0 0 0 24 0 23 73 0 0], True),
(Vector space of degree 33 and dimension 1 over Finite Field of
size 97
Basis matrix:
[ 0 1 96 90 90 7 7 6 91 0 0 91 6 13 7 0 91 0 0 84 90
6 0 6 0 0 0 90 0 91 7 0 0], True)
]
Got:
[
(Vector space of degree 33 and dimension 0 over Finite Field of
size 97
Basis matrix:
[], True),

(Sparse vector space of degree 33 and dimension 8 over Finite

Field of size 97
Basis matrix:

[ 1 0 0 0 0 0 0 0 78 55 59 6 76 85 61 87 10 26 51 29 79 46
51 17 36 45 19 31 88 13 52 50 73]
[ 0 1 0 0 0 0 0 0 18 21 87 47 6 94 96 93 92 51 16 78 77 69
71 25 61 20 15 77 8 60 72 50 88]
[ 0 0 1 0 0 0 0 0 1 78 76 71 33 92 79 61 69 37 49 28 27 64
83 58 68 60 52 86 80 57 75 69 41]
[ 0 0 0 1 0 0 0 0 43 55 44 23 77 24 74 28 37 71 36 15 0 24
58 80 65 70 73 54 54 71 75 96 92]
[ 0 0 0 0 1 0 0 0 49 58 10 44 75 30 29 64 42 3 19 50 51 58
18 50 83 0 39 38 17 56 45 1 49]
[ 0 0 0 0 0 1 0 0 47 76 15 0 48 38 39 62 17 13 60 54 0 6
76 52 68 42 81 7 31 96 34 65 42]
[ 0 0 0 0 0 0 1 0 8 24 53 29 48 93 27 10 26 18 30 41 7
39 1 42 57 3 11 7 17 2 6 76 44]
[ 0 0 0 0 0 0 0 1 8 3 90 32 13 92 79 13 96 56 2 84 62 73
67 9 68 12 54 12 38 44 74 79 16], True),
(Sparse vector space of degree 33 and dimension 24 over Finite

Field of size 97
Basis matrix:

24 x 33 sparse matrix over Finite Field of size 97, True)
]
**********************************************************************
File "/scratch/mabshoff/release-cycle/sage-3.0.4-vg/tmp/ssmod.py",

line 26:
sage: len(D)
Expected:
9
Got:
3
**********************************************************************
1 items had failures:
2 of 17 in __main__.example_0

sage -t -long devel/sage/sage/modular/ssmod/ssmod.py
**********************************************************************

File "/scratch/mabshoff/release-cycle/sage-3.0.4-vg/tmp/ssmod.py",

line 14:
sage: D[:3]
Expected:
[
(Vector space of degree 33 and dimension 1 over Finite Field of
size 97
Basis matrix:
[ 0 0 0 1 96 96 1 96 96 0 2 96 96 0 1 0 1 2 95 0 1
1 0 1 0 95 0 96 95 1 96 0 2], True),
(Vector space of degree 33 and dimension 1 over Finite Field of
size 97
Basis matrix:
[ 0 1 96 75 16 81 22 17 17 0 0 80 80 1 16 40 74 0 0 96 81 23
57 74 0 0 0 24 0 23 73 0 0], True),
(Vector space of degree 33 and dimension 1 over Finite Field of
size 97
Basis matrix:
[ 0 1 96 90 90 7 7 6 91 0 0 91 6 13 7 0 91 0 0 84 90
6 0 6 0 0 0 90 0 91 7 0 0], True)
]
Got:
[
(Vector space of degree 33 and dimension 0 over Finite Field of
size 97
Basis matrix:
[], True),

(Sparse vector space of degree 33 and dimension 9 over Finite

Field of size 97
Basis matrix:

[ 1 0 0 0 0 0 0 0 0 34 40 62 51 59 46 74 64 57 82 74 77 80
90 80 73 87 66 33 20 47 30 19 45]
[ 0 1 0 0 0 0 0 0 0 17 32 57 79 31 36 48 32 82 41 17 82 91
53 10 87 49 6 84 51 2 93 44 25]
[ 0 0 1 0 0 0 0 0 0 23 79 30 53 62 8 48 34 15 17 10 78 2
70 30 28 89 34 19 72 44 62 87 78]
[ 0 0 0 1 0 0 0 0 0 72 53 11 4 87 88 25 92 71 9 95 65 90
91 55 43 33 76 31 22 79 2 1 84]
[ 0 0 0 0 1 0 0 0 0 89 24 91 61 89 88 5 51 74 17 24 82 39
91 83 28 58 31 27 38 33 21 76 39]
[ 0 0 0 0 0 1 0 0 0 83 29 29 48 78 12 18 26 78 44 25 84 8
35 3 60 45 19 95 81 46 58 16 87]
[ 0 0 0 0 0 0 1 0 0 36 7 69 96 90 32 78 69 40 54 20 5
6 5 36 22 80 61 95 16 66 45 25 50]
[ 0 0 0 0 0 0 0 1 0 53 35 63 28 20 0 77 17 44 16 24 3 69
37 52 4 95 90 3 57 52 14 92 17]
[ 0 0 0 0 0 0 0 0 1 92 29 68 90 14 1 43 4 69 51 12 74 19
12 59 8 48 52 40 38 41 72 9 30], True),
(Sparse vector space of degree 33 and dimension 23 over Finite

Field of size 97
Basis matrix:

23 x 33 sparse matrix over Finite Field of size 97, True)
]
**********************************************************************
File "/scratch/mabshoff/release-cycle/sage-3.0.4-vg/tmp/ssmod.py",

line 26:
sage: len(D)
Expected:
9
Got:
3
**********************************************************************
1 items had failures:
2 of 17 in __main__.example_0

Does anyone see a pattern?

<SNIP>

> if there is anything I can do to help test it some more, you can count on me,
>
> cheers,
> Andrzej.

Besides FLINT there is always the possibility that LinBox is
involved :). I do not have a 3.0.3 tree, so I am building one now.

Cheers,

Michael

[mabshoff]

Ok, here is what I found out last night:

* 3.0.3 runs the test 200 times without failing it once
* 3.0.4 with the new FLINT 1.0.13 fails 8 ought of 500 tests.

So we are given a couple possibilities:

* There is an algorithmic issue in ssmod somewhere or some
algorithmic issue got exposed somehow in 3.0.4+
* There is an undiscovered bug in LinBox
* There is an undiscovered bug in FLINT
* none of the above
* all of the above

Cheers,

Michael

[mabshoff]

After looking at the code William has conjectured that it is very
likely charpoly mod p that fails here. We update Linbox in 3.0.3-
>3.0.4, so that fits the bill. This issue is now #3671. To debug this
we can compute the charpoly with LinBox and the generic code for a
large number of random inputs and compare. According to William the
speed difference between generic code and LinBox for the example in
ssmod (32 by 32 matrices) won't be too large.

If you have any (alternate) theories what goes wrong here please let
us know.

> Cheers,
>
> Michael

Cheers,

Michae

[Clement Pernet]

I am looking into it.

Applying the patch at
http://sage.math.washington.edu/home/pernet/Patches/charpoly_LUK.patch

will disable the current probablistic charpoly algorithm.
This could help diagnose the origin of the bug.

Cheers

Clement

mabshoff a écrit :

[mabshoff]

On Jul 18, 12:24 pm, Clement Pernet <clement.per...@gmail.com> wrote:

Hi Clement,

> I am looking into it.

Thanks. We are still not 100% certain that the probabilistic charpoly
mod p is at fault here, but it can't hurt to take a look.

> Applying the patch athttp://sage.math.washington.edu/home/pernet/Patches/charpoly_LUK.patch

>
> will disable the current probablistic charpoly algorithm.
> This could help diagnose the origin of the bug.

I have applied the patch and rebuild LinBox and started running the
test 500 times to see. Can you guess if/how much this patch does
affect performance for charpoly mod p?

Some data points: I could never get valgrind to detect any problem
with ssmod.py, but since it took about 2200 seconds in sage.math for
one round that is not so surprising since the sample set was so small.

> Cheers
>
> Clement

Cheers,

Michael

[Clement Pernet]

<snip>

> I have applied the patch and rebuild LinBox and started running the
> test 500 times to see. Can you guess if/how much this patch does
> affect performance for charpoly mod p?
>

For the dimensions you are considering (and up to a thousand) I don't
expect any performance loss.
But the probabilistic alg improves on larger matrices and gets
asymptotically better (the best algorithm indeed!)

I'll let you know when I've made progress on this one.

Clement

[mabshoff]

On Jul 18, 3:59 pm, Clement Pernet <clement.per...@gmail.com> wrote:
> <snip>> I have applied the patch and rebuild LinBox and started running the
> > test 500 times to see. Can you guess if/how much this patch does
> > affect performance for charpoly mod p?
>
> For the dimensions you are considering (and up to a thousand) I don't
> expect any performance loss.
> But the probabilistic alg improves on larger matrices and gets
> asymptotically better (the best algorithm indeed!)
>
> I'll let you know when I've made progress on this one.

Cool. ssmod.py passes 500 doctests in a row with the patch applied.

> Clement

Re performance:

The old code, i.e. non mod-p algorithm:

sage: A = random_matrix(GF(997),500)
sage: time p=A.charpoly()
CPU times: user 1.42 s, sys: 0.06 s, total: 1.48 s
Wall time: 1.51 s
sage: A = random_matrix(GF(997),1000)
sage: time p=A.charpoly()
CPU times: user 9.24 s, sys: 0.08 s, total: 9.32 s
Wall time: 9.33 s
sage: A = random_matrix(GF(997),1500)
sage: time p=A.charpoly()
CPU times: user 30.74 s, sys: 0.24 s, total: 30.98 s
Wall time: 30.98 s
sage: A = random_matrix(GF(997),2000)
sage: time p=A.charpoly()
CPU times: user 64.48 s, sys: 0.36 s, total: 64.83 s
Wall time: 64.83 s
sage: A = random_matrix(GF(997),3000)
sage: time p=A.charpoly()
CPU times: user 208.93 s, sys: 0.78 s, total: 209.71 s
Wall time: 209.78 s
sage: A = random_matrix(GF(997),4000)
sage: time p=A.charpoly()
CPU times: user 512.62 s, sys: 1.29 s, total: 513.91 s
Wall time: 513.99 s
sage:

With the old modp code:

sage: A = random_matrix(GF(997),500)
sage: time p=A.charpoly()
CPU times: user 2.12 s, sys: 0.04 s, total: 2.16 s
Wall time: 2.26 s
sage: A = random_matrix(GF(997),1000)
sage: time p=A.charpoly()
CPU times: user 9.21 s, sys: 0.12 s, total: 9.34 s
Wall time: 9.34 s
sage: A = random_matrix(GF(997),1500)
sage: time p=A.charpoly()
CPU times: user 30.39 s, sys: 0.23 s, total: 30.62 s
Wall time: 30.71 s
sage: A = random_matrix(GF(997),2000)
sage: time p=A.charpoly()
CPU times: user 74.39 s, sys: 0.40 s, total: 74.79 s
Wall time: 74.79 s
sage: A = random_matrix(GF(997),3000)
sage: time p=A.charpoly()
CPU times: user 178.98 s, sys: 0.96 s, total: 179.94 s
Wall time: 180.05 s
sage: A = random_matrix(GF(997),4000)
sage: time p=A.charpoly()
CPU times: user 518.67 s, sys: 1.46 s, total: 520.13 s
Wall time: 520.16 s

So I guess we can live with the "slow" code for a point release or
two.

Cheers,

Michael