Hey Joel, So I asked Robert about this earlier. He'll probably reply pretty soon, but I think he's currently on a plane, so I'll tell you what I learned. There was definitely something going wrong with coercion, i.e. the appearance of a base_extend call -- I think the issue was that the matrix classes weren't completely using the arithmetic architecture stuff. The MatrixSpace code was actually a reasonable thing, in either the ZZ or QQ case. They have different rationale:
(1) If you're multiplying two matrices over QQ, it actually factors out denominators, then works over ZZ. This is the MatrixSpace creation we were seeing. (2) Even if they have the same parent, often the code will construct the space to make the answer in. This is written this way because you only get to skip it when you are both square, so it was originally written to handle both cases; however, the matrix spaces are cached, so there's not a huge amount of overhead in calling into something that just looks up the space in the dictionary and sends it back to you. I think Robert might have agreed that it should maybe be special- cased away in many cases, but we got interrupted by a talk starting while we were discussing this; I'll wait and let him chime in with what is going to happen in this case. In any event, the code should be running much faster, and the patch is on Robert's computer. Hopefully he reads this early enough to get the patch to William for 2.8.6. ;) -cc On Oct 3, 2007, at 6:52 PM, Joel B. Mohler wrote: > > Hi, > > It would have been nice to sit down in person with Robert and/or > William about > this at Clay, but I only fully realized the extent of my questions > about 1.5 > hours before I wanted to leave :). Anyhow, the matrix > multiplication process > is looking a bit inefficient to me. > > Here's the situation: > sage: M=MatrixSpace(ZZ,3,3) > sage: m=M([range(9)]) > sage: n=M([range(1,10)]) > sage: prun m*n > 20 function calls in 0.000 CPU seconds > Ordered by: internal time > ncalls tottime percall cumtime percall filename:lineno > (function) > 1 0.000 0.000 0.000 0.000 <string>:1(<module>) > 2 0.000 0.000 0.000 0.000 matrix_space.py:105 > (MatrixSpace) > 1 0.000 0.000 0.000 0.000 matrix_space.py:282 > (change_ring) > 1 0.000 0.000 0.000 0.000 matrix_space.py:306 > (base_extend) > 1 0.000 0.000 0.000 0.000 matrix_space.py:648 > (matrix_space) > 3 0.000 0.000 0.000 0.000 matrix_space.py:670 > (ncols) > 3 0.000 0.000 0.000 0.000 matrix_space.py:681 > (nrows) > ... > > The most alarming thing in that is the "base_extend" call. Both > have a base > of ZZ (It also happens if both matrices are in MatrixSpace(QQ)). > This > occurs because of a call to base_base_extend_canonical_sym_c around > line 2075 > in element.pyx. The other thing that alarms me is the calls > to "matrix_space" and "MatrixSpace" to construct a new parent > space. These > are square matrices so we should not have to call out to the > (python) parent > ring to make a new parent ring. > > Now, both of these are easily enough fixed by an appropriate if > statement > above the offending lines of code. However, it seems that this > could all be > fit into the coercion model a little more seamlessly. It seems > that the > Matrix.__mul__ method pretty much takes over and does it's own thing. > > Any thoughts (especially from the coercion guru)? Craig suggested > that matrix > multiplication could be viewed as an action in the coercion model, > but I'm > not sure I agree. Mathematically, if element 'a' acts on element > 'b', I > expect the result to have the same parent as 'b', but that isn't > the case > with non-square matrices in general. I don't know if that definition > of 'action' is the same as the coercion model's. > > -- > Joel > > > --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
