Opened 8 months ago

Last modified 13 days 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


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 8 months ago by GMS

Description: modified (diff)

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

Cc: Martin Albrecht added
Priority: majorcritical

comment:3 Changed 8 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 8 months ago by GMS

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

However, all checks fail for M4RIE.




Last edited 8 months ago by GMS (previous) (diff)

comment:5 Changed 8 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 7 months ago by GMS

M4RIE works correctly on an Apple Silicon M1 Mac under macOS 12.3 (Monterey) with Xcode 13.3 (see 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 6 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 6 months ago by GMS

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

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

Milestone: sage-9.6sage-9.7

comment:10 Changed 13 days ago by Matthias Köppe

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