bug in zero_matrix rewrite in matrix_space.py #12020

williamstein · 2011-11-13T19:28:23Z

Observe this:

sage: D=DirichletGroup(20);
sage: g=D[7].extend(400); #order 4 character
sage: M=ModularSymbols(g,2,sign=1).cuspidal_subspace()
sage: N=M.new_subspace()
TypeError                                 Traceback (most recent call last)

/mnt/usb1/scratch/wstein/ref/sage-4.8.alpha2-sage.math.washington.edu-x86_64-Linux/local/lib/python2.6/site-packages/sage/rings/number_field/number_field.pyc in _coerce_non_number_field_element_in(self, x)
   5399         except (TypeError, AttributeError), msg:
   5400             pass
-> 5401         raise TypeError, type(x)
   5402 
   5403     def _coerce_from_str(self, x):
TypeError: <type 'NoneType'>

Debugging we see that the problem is that this code in matrix_space.py:

    479         if entries is None or entries == 0:
    480             if self._copy_zero: # faster to copy than to create a new one.
    481                 return self.zero_matrix().__copy__()
    482             else:
--> 483                 return self.__matrix_class(self, None, coerce=coerce, copy=copy)

That None in the last line is then coerced for some reason into a number field (Cyclotomic Field of order 4 and degree) which makes no sense now...

This bug was introduced in #11589.

Apply attachment: trac_12020_alt.patch and attachment: 12020_review.patch

CC: @vbraun

Component: linear algebra

Author: Martin Albrecht, Volker Braun, Jeroen Demeyer

Reviewer: William Stein, Jeroen Demeyer, Volker Braun,

Merged: sage-4.8.alpha3

Issue created by migration from https://trac.sagemath.org/ticket/12020

The text was updated successfully, but these errors were encountered:

williamstein · 2011-11-13T19:45:24Z

comment:1

I figured this out. This bug was introduced by #11589 (by Simon King and Martin Albrecht). Basically the zero_matrix() method's code was "mangled/changed" (?) when being copied into the __init__ method by replacing "0" by "None". This breaks the code, since there is no reason that None be coercible into a ring R, and I don't think that has to be supported because, e.g., in Python int(None) is an error. Also, this is a weird change since the zero_matrix method in the new code still uses 0.

Patch coming up.

williamstein · 2011-11-13T19:49:37Z

comment:2

Here is a simple test to reveal the bug. Small size matrices don't show the bug, probably because of some arbitrary caching parameter in #11589, which is probably why this bug slipped through our test framework (we really need a random larger testing framework!):

sage: A = MatrixSpace(CyclotomicField(4),60,30)(0)
sage: A.augment(A)
boom!

jdemeyer · 2011-11-14T08:44:08Z

Attachment: trac_12020.patch.gz

Attachment: trac_12020.2.patch.gz

Same patch with corrected doc formatting

jdemeyer · 2011-11-14T08:46:29Z

Author: William Stein

malb · 2011-11-14T12:20:33Z

comment:5

I have attached an alternative solution: instead of switching back to 0 instead of None make Matrix_cyclo_dense deal with None properly. The reason we switched to None was because this is faster since most (?, perhaps only some) matrix classes do nothing if None is passed, while they write 0 along the main diagonal if zero is passed. Of course, one could also fix those matrix classes and switch back to 0.

jdemeyer · 2011-11-14T14:00:56Z

comment:6

Replying to @malb:

Of course, one could also fix those matrix classes and switch back to 0.

I slightly prefer that because it seems safer to me.

vbraun · 2011-11-14T15:08:40Z

comment:7

I found and fixed this bug earlier in #12000. Of course nobody ever reviews my patches, sniff.

jdemeyer · 2011-11-14T15:49:15Z

comment:8

Replying to @vbraun:

I found and fixed this bug earlier in #12000. Of course nobody ever reviews my patches, sniff.

Especially with such a nice ticket number...

Proposing to close this as "duplicate"

malb · 2011-11-14T15:52:49Z

comment:9

If "this" is "this ticket" then I agree.

williamstein · 2011-11-14T16:18:07Z

comment:10

The fix for #12000 also works for this particular example. I really hope that all other matrix types (now and in the future) respect this None convention, since they will all have the same problem if we go with the #12000 fix rather than the fix here. We could add documentation in the file matrix/docs.py that reflects what should happen with None, and we should try to add a test that things work with several different types.

malb · 2011-11-14T17:09:12Z

comment:11

I checked the __init__ methods of all pyx files in sage/matrix/ and found one which doesn't treat entries==None properly: matrix_modn_sparse.pyx, so this one should get fixed. Note that all others explicitly support entries==None and many do nothing when it is passed, i.e., it's the explicit fast path.

williamstein · 2011-11-14T17:17:47Z

comment:12

