Karatsuba multiplication of matrices: failed test

[GMS103]

This is for SageMath version 9.5.rc3 built on two M1 Macs, one with macOS 11.6.2 (Big Sur) and the other with macOS 12.1 (Monterey).

One test in

src/sage/matrix/matrix_gf2e_dense.pyx

seems to fail consistently, namely

sage: K.<a> = GF(2^n)
sage: A = random_matrix(K, 50, 50)
sage: B = random_matrix(K, 50, 50)
sage: A._multiply_karatsuba(B) == A._multiply_classical(B)

as soon as n > 2.
In fact, A and B appear to be completely different.

I do not know how to deal with this, but I am available to test.

CC: @malb

Component: linear algebra

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

[malb]

comment:3

Works on my x64 Linux. I assume the underlying reason is that M4RIE relies on some undefined behaviour that works "as expected" on x86-ish architectures? Can you compile M4RIE with all warnings on and then run the tests? Maybe it's already triggered there?

[GMS103]

comment:4

I have been able to compile M4RI and M4RIE (the former is needed for the latter).

However, all checks fail for M4RIE.

See

https://bitbucket.org/malb/m4ri/issues/83/trying-to-compile-on-apple-m1

and

https://bitbucket.org/malb/m4rie/issues/23/trying-to-compile-on-apple-m1

HTH

[malb]

comment:5

So it seems to be an issue with M4RIE but not sure how to debug this. I've asked on sage-devel if others can reproduce it (I assume the answer is "yes", but still).

[GMS103]

comment:6

M4RIE works correctly on an Apple Silicon M1 Mac under macOS 12.3 (Monterey) with Xcode 13.3 (see https://bitbucket.org/malb/m4rie/issues/23/trying-to-compile-on-apple-m1): the test in this ticket succeeds.

The bad news is that Xcode 13.3 is not available for macOS 11.6.5 (Monterey), the last available version being Xcode 13.2.1, which fails as indicated above.

[malb]

comment:7

Thanks for tracking this down. We can compile with a lower optimisation level on those machines with a buggy compiler?

[GMS103]

comment:8

It should be possible, but I do not know how to do it when making SageMath.