Opened 16 months ago
Closed 15 months ago
#28970 closed defect (duplicate)
Smith normal form over GF(4) is sometimes incorrect on Mac OS
Reported by: | gh-DaveWitteMorris | Owned by: | |
---|---|---|---|
Priority: | critical | Milestone: | sage-duplicate/invalid/wontfix |
Component: | linear algebra | Keywords: | |
Cc: | jhpalmieri, malb | Merged in: | |
Authors: | Reviewers: | John Palmieri | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
This is split off from the discussion at #28944.
I am using a Python 3 build of 9.0 on Mac OS 10.15.1. The following code should always print True.
M = random_matrix(GF(4), 100, 100) for k in range(50): S,U,V = M.smith_form() print(S == U * M * V) # True
Instead, in any given run, I always get False at least a few times. And the loop usually does not get through the entire set of 50, because it is terminated by NotImplementedError
(or, occasionally, a sage crash like the one reported in #28944). We are using the same matrix for the entire run, so the output should not be random.
@jhpalmieri reported in #28944 that he has seen this issue on OS X 10.14.6, but not on an Ubuntu virtual machine. It also did not show up in my limited testing on CoCalc
. So (like #28944) this seems to be a Mac OS issue.
I do not see this problem when GF(4)
is replaced with a different finite field. Fields of odd order do not seem to have any problems at all, but fields of characteristic 2 crash as reported for GF(2)
in #28944.
I understand the superficial cause of the NotImplementedError
, but not the underlying cause. The value of t[0,0]
is always nonzero at the start of the following code snippet from the definition of smith_form
.
# now recurse: t now has a nonzero entry at 0,0 and zero entries in the rest # of the 0th row and column, so we apply smith_form to the smaller submatrix mm = t.submatrix(1,1) if transformation: dd, uu, vv = mm.smith_form(transformation=True) else: dd = mm.smith_form(transformation=False) mone = self.new_matrix(1, 1, [1]) d = dd.new_matrix(1,1,[t[0,0]]).block_sum(dd)
However, executing mm.smith_form
sometimes changes the value of t[0,0]
, so that t[0,0]
is 0 in the definition of d
. (In the cases where the value of t[0,0]
is changed, it seems to always be changed to 0.) This 0 in the top left corner of d
causes a NotImplementedError
. (The patch in ticket #28967 eliminates the NotImplementedError
, by providing a definition of inverse_mod
, but the value returned by smith_form
will be incorrect, because the value of t[0,0]
is wrong.)
How can mm.smith_form
be changing the value of t
?
Change History (11)
comment:1 Changed 16 months ago by
- Cc jhpalmieri added
comment:2 Changed 16 months ago by
comment:3 Changed 16 months ago by
- Cc malb added
comment:4 Changed 16 months ago by
m4ri(e) now may come from "the system": https://trac.sagemath.org/ticket/28342
Do you build m4ri(e), or use one from Homebrew (or something like this)?
comment:5 Changed 16 months ago by
Assuming you use Sage's m4ri(e): Try doing internal tests of m4ri and m4rie:
SAGE_CHECK=yes ./sage -f m4ri SAGE_CHECK=yes ./sage -f m4rie
and see whether you manage to get errors there.
comment:6 Changed 15 months ago by
I'm using Sage's m4ri and m4rie, and both pass their test suites. There are warnings in the log files, but nothing jumps out at me. For m4rie, I saw this:
m4rie/strassen.c:52:7: warning: absolute value function 'abs' given an argument of type 'long' but has parameter of type 'int' which may cause truncation of value [-Wabsolute-value] if (CLOSER(m, m/2, cutoff) || CLOSER(k, k/2, cutoff) || CLOSER(n, n/2, cutoff)) { ^ m4rie/strassen.c:31:29: note: expanded from macro 'CLOSER' #define CLOSER(a,b,target) (abs((long)a-(long)target)<abs((long)b-(long)target)) ^ m4rie/strassen.c:52:7: note: use function 'labs' instead
so I patched m4rie to change abs
to labs
. It didn't affect the behavior.
comment:7 Changed 15 months ago by
Should be fixed by the new patch on #29026 Please verify it fixes the issue.
comment:8 Changed 15 months ago by
comment:9 Changed 15 months ago by
- Milestone changed from sage-9.1 to sage-duplicate/invalid/wontfix
- Status changed from new to needs_review
Looks good to me, too. Let's close this as a duplicate of #29026.
comment:10 Changed 15 months ago by
- Reviewers set to John Palmieri
- Status changed from needs_review to positive_review
comment:11 Changed 15 months ago by
- Resolution set to duplicate
- Status changed from positive_review to closed
First, I asked about this on sage-devel, so we'll see if anyone can help. Second, I tried with some other fields: cardinality 2, 3, 4, 5, 8, and 9. I only see the problem with GF(4) or GF(8), although GF(9) is slow enough that I didn't want to try too many iterations. I wonder if there is some problem with
m4rie
on OS X. (I don't know anything aboutm4rie
except that it does matrix manipulations over the fieldsGF(2^k)
for2 <= k <= 10
.)