#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:

Status badges

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 jhpalmieri

  • Cc jhpalmieri added

comment:2 Changed 16 months ago by jhpalmieri

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 about m4rie except that it does matrix manipulations over the fields GF(2^k) for 2 <= k <= 10.)

comment:3 Changed 16 months ago by jhpalmieri

  • Cc malb added

comment:4 Changed 16 months ago by dimpase

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 dimpase

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 jhpalmieri

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 dimpase

Should be fixed by the new patch on #29026 Please verify it fixes the issue.

comment:8 Changed 15 months ago by gh-DaveWitteMorris

Yes, #29026 got rid of the problem in my testing (like it did for #28944). I tried a few hundred times, and never got False or an error. Thank you!

comment:9 Changed 15 months ago by jhpalmieri

  • 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 jhpalmieri

  • Reviewers set to John Palmieri
  • Status changed from needs_review to positive_review

comment:11 Changed 15 months ago by chapoton

  • Resolution set to duplicate
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.