Opened 10 months ago

Last modified 2 months ago

#33212 new defect

Karatsuba multiplication of matrices: failed test

Reported by: GMS Owned by:
Priority: critical Milestone: sage-9.8
Component: linear algebra Keywords:
Cc: Martin Albrecht Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by GMS)

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.

Change History (10)

comment:1 Changed 10 months ago by GMS

Description: modified (diff)

comment:2 Changed 10 months ago by Matthias Köppe

Cc: Martin Albrecht added
Priority: majorcritical

comment:3 Changed 10 months ago by Martin Albrecht

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?

comment:4 Changed 10 months ago by GMS

Version 0, edited 10 months ago by GMS (next)

comment:5 Changed 10 months ago by Martin Albrecht

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).

comment:6 Changed 8 months ago by GMS

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.

comment:7 Changed 8 months ago by Martin Albrecht

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

comment:8 Changed 8 months ago by GMS

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

comment:9 Changed 7 months ago by Matthias Köppe

Milestone: sage-9.6sage-9.7

comment:10 Changed 2 months ago by Matthias Köppe

Milestone: sage-9.7sage-9.8
Note: See TracTickets for help on using tickets.