Opened 7 years ago

Closed 7 years ago

#16306 closed defect (fixed)

Replace =0 by is_zero() in test for matrix being alternating

Reported by: darij Owned by:
Priority: trivial Milestone: sage-6.3
Component: linear algebra Keywords:
Cc: nbruin, stumpc5 Merged in:
Authors: Darij Grinberg Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: f36f0ad (Commits) Commit: f36f0ad401050a0ea824acd75be32d92c0b832c1
Dependencies: Stopgaps:

Description (last modified by darij)

This branch does a couple small improvements to src/sage/matrix/matrix0.pyx, the most important one being a replacement of "== 0" by "== zero" since there are rings R whose zero element is not the same as R(0). (Two grammar errors in the doc are also fixed.)

Change History (21)

comment:1 Changed 7 years ago by darij

  • Status changed from new to needs_review

comment:2 Changed 7 years ago by darij

  • Cc nbruin stumpc5 added

comment:3 Changed 7 years ago by vdelecroix

Hi Darij,

1) Could you provide examples of rings for which the test fails? It is not clear to me why we need this and if you do not want that such bug reproduces you need to test it. More precisely, in the documentation write something along the lines of

In the following example, we show that we solve the issue in :trac:`16306` is solved::

    sage: a_nice_example()
    Hey!

2) why not

-            if self.get_unsafe(i,i) != 0:
+            if self.get_unsafe(i,i):

Do we know that __nonzero__ always does what we expect?

Vincent

Last edited 7 years ago by vdelecroix (previous) (diff)

comment:4 follow-up: Changed 7 years ago by darij

1) I don't have good examples. We have semirings where 0 is not the zero in Sage (try TropicalSemiring(ZZ)), but this particular method doesn't make much sense for these. This is more an issue of principle: We might eventually get rings like Grothendieck's lambda-rings (the ring of power series over a given ring K, with multiplication of power series as addition, and a weirder multiplication -- and, before you ask, there are finite-dimensional quotients of this, so it's not all lazy power series, so testing for zeroness does make sense), on which there will suddenly be a lot of failing code due to the fact that the coerce of 1 (not the coerce of 0) is the zero element. Better to fix as many of these issues as we can right now.

However, in most examples I've tried, is_zero is faster than == 0 due to the coercion that has to be resolved for the latter.

2) I don't know. I wouldn't make an assumption on the boolean coerce of a ring element. But maybe I could...

Last edited 7 years ago by darij (previous) (diff)

comment:5 in reply to: ↑ 4 Changed 7 years ago by vdelecroix

Replying to darij:

1) I don't have good examples. We have semirings where 0 is not the zero in Sage (try TropicalSemiring(ZZ)), but this particular method doesn't make much sense for these. This is more an issue of principle: We might eventually get rings like Grothendieck's lambda-rings (the ring of power series over a given ring K, with multiplication of power series as addition, and a weirder multiplication -- and, before you ask, there are finite-dimensional quotients of this, so it's not all lazy power series, so testing for zeroness does make sense), on which there will suddenly be a lot of failing code due to the fact that the coerce of 1 (not the coerce of 0) is the zero element. Better to fix as many of these issues as we can right now.

So, I do not understand the description of the ticket. You wrote Not all rings R have their zero element equal to R(0). But now that I asked for an example, you say that no such ring exists.

However, in most examples I've tried, is_zero is faster than == 0 due to the coercion that has to be resolved for the latter.

Ok. Looks like a better argument than claiming that there are other rings. Could you provide timings then?

2) I don't know. I wouldn't make an assumption on the boolean coerce of a ring element. But maybe I could...

No. I was just asking. Because, if you care about speed, this is by far the fastest.

Vincent

comment:6 Changed 7 years ago by darij

I hope you will agree that "all rings" and "all rings in Sage" are two rather different things... :)

Some timings on zero elements:

sage: %timeit ZZ(1) == 0
1000000 loops, best of 3: 419 ns per loop
sage: %timeit ZZ(1).is_zero()
1000000 loops, best of 3: 389 ns per loop
sage: %timeit QQ(1) == 0
100000 loops, best of 3: 2.15 µs per loop
sage: %timeit QQ(1).is_zero()
1000000 loops, best of 3: 853 ns per loop
sage: P.<x> = PolynomialRing(QQ)
sage: %timeit x == 0
100000 loops, best of 3: 2.76 µs per loop
sage: %timeit x.is_zero()
1000000 loops, best of 3: 223 ns per loop
sage: Sym = SymmetricFunctions(QQ); e = Sym.e(); ez = e.zero()
sage: %timeit ez == 0
10000 loops, best of 3: 27.9 µs per loop
sage: %timeit ez.is_zero()
100000 loops, best of 3: 4.45 µs per loop

and on nonzero elements:

sage: %timeit ZZ(2) == 0     
1000000 loops, best of 3: 416 ns per loop
sage: %timeit ZZ(2).is_zero()
1000000 loops, best of 3: 383 ns per loop
sage: %timeit QQ(2) == 0
100000 loops, best of 3: 2.15 µs per loop
sage: %timeit QQ(2).is_zero()
1000000 loops, best of 3: 877 ns per loop
sage: e2 = e[2]
sage: %timeit e2 == 0
10000 loops, best of 3: 27.8 µs per loop
sage: %timeit e2.is_zero()
100000 loops, best of 3: 5.91 µs per loop
sage: %timeit Integer(2) == 0     
1000000 loops, best of 3: 417 ns per loop
sage: %timeit Integer(2).is_zero()
1000000 loops, best of 3: 360 ns per loop

I don't know how much of the coercion overhead can be removed by improving the coercion system, but for now it looks like is_zero wins against coercion.

Last edited 7 years ago by darij (previous) (diff)

comment:7 follow-up: Changed 7 years ago by darij

Actually, checking equality with parent.zero() is even faster than checking is_zero(). I'll push this once I am back home.

comment:8 Changed 7 years ago by leif

  • Milestone changed from sage-6.2 to sage-6.3

comment:9 Changed 7 years ago by git

  • Commit changed from 4d4cbe0664c62dce9780d82e8eb948ee420ce521 to 46f627eb1d6387b28732d73bf3a7e9994b1db96f

Branch pushed to git repo; I updated commit sha1. New commits:

0cf0ac9Merge branch 'public/combinat/matrix0-fix' of git://trac.sagemath.org/sage into matrixnew
46f627espeed up is_alternating a bit more, and improving some doc

comment:10 Changed 7 years ago by darij

Fixed. Sorry for it taking such a while!

comment:11 in reply to: ↑ 7 Changed 7 years ago by vdelecroix

Replying to darij:

Actually, checking equality with parent.zero() is even faster than checking is_zero(). I'll push this once I am back home.

I see, the following tests are more appropriate

sage: n = 12
sage: %timeit n.is_zero()
1000000 loops, best of 3: 204 ns per loop
sage: zero = n.parent().zero()
sage: %timeit n == zero
10000000 loops, best of 3: 149 ns per loop
Last edited 7 years ago by vdelecroix (previous) (diff)

comment:12 Changed 7 years ago by vdelecroix

Hi Darij,

What is the point of if not self.get_unsafe(i,i) == zero: instead of if self.get_unsafe(i,i) != zero:? Could you write an appropriate title and an appropriate description for the ticket?

I agree that it is a small ticket. But it is not a reason to not do it cleanly!

Thanks, Vincent

comment:13 Changed 7 years ago by git

  • Commit changed from 46f627eb1d6387b28732d73bf3a7e9994b1db96f to f36f0ad401050a0ea824acd75be32d92c0b832c1

Branch pushed to git repo; I updated commit sha1. New commits:

f36f0aduse != instead of not ==

comment:14 Changed 7 years ago by darij

  • Description modified (diff)

Oops, the use of "not" was a relic of the old version.

Part of the reason why comparison with parent().zero() takes so long is that parent() and zero() have to be computed. This can be done once per call of the method, and so the time amortizes quite well.


New commits:

f36f0aduse != instead of not ==

comment:15 Changed 7 years ago by vdelecroix

  • Status changed from needs_review to positive_review

Hi Darij,

I still do not understand the motivation for the ticket: the function is not time critical and as you confirmed there is nowhere in Sage a ring whose zero is not 0. The code is better with the branch applied so I set to positive review.

Vincent

comment:16 Changed 7 years ago by darij

Thank you!

This is a really minor change I wouldn't have done if the code in question wasn't my code from an older ticket.

comment:17 Changed 7 years ago by vbraun

reviewer name

comment:18 Changed 7 years ago by darij

  • Reviewers set to ​Vincent Delecroix

comment:19 Changed 7 years ago by tscrim

FTR, there is one:

sage: T = TropicalSemiring(QQ)
sage: T(0)
0
sage: T.zero()
+infinity

(which we have to do because TestSuite uses zero as the additive identity, so we might want a separate categories for tropical stuff, but that's an issue for a different ticket).

comment:20 Changed 7 years ago by vbraun

  • Reviewers changed from ​Vincent Delecroix to Vincent Delecroix

comment:21 Changed 7 years ago by vbraun

  • Branch changed from public/combinat/matrix0-fix to f36f0ad401050a0ea824acd75be32d92c0b832c1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.