Re: [sage-devel] Re: Severe regression in construction of matrices
On Wednesday, June 6, 2018 at 12:01:54 PM UTC+10, Nils Bruin wrote: > > On Tuesday, June 5, 2018 at 5:51:34 PM UTC-7, Travis Scrimshaw wrote: >> >> >> For instance, what prevents us from cdeffing >>> sage.matrix.matrix_space.MatrixSpace? >>> >> >> Multiple inheritance: UniqueRepresentation and ParentWithGens (which >> should be Parent at some point...). >> >> Oh boy. So we'd end up manually resolving some inheritance in order to > splice a cdef class in ... Perhaps Jeroen can find another way. > > In general, would it be opportune to have a "Space of matrices over ..." > as a parent? Addition and multiplication would only be partial operations > it, but matrices tend to know their own dimensions quite efficiently, and > the coercion framework only deals with the base ring anyway (for matrix > operations). SO it would seem that for basic purposes, the parent might not > need to keep track of the dimensions of its elements. A method like > ".new_matrix(n,m)" would be able to *very quickly* construct a > matrix, because it's basically guaranteed that installing the parent > amounts to copying a reference. > > We'd of course still have our more fully defined MatrixSpace(..,n,m) for > cases where having a mathematically more specific parent is warranted (and > perhaps we can refine this dynamically on mutable matrices) > But for that, you would lose anything that comes from the appropriate category. So this should work: sage: MS = MatrixSpace(QQ, 2) sage: M = MS.an_element() sage: M.to_matrix() Although it does not due to a separate bugs I just uncovered: The result of a module_morphism does not know it should be in finite-dimensional vector spaces. Moreover, its parent is not the result of Hom(MS, MS). sage: basis = M.parent().basis() sage: action = lambda x: action_left(self, basis[x]) sage: endo = M.parent().module_morphism(on_basis=action, codomain=M.parent ()) sage: endo.parent() Set of Morphisms from Full MatrixSpace of 2 by 2 dense matrices over Rational Field to Full MatrixSpace of 2 by 2 dense matrices over Rational Field in Category of vector spaces with basis over Rational Field sage: Hom(MS, MS) Set of Homomorphisms from Full MatrixSpace of 2 by 2 dense matrices over Rational Field to Full MatrixSpace of 2 by 2 dense matrices over Rational Field sage: type(endo.parent()) sage: type(Hom(MS, MS)) However, these bugs are a separate issue. Best, Travis -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Severe regression in construction of matrices
On Tuesday, June 5, 2018 at 5:51:34 PM UTC-7, Travis Scrimshaw wrote: > > > For instance, what prevents us from cdeffing >> sage.matrix.matrix_space.MatrixSpace? >> > > Multiple inheritance: UniqueRepresentation and ParentWithGens (which > should be Parent at some point...). > > Oh boy. So we'd end up manually resolving some inheritance in order to splice a cdef class in ... Perhaps Jeroen can find another way. In general, would it be opportune to have a "Space of matrices over ..." as a parent? Addition and multiplication would only be partial operations it, but matrices tend to know their own dimensions quite efficiently, and the coercion framework only deals with the base ring anyway (for matrix operations). SO it would seem that for basic purposes, the parent might not need to keep track of the dimensions of its elements. A method like ".new_matrix(n,m)" would be able to *very quickly* construct a matrix, because it's basically guaranteed that installing the parent amounts to copying a reference. We'd of course still have our more fully defined MatrixSpace(..,n,m) for cases where having a mathematically more specific parent is warranted (and perhaps we can refine this dynamically on mutable matrices) -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: random_element and randtest_element
> > What do you think? Does the name randtest_element look ok? How about "_random_test_element", as this method needs not to be revealed to users, unlike "random_element" and "some_elements". -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Severe regression in construction of matrices
> For instance, what prevents us from cdeffing > sage.matrix.matrix_space.MatrixSpace? > Multiple inheritance: UniqueRepresentation and ParentWithGens (which should be Parent at some point...). Best, Travis -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Severe regression in construction of matrices
On Tuesday, June 5, 2018 at 7:11:40 AM UTC-7, Jeroen Demeyer wrote: > > The problem is that you need to access the *Python* attributes of the > *Python* class MatrixSpace. Ideally, you do this at most once for each > such attribute, but after #24742 nrows() may be called twice when > constructing a matrix. > Would it be a problem to splice in a cdef class somewhere that provides cdef attributes for _nrows and _ncols and then provides python-level methods to access these values from python? For instance, what prevents us from cdeffing sage.matrix.matrix_space.MatrixSpace? The cython code could then simply use the superfast attributes. Small matrices over superfast rings (such as GF(p)) are sufficiently basic that we probably want to use all tricks to make them superfast, just like integers and univariate polynomials. If parents are too heavy, we should even consider a parentless version of them. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Severe regression in construction of matrices
Hi Jeroen, On 2018-06-05, Jeroen Demeyer wrote: > On 2018-06-05 15:56, Simon King wrote: >> Yes, it would indeed be a total waste of time to not just access the >> cdef attributes of a matrix when writing Cython code. > > The problem is that you need to access the *Python* attributes of the > *Python* class MatrixSpace. Ideally, you do this at most once for each > such attribute, but after #24742 nrows() may be called twice when > constructing a matrix. Sorry, I thought you were talking about the nrows() method of a matrix (not of a matrix space). Best regards, Simon -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] random_element and randtest_element
Hi, On Tue, Jun 05, 2018 at 10:31:38AM -0700, Samuel Lelievre wrote: > How about adding an optional argument "distribution" > defaulting to None, and for polynomials having say, > if distribution == 'for_testing', then, > > - with probability 1/4, > select at random among R.some_elements() > - with probability 1/4, > return random polynomial of density 1 > - with probability 1/4, > return random polynomial of density 1/2 > - with probability 1/4, > return random polynomial of <= 3 monomials This will make the code of random_element overloaded hence less readable. If those four tests are interesting, we should just add them to the TEST section. Ciao, Thierry > -- > You received this message because you are subscribed to the Google Groups > "sage-devel" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to sage-devel+unsubscr...@googlegroups.com. > To post to this group, send email to sage-devel@googlegroups.com. > Visit this group at https://groups.google.com/group/sage-devel. > For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] random_element and randtest_element
How about adding an optional argument "distribution" defaulting to None, and for polynomials having say, if distribution == 'for_testing', then, - with probability 1/4, select at random among R.some_elements() - with probability 1/4, return random polynomial of density 1 - with probability 1/4, return random polynomial of density 1/2 - with probability 1/4, return random polynomial of <= 3 monomials -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] random_element and randtest_element
On Tue, Jun 05, 2018 at 06:01:35PM +0200, Jeroen Demeyer wrote: > On 2018-06-05 17:52, Vincent Delecroix wrote: > > 2) a new method randtest_element that would generate (quickly) a > > random element suited for testing. Such a method would try to > > return "corner cases" with good probability. > > I thought that some_elements() was meant for that: +1. Ciao, Thierry > > sage: R. = ZZ[] > sage: list(R.some_elements()) > [x, 0, 1, 1, x^2 + 2*x + 1, x^3, x^2 - 1, x^2 + 1, 2*x^2 + 2] > > Obviously, this some_elements() method could be improved but that's besides > the point. > > -- > You received this message because you are subscribed to the Google Groups > "sage-devel" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to sage-devel+unsubscr...@googlegroups.com. > To post to this group, send email to sage-devel@googlegroups.com. > Visit this group at https://groups.google.com/group/sage-devel. > For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] random_element and randtest_element
On 2018-06-05 17:52, Vincent Delecroix wrote: 2) a new method randtest_element that would generate (quickly) a random element suited for testing. Such a method would try to return "corner cases" with good probability. I thought that some_elements() was meant for that: sage: R. = ZZ[] sage: list(R.some_elements()) [x, 0, 1, 1, x^2 + 2*x + 1, x^3, x^2 - 1, x^2 + 1, 2*x^2 + 2] Obviously, this some_elements() method could be improved but that's besides the point. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] random_element and randtest_element
Dear all, Random elements serve two purposes: * random testing * probabilities I would like to introduce 1) better specifications for random_element: eg state clearly the probability distribution of the outcome in the docstring. 2) a new method randtest_element that would generate (quickly) a random element suited for testing. Such a method would try to return "corner cases" with good probability. For example on polynomials, one could imagine something like * random_element: generate a random polynomial of given degree and density (extra argument are forwarded to the base ring) * randtest_element: generate 0, 1, -1, x, x^100 with good probability then either return a polynomial with 3 nonzero coefficients, or a polynomial with density 0.5 or a polynomial with density 1.0. In the above sceniario, we would almost never get 0 by calling random_element which is typically something we want to be tested. What do you think? Does the name randtest_element look ok? Best Vincent -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Severe regression in construction of matrices
On 2018-06-05 15:56, Simon King wrote: Yes, it would indeed be a total waste of time to not just access the cdef attributes of a matrix when writing Cython code. The problem is that you need to access the *Python* attributes of the *Python* class MatrixSpace. Ideally, you do this at most once for each such attribute, but after #24742 nrows() may be called twice when constructing a matrix. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Severe regression in construction of matrices
Hi Jeroen,
On 2018-06-05, Jeroen Demeyer wrote:
> On 2018-06-05 11:48, Jeroen Demeyer wrote:
>> S = MatrixSpace(GF(37), 5, 5); timeit('S()')
>
> I investigated further and one of the reasons that the new code is
> slower is because of some additional calls to MatrixSpace.nrows() and
> similar methods. Since almost everything else is in Cython, calls to
> simple pure Python methods like these account for a large part of the
> time taken in S() above.
Yes, it would indeed be a total waste of time to not just access the
cdef attributes of a matrix when writing Cython code.
Cheers,
Simon
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Severe regression in construction of matrices
On 2018-06-05 11:48, Jeroen Demeyer wrote:
S = MatrixSpace(GF(37), 5, 5); timeit('S()')
I investigated further and one of the reasons that the new code is
slower is because of some additional calls to MatrixSpace.nrows() and
similar methods. Since almost everything else is in Cython, calls to
simple pure Python methods like these account for a large part of the
time taken in S() above.
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Severe regression in construction of matrices
On 2018-06-05 11:38, Jeroen Demeyer wrote:
[M.new_matrix(5,6) for i in range(1,50) for j in range(1,50)]
Here I am seeing a regression of roughly 20%.
This is because of a specific optimization for creating zero matrices
which was removed in #24742. This is giving a regression for
S = MatrixSpace(GF(37), 5, 5); timeit('S()')
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Severe regression in construction of matrices
Comparing 8.2 and 8.3.beta2: On 2018-06-05 08:34, Nils Bruin wrote: M=matrix(GF(37),9,9,range(81)) I don't see any regression for this, timings are identical (with possibly a very small gain in 8.3.beta2). [M.new_matrix(i,j) for i in range(1,50) for j in range(1,50)] For this example, I do see a regression of a factor 3, which is indeed pretty bad! [M.new_matrix(5,6) for i in range(1,50) for j in range(1,50)] Here I am seeing a regression of roughly 20%. I'll continue my analysis... -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Permutation group: faster use of stabilizer chain from gap
In https://trac.sagemath.org/ticket/25477, we (this is mainly Moritz Firsching) implement a new iterator for permutation groups using stabilizer chains. Indeed, the multiplication of permutations seems to be faster than in gap so we hope this method to be really fast in the end... The bottleneck now is that we call self.strong_generating_system(base) for a permutation group self and this is done doing tons of back and forth translations between sage and gap using the pexpect interface (if I understand it correctly). I now have reimplemented the computation of the strong generating system directly in gap, and now the remaining bottleneck is to turn the gap permutations back to sage permutations. So my question is What is the currently fastest way to turn gap permutations into sage permutations? Here is the code: # def SGS_old(G): # taken from strong_generating_system sgs = [] stab = G base = G.base() for j in base: sgs.append(stab.transversals(j)) stab = stab.stabilizer(j) return sgs def SGS_new(G, gap_output=True): S = G._gap_().StabChain() gap.execute(gap_cosets) cosets = S.CosetsStabChain() if gap_output: return cosets # <--- elt_class = G._element_class() gap2sage = lambda elt: elt_class(elt, G, check=False) return [ [ gap2sage(elt) for elt in coset] # <--- for coset in cosets ] # <--- gap_cosets = """CosetsStabChain := function ( S ) local cosets, # element list, result new_coset, # pnt,# point in the orbit of rep;# inverse representative for that point # if is trivial then it is easy if Length(S.generators) = 0 then cosets := [ [S.identity] ]; # otherwise else # compute the elements of the stabilizer cosets := CosetsStabChain( S.stabilizer ); # loop over all points in the orbit new_coset := []; for pnt in S.orbit do # add the corresponding coset to the set of elements rep := S.identity; while S.orbit[1] ^ rep <> pnt do rep := LeftQuotient( S.transversal[pnt/rep], rep ); od; Add( new_coset, rep ); od; Add( cosets, new_coset ); fi; # return the result return cosets; end; """ # and here is the test case to look at: # sage: sage: p = [(i,i+1) for i in range(1,601,2)] : sage: q = [tuple(range(1+i,601,3)) for i in range(3)] : sage: A = PermutationGroup([p,q]) sage: %time XX = SGS_old(A) CPU times: user 3.67 s, sys: 664 ms, total: 4.34 s Wall time: 4.45 s sage: %time XX = SGS_new(A, True) CPU times: user 4.94 ms, sys: 712 µs, total: 5.65 ms Wall time: 14 ms sage: %time XX = SGS_new(A, False) CPU times: user 2.48 s, sys: 116 ms, total: 2.59 s Wall time: 2.61 s # so the actual strong generating system is computed very fast in gap in SGS_new(A, True) while casting the output into sage in SGS_new(A, False) then takes forever. Thanks for your help -- I would expect this fast iteration will help not help my code to be faster! Christian -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Severe regression in construction of matrices
Hi Nils, On 2018-06-05, Nils Bruin wrote: > I suspect that the main slowdowns I am observing are due to the reduced > performance in examples like > > M=matrix(GF(37),9,9,range(81)) > > [M.new_matrix(i,j) for i in range(1,50) for j in range(1,50)] > > and > > [M.new_matrix(5,6) for i in range(1,50) for j in range(1,50)] > > etc.(i.e., both the case where a lot of different parents are constructed > and where the same parent keeps reoccurring). As far as I can see both of > these perform dramatically worse now. Perhaps "memory leak fixed => parents are garbage collected => parents need to be recreated => performance drops"? Best regards, Simon -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Severe regression in construction of matrices
On Monday, June 4, 2018 at 11:10:34 PM UTC-7, Jeroen Demeyer wrote: > > It would be useful to have a concrete MatrixSpace.__call__() call > showing the regression. > I suspect that the main slowdowns I am observing are due to the reduced performance in examples like M=matrix(GF(37),9,9,range(81)) [M.new_matrix(i,j) for i in range(1,50) for j in range(1,50)] and [M.new_matrix(5,6) for i in range(1,50) for j in range(1,50)] etc.(i.e., both the case where a lot of different parents are constructed and where the same parent keeps reoccurring). As far as I can see both of these perform dramatically worse now. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Severe regression in construction of matrices
It would be useful to have a concrete MatrixSpace.__call__() call showing the regression. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