Replying to @malb:

I checked the __init__ methods of all pyx files in sage/matrix/ and found one which doesn't treat entries==None properly: matrix_modn_sparse.pyx, so this one should get fixed. Note that all others explicitly support entries==None and many do nothing when it is passed, i.e., it's the explicit fast path.

Cool. Great work checking that. I'm really happy with this now then.

williamstein · 2011-11-14T17:20:59Z

comment:13

I give malb's trac_12020_alt.patch a positive review. Note that the patch at 12000 by Volker is isomorphic to malb's, except it also has sphinxification of the relevant docstrings (though the rest of the file is pre-sphinx) and a different doctest illustrating the same issue.

jdemeyer · 2011-11-14T17:25:32Z

comment:14

Replying to @williamstein:

I give malb's trac_12020_alt.patch a positive review.

He just said that matrix_modn_sparse.pyx is also broken (and not yet fixed by the patch here)...

williamstein · 2011-11-14T17:38:09Z

comment:15

Replying to @jdemeyer:

Replying to @williamstein:

I give malb's trac_12020_alt.patch a positive review.

He just said that matrix_modn_sparse.pyx is also broken (and not yet fixed by the patch here)...

Woops -- I agree with not giving this a positive review.

It would be good to have a test that runs through a large number of base rings.

malb · 2011-11-14T18:41:30Z

Attachment: trac_12020_alt.patch.gz

malb · 2011-11-14T18:43:40Z

comment:16

I added a comment to docs.py and added a return if entries is None. However, since e.g., GF(7)(None) == 0} it does not actually fix a bug, just exits slightly faster.

williamstein · 2011-11-14T18:51:19Z

comment:17

Thanks malb. It looks great to me. (And if you want to do something else for Sage-5.0, you could doctest "matrix/benchmark.py: 0% (0 of 29)" from #12024.)

jdemeyer · 2011-11-14T21:03:39Z

Reviewer: William Stein

jdemeyer · 2011-11-14T21:03:39Z

Changed author from William Stein to Martin Albrecht, Jeroen Demeyer

jdemeyer · 2011-11-14T21:04:13Z

comment:19

Reviewer patch adding extra doctests like William suggested, needs_review.

williamstein · 2011-11-14T21:07:33Z

comment:20

It would be nice to define a list of 100 (say) various rings in a file in the tests directory. Then the test could be

sage: from sage.tests.examples import commutative_rings0
sage: for R in commutative_rings0: 
         do something

Then people could add new rings to that list, and tests all over may benefit.

And in addition to rings, we could assemble many other lists of examples of objects in that file.

This could be on another ticket.

jdemeyer · 2011-11-15T09:06:54Z

Attachment: 12020_review.patch.gz

jdemeyer · 2011-11-15T09:08:12Z

comment:21

I added Volker's patch from #12000 here.

jdemeyer · 2011-11-15T09:08:12Z

Changed author from Martin Albrecht, Jeroen Demeyer to Martin Albrecht, Volker Braun, Jeroen Demeyer

jdemeyer · 2011-11-19T12:00:40Z

comment:22

ping needs review

vbraun · 2011-11-19T12:35:01Z

comment:23

Looks good!

vbraun · 2011-11-19T12:35:01Z

Changed reviewer from William Stein to William Stein, Jeroen Demeyer, Volker Braun,

jdemeyer · 2011-11-21T10:45:42Z

Merged: sage-4.8.alpha3

… type MA_ENTRIES_ZERO There are many ways to specify entries when creating a matrix, which are handled in `args.pyx` with `MatrixArgs` class. It has been discussed before why allowing `entries=None` in the matrix creation methods can be beneficial in terms of performance (sagemath#11589 , sagemath#12020). This input `entries=None` is required to yield the zero matrix. For example: `matrix(QQ, 4, 4)` creates the zero matrix. This corresponds to the type `MA_ENTRIES_ZERO` in `args.pyx`. When one passes a value, e.g. `matrix(QQ, 4, 4, 2)`, then one gets a diagonal matrix with `2` on the diagonal; this corresponds to the type `MA_ENTRIES_SCALAR` in `args.pyx`. Currently, doing something like `matrix(QQ, 4, 4, 0)` will pick `MA_ENTRIES_SCALAR`, and therefore will build the matrix and fill the diagonal with zero. [Behind the scenes, there is still some acknowledgement that this is not the usual scalar matrix case, since this will not fail if the matrix is not square (`matrix(QQ, 4, 5, 0)` will not fail, but `matrix(QQ, 4, 5, 1)` will). But this is still not seen as `MA_ENTRIES_ZERO`.] This PR ensures the type `MA_ENTRIES_ZERO` is picked in this situation. This improves performance and solves some issues, as noted below. This PR also fixes the related issue sagemath#36065 . In fact, `entries=None` is the default in the `__init__` of all matrix subclasses presently implemented. It also used to be the default when constructing a matrix by "calling" a matrix space, until sagemath#31078 and https://github.com/sag emath/sage/commit/cef613a0a57b85c1ebc5747185213ae4f5ec35f2 which changed this default value from `None` to `0`, bringing some performance regression. Regarding this "calling the matrix space", this PR also solves the performance issue noted in sagemath#35961 (comment) , where it was observed that in the following piece of code: ``` sage: space = MatrixSpace(GF(9001), 10000, 10000) sage: %timeit zmat = space.matrix() 18.3 µs ± 130 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each) sage: %timeit zmat = space() 12.1 ms ± 65.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) ``` the called default is not the same. `space.matrix()` directly initializes the matrix through `entries=None`, but on the other hand `space()` actually calls the constructor with `entries=0`. This performance regression comes from sagemath#31078 and https://github.com/sag emath/sage/commit/cef613a0a57b85c1ebc5747185213ae4f5ec35f2 , where the default for construction from the matrix space was changed from `None` to `0`. This cannot be easily reverted: this is now the default in the `__call__` of the `Parent` class. So this PR does not directly revert the call default to `None` somehow, but the result is very close in effect (read: the overhead is small). Unchanged: through the parent call, `0` is converted to the base ring zero, which is passed to the constructor's `entries` which is then analyzed as `MA_ENTRIES_SCALAR`. Changed: the code modifications ensure that soon enough it will be detected that this is in fact `MA_ENTRIES_ZERO`. The small overhead explains why, despite the improvements, construction with `None` is still sometimes slightly faster than with `0`. Below are some timings showing the improvements for some fields. Also, this PR merged with the improvements discussed in sagemath#35961 will make the above timings of `space.matrix()` and `space()` be the same (which means a speed-up of a factor >500 for this call `space()`...). The measurement is for construction via calling the matrix space: `None` is `space(None)`, `Empty` is `space()`, `Zero` is `space(0)`, and `Nonzero` is `space(some nonzero value)`. ``` NEW TIMES field dim None Empty Zero Nonzero GF(2) 5 2.3e-06 3.2e-06 3.6e-06 3.2e-06 GF(2) 50 2.4e-06 3.3e-06 3.6e-06 5.8e-06 GF(2) 500 3.6e-06 4.5e-06 4.8e-06 3.1e-05 GF(512) 5 2.6e-05 2.8e-05 2.9e-05 2.9e-05 GF(512) 50 2.6e-05 2.9e-05 2.9e-05 4.0e-05 GF(512) 500 3.7e-05 3.8e-05 3.9e-05 1.6e-04 QQ 5 2.2e-06 3.3e-06 3.4e-06 3.2e-06 QQ 50 8.0e-06 9.2e-06 9.4e-06 1.2e-05 QQ 500 6.1e-04 6.3e-04 6.4e-04 6.7e-04 OLD TIMES field dim None Empty Zero Nonzero GF(2) 5 2.3e-06 3.5e-06 3.6e-06 3.7e-06 GF(2) 50 2.4e-06 6.0e-06 6.1e-06 6.0e-06 GF(2) 500 3.6e-06 3.0e-05 3.0e-05 3.0e-05 GF(512) 5 2.5e-05 2.8e-05 2.9e-05 2.9e-05 GF(512) 50 2.5e-05 3.9e-05 4.0e-05 4.0e-05 GF(512) 500 3.5e-05 1.5e-04 1.5e-04 1.6e-04 QQ 5 2.2e-06 3.5e-06 3.7e-06 3.7e-06 QQ 50 7.9e-06 1.2e-05 1.2e-05 1.2e-05 QQ 500 6.4e-04 6.9e-04 6.9e-04 6.9e-04 ``` Code used for the timings: ``` time_kwds = dict(seconds=True, number=20000, repeat=7) fields = [GF(2), GF(2**9), QQ] names = ["GF(2)", "GF(512)", "QQ"] vals = [GF(2)(1), GF(2**9).gen(), 5/2] print(f"field\tdim\tNone\tEmpty\tZero\tNonzero") for field,name,val in zip(fields,names,vals): for dim in [5, 50, 500]: space = MatrixSpace(field, dim, dim) tnone = timeit("mat = space(None)", **time_kwds) tempty = timeit("mat = space()", **time_kwds) tzero = timeit("mat = space(0)", **time_kwds) tnonz = timeit("mat = space(1)", **time_kwds) print(f"{name}\t{dim}\t{tnone:.1e}\t{tempty:.1e}\t{tzero:.1e}\t{ tnonz:.1e}") ``` ### 📝 Checklist - [x] The title is concise, informative, and self-explanatory. - [x] The description explains in detail what this PR is about. - [x] I have linked a relevant issue or discussion. - [x] I have created tests covering the changes. - [x] I have updated the documentation accordingly. ### ⌛ Dependencies URL: sagemath#36068 Reported by: Vincent Neiger Reviewer(s): Matthias Köppe, Vincent Neiger

williamstein added this to the sage-4.8 milestone Nov 13, 2011

williamstein added c: linear algebra labels Nov 13, 2011

williamstein assigned jasongrout and williamstein Nov 13, 2011

williamstein changed the title ~~major (BLOCKER!) bug probably in matrix_space.py~~ bug in zero_matrix rewrite in matrix_space.py Nov 13, 2011

This comment has been minimized.

Sign in to view

jdemeyer added the s: needs review label Nov 14, 2011

jdemeyer removed this from the sage-4.8 milestone Nov 14, 2011

williamstein added s: positive review and removed s: needs review labels Nov 14, 2011

jdemeyer added s: needs work and removed s: positive review labels Nov 14, 2011

malb added s: needs review and removed s: needs work labels Nov 14, 2011

williamstein added s: positive review and removed s: needs review labels Nov 14, 2011

This comment has been minimized.

Sign in to view

jdemeyer added s: needs work and removed s: positive review labels Nov 14, 2011

jdemeyer added this to the sage-4.8 milestone Nov 14, 2011

jdemeyer added s: needs review and removed s: needs work labels Nov 14, 2011

vbraun added s: positive review and removed s: needs review labels Nov 19, 2011

jdemeyer removed the s: positive review label Nov 21, 2011

jdemeyer closed this as completed Nov 21, 2011

vbraun mentioned this issue Nov 15, 2011

block_matrix over cyclotomics fails #12000

Closed

vneiger mentioned this issue Aug 10, 2023

Speed-up matrix construction by ensuring MatrixArgs type MA_ENTRIES_ZERO #36068

Merged

5 tasks

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

bug in zero_matrix rewrite in matrix_space.py #12020

bug in zero_matrix rewrite in matrix_space.py #12020

williamstein commented Nov 13, 2011

williamstein commented Nov 13, 2011

williamstein commented Nov 13, 2011

jdemeyer commented Nov 14, 2011

This comment has been minimized.

jdemeyer commented Nov 14, 2011

malb commented Nov 14, 2011

jdemeyer commented Nov 14, 2011

vbraun commented Nov 14, 2011

jdemeyer commented Nov 14, 2011

malb commented Nov 14, 2011

williamstein commented Nov 14, 2011

malb commented Nov 14, 2011

williamstein commented Nov 14, 2011

williamstein commented Nov 14, 2011

jdemeyer commented Nov 14, 2011

williamstein commented Nov 14, 2011

malb commented Nov 14, 2011

malb commented Nov 14, 2011

williamstein commented Nov 14, 2011

jdemeyer commented Nov 14, 2011

This comment has been minimized.

jdemeyer commented Nov 14, 2011

jdemeyer commented Nov 14, 2011

williamstein commented Nov 14, 2011

jdemeyer commented Nov 15, 2011

jdemeyer commented Nov 15, 2011

jdemeyer commented Nov 15, 2011

jdemeyer commented Nov 19, 2011

vbraun commented Nov 19, 2011

vbraun commented Nov 19, 2011

jdemeyer commented Nov 21, 2011

bug in zero_matrix rewrite in matrix_space.py #12020

bug in zero_matrix rewrite in matrix_space.py #12020

Comments

williamstein commented Nov 13, 2011

williamstein commented Nov 13, 2011

williamstein commented Nov 13, 2011

jdemeyer commented Nov 14, 2011

This comment has been minimized.

jdemeyer commented Nov 14, 2011

malb commented Nov 14, 2011

jdemeyer commented Nov 14, 2011

vbraun commented Nov 14, 2011

jdemeyer commented Nov 14, 2011

malb commented Nov 14, 2011

williamstein commented Nov 14, 2011

malb commented Nov 14, 2011

williamstein commented Nov 14, 2011

williamstein commented Nov 14, 2011

jdemeyer commented Nov 14, 2011

williamstein commented Nov 14, 2011

malb commented Nov 14, 2011

malb commented Nov 14, 2011

williamstein commented Nov 14, 2011

jdemeyer commented Nov 14, 2011

This comment has been minimized.

jdemeyer commented Nov 14, 2011

jdemeyer commented Nov 14, 2011

williamstein commented Nov 14, 2011

jdemeyer commented Nov 15, 2011

jdemeyer commented Nov 15, 2011

jdemeyer commented Nov 15, 2011

jdemeyer commented Nov 19, 2011

vbraun commented Nov 19, 2011

vbraun commented Nov 19, 2011

jdemeyer commented Nov 21, 2011