New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
avoid Maxima on creation of symbolic matrices #18979
Comments
New commits:
|
Commit: |
Author: Ralf Stephan |
This comment has been minimized.
This comment has been minimized.
comment:5
Hi, I really do not like your solution. You are invading a generic class with some specialized code. Moreover, the issue you found might be present in a lot of other places. You should find a better way to do this test without having to care whether the input is symbolic. If each ring needs a specialized treatment it will become a complete nightmare. Secondly, the operations In this very particular case of matrices, there is a simpler way to fix the issue. You can just avoid testing anything. In case Vincent |
comment:6
Replying to @videlec:
Agreed. The easiest way would be
Will do that. EDIT: not zero |
comment:7
Omitting the checks however makes hundreds of doctests fail with eg...
|
comment:8
For the symbolic solution see #19040. The question is if that makes this ticket a duplicate, or if your idea of simply removing checks can be implemented. |
comment:9
Replying to @rwst:
I was wrong. Removing the check would work only for square matrices. You want to allow initialization from zero for any matrix (because the matrix space form a vector space). But for other scalars the matrices need to be square in order to form a ring. |
comment:10
This is nonsense. Look at how many instance checks you have in |
Changed branch from u/rws/avoid_maxima_on_creation_of_symbolic_matrices to u/rws/18979 |
comment:12
This patch has the following footprint:
I don't believe you would stall this again because of, say, ten microseconds? New commits:
|
comment:13
I think invading a fundamental piece of infrastructure with specific tests for a specific ring should not be taken lightly. I think you can avoid most of your trouble by delaying the is_zero test to the last possible moment:
The first list comprehension can be optimized further, if required (I suspect that testing whether "entries" is zero to more quickly create a square zero matrix is a false optimization: if you need that thing quickly often, you should reuse an immutable zero matrix. That will be much quicker (and constant in size of the matrix!), so I don't think it's necessary). If the zero check is expensive, it will almost certainly lead to an error. With this code there is no big need to single out SR anymore, and you fix a more fundamental issue: in order to create a matrix (even a diagonal square one) it shouldn't be necessary that your ring has a decidable (or efficient) zero test. For a non-square zero matrix, we can't avoid a zero check, but at least we can delay that until we really need to know (because otherwise we raise an error). |
Changed branch from u/rws/18979 to u/nbruin/18979 |
Changed author from Ralf Stephan to Nils Bruin |
comment:16
OK, I'll put my code where my mouth is. Previous branch u/rws/18979 should still be present if it's preferred to resolve this ticket on the solution proposed there. New commits:
|
comment:17
As I said in comment:5, the solution should be non intrusive and your solution is what I suggested at the very end of this comment. Though, using a list extension is twice slower. With
I got
|
comment:18
Replying to @videlec:
OK, go ahead and replace the loop by whatever works better. I hoped cython would be able to optimize this loop, but apparently it cannot. As your example shows, we're likely better off writing the diagonal twice. If this absolutely needs to be fast, we can kick down to a The only thing that testing for zero got us in the square case is that for a zero matrix, we can avoid reinitializing the diagonal. I think we can do without that optimization, so then at least the problem for SR and other rings without (easily) testable equality are mostly fine except for situations that will most likely be an error anyway. |
Branch pushed to git repo; I updated commit sha1. New commits:
|
comment:21
Thanks for the changes. Note that your solution does not change anything to the problem mentioned in the description of this ticket! Vincent |
comment:22
Replying to @videlec:
Well, it solves the problem for the example mentioned: for square matrices and a single ring element as initialization it doesn't compare it to 0 anymore, so for square matrices, maxima is now avoided. I think comparison in SR is smart enough that an explicit 0 compares equal to 0 without punting to maxima. So maxima should only be hit if we have a non-square matrix and the argument is not obviously 0. In that case it probably isn't zero, and in any case the user deserves what they have coming to them then. In general, I think indeed that the generic matrix code shouldn't assume equality- or zero-testing is particularly cheap, and hence avoid it unless it's really necessary. The change here is a step in the right direction and basically has the same effect of what rws was trying to do on his branch. |
Reviewer: Vincent Delecroix |
comment:23
Replying to @nbruin:
Right. Sorry, I misunderstood the branching of the code! |
comment:24
Replying to @nbruin:
Right, but for sparse matrices it is explicitely assumed that only nonzero entries are stored... what should we do in that case? |
comment:25
Replying to @videlec:
Different problem, different ticket. Of course, one should only avoid comparisons if one can. Since matrices rarely "accidentally" remain sparse, you probably get decent performance by just assuming any entry that is actually given, is nonzero (so no explicit checks necessary). Of course that doesn't work when converting a dense matrix to a sparse one. If this is an issue, perhaps we should have a special "comparison avoiding" sparse matrix class. |
comment:26
In any case #19040 will make this all obsolete. |
Changed branch from u/nbruin/18979 to |
People have no idea what they ask for when they write
if ex != 0:
withex
possibly(!) a symbolic expression. E.g. this happens to trigger inmatrix/*
the full blown procedure of starting Maxima with its limited deductive armament trying to prove thatex
is nonzero. This when all was wanted was that it not be a "numeric" zero.This ticket replaces the two instances in
matrix/
where such behaviour was triggered in doctests.Compare on fresh Sage:
Before:
After:
Component: linear algebra
Author: Nils Bruin
Branch/Commit:
e42f285
Reviewer: Vincent Delecroix
Issue created by migration from https://trac.sagemath.org/ticket/18979
The text was updated successfully, but these errors were encountered: