[sage-devel] Re: How would you like your parallel linear algebra ?
> > > In https://trac.sagemath.org/ticket/27444 we are exposing the parallel > versions (using OpenMP) of > fflas-ffpack routines used in SageMath. This is only about multicore > parallelism, based on OpenMP. > > +1 to having multicore linear algebra in Sage. I have hacked together some things in the past to do computations that would take too long serially, but they were really ugly, and I would prefer not to have to do them again. > We would like to discuss on the best design to expose them to the end > user: > > 1. Should the default behaviour be sequential or parallel ? > I think it should follow SAGE_NUM_THREADS as a default. This is something that you have to know at least a little bit of what you are doing to set it. Moreover, if you are doing this for building/testing, then you would want to do the same for computations. > > 2. If the default is parallel, how many cores should be used by default? I > guess the default should > be whatever value openmp_get_numthreads() returns, which is usually the > number of cores, however, in > most systems where hyperthreading is enabled, this means that we will use > twice as many cores as the > number of real cores, which will slow down the computation. > IMO, same as the above: Start with SAGE_NUM_THREADS and allow the user to modify it accordingly. > > 3. What interface do we want for the sage user who wants to > >3a switch between sequential and parallel, > >3b specify the number of cores to be used ? > > Should there be some kind of environment variable containing such > informations? > As Eric mentioned, I would expand upon Parallelism() as that would make a good unique and natural point to have all of this data. 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.
[sage-devel] Re: [sage-cell] Re: Is sagecell python3-ready?
On Thursday, 21 March 2019 22:48:08 UTC-6, Kwankyu Lee wrote: > > > > On Friday, March 22, 2019 at 12:56:58 AM UTC+9, Andrey Novoseltsev wrote: >> >> "languages" for SageMathCell are very different from kernels for Jupyter. >> SageMathCell keeps a bunch of preforked kernels (all are the same) >> > > And a new kernel is created for each interact cell. Right? This seems to > me a very bad architectural weakness of SageMathCell. > Right. Feel free to fix it ;-) Do you want to have the same process serving multiple clients simultaneously? With each client allowed to execute arbitrary code, in particular crashing that kernel? -- 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: Suggestion to speed up nauty_geng()?
On Fri, 22 Mar 2019, Ai Bo wrote: > With 12, I can't write to a file, it is at least 1500G. I can write to a > file up to around 300G at most. > That is why I am thinking how to divide the output of "geng 12". So > far, I don't have any idea. Any suggestion? You can (and should) use A/B -notation to geng: $ ./local/bin/geng 9 > /dev/null >A ./local/bin/geng -d0D8 n=9 e=0-36 >Z 274668 graphs generated in 0.15 sec $ ./local/bin/geng 9 0/10 > /dev/null >A ./local/bin/geng -X0x200d0D8 n=9 e=0-36 class=0/10 >Z 30682 graphs generated in 0.02 sec $ ./local/bin/geng 9 1/10 > /dev/null >A ./local/bin/geng -X0x200d0D8 n=9 e=0-36 class=1/10 >Z 26300 graphs generated in 0.02 sec and to verify this: ./local/bin/geng 9 | wc -l outputs 274668, just like for x in $(seq 0 9); do ./local/bin/geng 9 $x/10; done | wc -l (But I guess you must use splitting number bigger than 10, maybe ~100.) I think that you can run this in parallel and get you computation done in a day or two. But n=13 might need a supercomputer. -- Jori Mäntysalo Tampereen yliopisto - Ihminen ratkaisee -- 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] Integrals don't coincide with the ones directly done by maxima
On Friday, March 22, 2019 at 3:00:54 AM UTC-7, Dima Pasechnik wrote: > > > I would not mind to see not loading abs_integrate by default, and > modifications to examples and tests > to explicitly load abs_integrate before running affected examples... > > See: https://trac.sagemath.org/ticket/12731 The method proposed there would lead to much more finely grained control than simply not loading abs_integrate at all (which would be "ruined" by loading abs_integral for the rest of the session) -- 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: how does the res/mod in "geng" work?
It is very true that I am not familiar with geng, nor sagemath. I just installed on my machine a few days ago. The reason I want to modify geng.c is I don't have a way to partition the output of "geng 12". I have finished up to "geng 11" so far, mostly with manual work. I know how many "geng 12" generates. With "geng 12", the output, if written to a file, is too large for my machine to handle. I can write to about 300G, not anything like 1500G. That is why I am looking at res/mod, but it seems I can't easily control how large the output will be (or I just don't know how). So if I can modify "geng" program, I can control the output range. Any other suggestion? On Friday, March 22, 2019 at 12:28:32 AM UTC-7, nvcleemp wrote: > > Why would you want to modify geng.c? From your previous comments I get the > impression that you are not familiar with the algorithm that geng uses. > You're not even familiar with the way geng encodes graphs. In that case it > is almost guaranteed that you will break something if you modify it. > > So again, why would you want to modify it? If it is to obtain an even > split, then you can only do this by generating all graphs and then > splitting the output. The commands to do this without translating the > intermediate graphs to the Sage data structure have been shown in the other > thread. For anything larger than 12 this will still be too slow since there > are just so many graphs. > > The builtin splitting in geng works by generating the graphs and at a > certain depth in the generation tree counting the branches and only > proceeding if the number modulo mod is equal to res. This way not > everything is generated and if this is done at a suitable depth then the > splitting will be fairly equal. > > Cheers > Nico > > Op vr 22 mrt. 2019 om 06:06 schreef Ai Bo > >: > >> Sorry for not being clear. >> I meant I used geng —help. >> Apparently, the equal divide doesn’t help in my example case. >> Where is this geng.c file? If I modify geng.c, how should I build geng? >> >> On Thu, Mar 21, 2019 at 9:58 PM John H Palmieri > > wrote: >> >>> >>> >>> On Thursday, March 21, 2019 at 9:38:03 PM UTC-7, Ai Bo wrote: Saw this in the document: res/mod : only generate subset res out of subsets 0..mod-1 >>> >>> It would help if you gave some context for this. I'm guessing that most >>> Sage users won't know what "geng" is. I certainly didn't. I found by >>> searching the source code that you found this help message in the method >>> "nauty_geng" in graph_generators.py: you should have said this at the start >>> instead of just "saw this in the document". This makes it look like the >>> program "geng" comes from nauty. Now look at the nauty source code (there >>> is a tar file in the "upstream" directory, if you have a source code >>> version of Sage, also available at >>> http://files.sagemath.org/spkg/upstream/nauty/index.html). The nauty >>> manual says >>> >>> res/mod : only generate subset res out of subsets 0..mod-1 >>> >>> and >>> >>> See program text for much more information. >>> >>> The file geng.c says >>> >>> mod, res = a way to restrict the output to a subset. >>> All the graphs in G(n,mine..maxe) are divided >>> into >>> disjoint classes C(0,mod),C(1,mod),...,C(mod-1, >>> mod), >>> of very approximately equal size. >>> Only the class C(res,mod) is written. >>> >>> If the -x or -X switch is used, they must have >>> the >>> same value for different values of res; >>> otherwise >>> the partitioning may not be valid. In this case >>> (-x,-X with constant value), the usual >>> relationships >>> between modulo classes are obeyed; for example >>> C(3,4) = C(3,8) union C(7,8). This is not true >>> if 3/8 and 7/8 are done with -x or -X values >>> different from those used for 3/4. >>> >>> >>> How is the output divided? I tried with : ../sage-8.6/local/bin/geng 6 -C 0/7 and then I iterated from 0/7, 1/7, 2/7, 3/7 Why the output is 27, 21, 7, 1, 0, 0, ... How is the subset generated? Thank you. >>> -- >>> You received this message because you are subscribed to a topic in the >>> Google Groups "sage-devel" group. >>> To unsubscribe from this topic, visit >>> https://groups.google.com/d/topic/sage-devel/FJZoODSZK3Q/unsubscribe. >>> To unsubscribe from this group and all its topics, send an email to >>> sage-devel+...@googlegroups.com . >>> To post to this group, send email to sage-...@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
Re: [sage-devel] Re: Suggestion to speed up nauty_geng()?
Thank you!
I have resolved for up to "geng 11". It is the 12 that I need a solution. I
am aware how many graphs it generates.
I used multi-core manually, i.e., I launched multiple(24) geng program on a
24-core machine.
There is no doubt that geng is much faster than using sagemath's
nauty_geng(python). Thank you for the suggestion.
With 12, I can't write to a file, it is at least 1500G. I can write to a
file up to around 300G at most.
That is why I am thinking how to divide the output of "geng 12". So far,
I don't have any idea. Any suggestion?
On Friday, March 22, 2019 at 1:37:42 AM UTC-7, Jori Mäntysalo (TAU) wrote:
>
> OK, more explanation.
>
> * * *
>
> First I compare time for generating graphs in Nauty and in Sage. As plain
> graphs(n) uses nauty, I have test.sage containing
>
> print(sum(1 for _ in graphs(9)))
>
> It takes about 11½ seconds to run. I tested this with
>
> time ./sage test.sage
>
> Then,
>
> ./local/bin/geng 9 > /dev/null
>
> says "274668 graphs generated in 0.12 sec". So, if we just want to sample
> few graphs, we can get the speedup of ~50x. In other words, it is slow to
> convert data to Python internal format.
>
> OTOH number of many finite structures up to isomorphism grows very fast.
> So you can for example test some hypothesis to n=10 on a mobile phone,
> n=11 on a desktop computer and n=13 on a supercomputer. Same happens when
> you optimize code.
>
> * * *
>
> Next, does geng use multiple cpu cores? No. There is no difference between
>
> time taskset -c 1 ./local/bin/geng 9 > /dev/null
> time taskset -c 1-4 ./local/bin/geng 9 > /dev/null
>
> (You could also use "top" to see cpu usage.)
>
> * * *
>
> Now, how to use geng, make a sample, and then get them to Sage? First I
> generated all graphs (here to n=9 for speed):
>
> $ ./local/bin/geng 9 > g9
> >A ./local/bin/geng -d0D8 n=9 e=0-36
> >Z 274668 graphs generated in 0.12 sec
>
> OK, now I have a big list of strings:
>
> $ head -3 g9 ; tail -3 g9
> H??
> HA?
> HB?
> H]~
> H^~
> H~~
>
> Every line is an encoded graph. I want to make a sample, lets say every
> 1000:th line. Every line is (HERE, not when n=12) 8 bytes long. So,
>
> $ i=0; while [[ i -lt 274668 ]]; do dd if=g9 bs=8 skip=$i count=1 >>
> g9sample 2> /dev/null; i=$((i+1000)); done
>
> will give you a file of 275 lines:
>
> $ wc -l g9sample
> 275 g9sample
>
> And now I did a test2.sage -file:
>
> with open('g9sample', 'r') as fp:
> c = 0
> n = 0
> for line in fp:
> g = Graph(line, format='graph6')
> n += 1
> if g.is_connected():
> c += 1
> print("About %s percent are connected" % round(100.0*c/n))
>
> and
>
> $ ./sage test2.sage
> About 95 percent are connected
>
> Of course there are many other ways for this. For example you could read
> the whole file with Python and just skip 99,9% of lines, or skip every
> line with propability of 0.999 etc. Hopefully you get the idea from this.
>
> --
> Jori Mäntysalo
>
> Tampereen yliopisto - Ihminen ratkaisee
--
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: How would you like your parallel linear algebra ?
PS: an example of use of Parallelism() is
http://doc.sagemath.org/html/en/reference/manifolds/sage/manifolds/differentiable/affine_connection.html#sage.manifolds.differentiable.affine_connection.AffineConnection.riemann
Le vendredi 22 mars 2019 14:36:10 UTC+1, Eric Gourgoulhon a écrit :
>
> Hi,
>
> Regarding your question 3:
>
> Le vendredi 22 mars 2019 11:15:04 UTC+1, Clement Pernet a écrit :
>
>>
>> 3. What interface do we want for the sage user who wants to
>>
>>3a switch between sequential and parallel,
>>
>>3b specify the number of cores to be used ?
>>
>> Should there be some kind of environment variable containing such
>> informations?
>>
>>
> note that there exists already in Sage the singleton class Parallelism(),
> which has been invented precisely for this:
>
> http://doc.sagemath.org/html/en/reference/parallel/sage/parallel/parallelism.html
> For instance, in your case, it could be used as
>
> sage: Parallelism().set('fflas-ffpack', nproc=8)
>
> or any better name that you may figure out, e.g.
>
> sage: Parallelism().set('linear_algebra', nproc=8)
>
> Note that one can also use the shorten version
>
> sage: Parallelism().set(nproc=8)
>
> to trigger parallel computations in all declared fields, i.e. including
> fflas-ffpack if you have registered it in the dictionary attribute `_nrpoc`
> of class Parallelism.
>
> Best wishes,
>
> Eric.
>
--
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: How would you like your parallel linear algebra ?
Hi,
Regarding your question 3:
Le vendredi 22 mars 2019 11:15:04 UTC+1, Clement Pernet a écrit :
>
> 3. What interface do we want for the sage user who wants to
>
>3a switch between sequential and parallel,
>
>3b specify the number of cores to be used ?
>
> Should there be some kind of environment variable containing such
> informations?
>
>
note that there exists already in Sage the singleton class Parallelism(),
which has been invented precisely for this:
http://doc.sagemath.org/html/en/reference/parallel/sage/parallel/parallelism.html
For instance, in your case, it could be used as
sage: Parallelism().set('fflas-ffpack', nproc=8)
or any better name that you may figure out, e.g.
sage: Parallelism().set('linear_algebra', nproc=8)
Note that one can also use the shorten version
sage: Parallelism().set(nproc=8)
to trigger parallel computations in all declared fields, i.e. including
fflas-ffpack if you have registered it in the dictionary attribute `_nrpoc`
of class Parallelism.
Best wishes,
Eric.
--
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: Suggestion to speed up nauty_geng()?
On Thu, 21 Mar 2019, Simon King wrote: > Does either of you plan to open a ticket and make the functionality > available, that according to Jori is present in nauty but according > to Ai isn't wrapped in Sage? At least I do not. -- Jori Mäntysalo Tampereen yliopisto - Ihminen ratkaisee -- 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] How would you like your parallel linear algebra ?
Hi, May be what openblas is doing could be inspiring. Openblas (I hope it did not changed, I have tested this sometime ago) allows to use the number of thread defined for open_mp (by setting an environment variable or by program), and also to specify the number of threads for openblas. This is important (at least for me) when you do nested parallelism: you have say n threads, each one is using openblas and thus you dont want openblas to be parallel. Also, it is possible do get the numer of cpu in the program (but counting them twice in cas of hyperthreading, and more with exotic processors (4 threads / cpu with XeonPhi)). Thierry Le 22/03/2019 à 11:14, Clement Pernet a écrit : > Hi, > > In https://trac.sagemath.org/ticket/27444 we are exposing the parallel > versions (using OpenMP) of fflas-ffpack routines used in SageMath. This > is only about multicore parallelism, based on OpenMP. > > We would like to discuss on the best design to expose them to the end user: > > 1. Should the default behaviour be sequential or parallel ? > > 2. If the default is parallel, how many cores should be used by default? > I guess the default should be whatever value openmp_get_numthreads() > returns, which is usually the number of cores, however, in most systems > where hyperthreading is enabled, this means that we will use twice as > many cores as the number of real cores, which will slow down the > computation. > > 3. What interface do we want for the sage user who wants to > > 3a switch between sequential and parallel, > > 3b specify the number of cores to be used ? > > Should there be some kind of environment variable containing such > informations? > > Note that passing an extra argument is not (always) an option, as we > would like that the * operator for matrices benefits from this > parallization. > > In its current status, the branch on #27444 calls parallel fgemm when > multiplying two modn_dense matrices over the maximal number of available > OMP threads. It currently possible to use a specified number of threads > by exporting OMP_NUM_THREADS=XXX before lauching sage. > > Thanks for your feedback. > > Clément > -- 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] How would you like your parallel linear algebra ?
Hi, In https://trac.sagemath.org/ticket/27444 we are exposing the parallel versions (using OpenMP) of fflas-ffpack routines used in SageMath. This is only about multicore parallelism, based on OpenMP. We would like to discuss on the best design to expose them to the end user: 1. Should the default behaviour be sequential or parallel ? 2. If the default is parallel, how many cores should be used by default? I guess the default should be whatever value openmp_get_numthreads() returns, which is usually the number of cores, however, in most systems where hyperthreading is enabled, this means that we will use twice as many cores as the number of real cores, which will slow down the computation. 3. What interface do we want for the sage user who wants to 3a switch between sequential and parallel, 3b specify the number of cores to be used ? Should there be some kind of environment variable containing such informations? Note that passing an extra argument is not (always) an option, as we would like that the * operator for matrices benefits from this parallization. In its current status, the branch on #27444 calls parallel fgemm when multiplying two modn_dense matrices over the maximal number of available OMP threads. It currently possible to use a specified number of threads by exporting OMP_NUM_THREADS=XXX before lauching sage. Thanks for your feedback. Clément -- 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] Integrals don't coincide with the ones directly done by maxima
On Wed, Mar 20, 2019 at 1:37 PM Dima Pasechnik wrote: > > On Wed, Mar 20, 2019 at 1:27 PM mmarco wrote: > > > > So the bug is really in the abs_integrate package for maxima? In that case: > > is it really worth it to import it by default? > > removing it makes 7 tests fail in src/sage/interfaces/maxima_lib.py > > perhaps it should be applied more intelligently, but this seems to > require parsing for abs() and sgn()... I would not mind to see not loading abs_integrate by default, and modifications to examples and tests to explicitly load abs_integrate before running affected examples... > > > > > > > El miércoles, 20 de marzo de 2019, 13:58:46 (UTC+1), Dima Pasechnik > > escribió: > >> > >> On Wed, Mar 20, 2019 at 05:36:59AM -0700, mmarco wrote: > >> > I am trying to pinpoint the following bug: > >> > > >> > sage: integral(sqrt(1+cos(x)^2),x) > >> > -1/24*sin(3*x) + 1/8*sin(x) > >> > > >> > > >> > which is incorrect. One would think that maxima is returning a wrong > >> > answer, but if we ask directly to maxima, it leaves the integral as it > >> > is: > >> indeed, it is an elliptic integral, cannot be done in elementary > >> functions. > >> > >> The problem comes from src/sage/interfaces/maxima_lib.py > >> loading abs_integrate: > >> > >> sage --maxima > >> ;;; Loading #P"/mnt/opt/Sage/sage-dev/local/lib/ecl/sb-bsd-sockets.fas" > >> ;;; Loading #P"/mnt/opt/Sage/sage-dev/local/lib/ecl/sockets.fas" > >> ;;; Loading #P"/mnt/opt/Sage/sage-dev/local/lib/ecl/defsystem.fas" > >> ;;; Loading #P"/mnt/opt/Sage/sage-dev/local/lib/ecl/cmp.fas" > >> Maxima 5.41.0 http://maxima.sourceforge.net > >> using Lisp ECL 16.1.2 > >> Distributed under the GNU Public License. See the file COPYING. > >> Dedicated to the memory of William Schelter. > >> The function bug_report() provides bug reporting information. > >> (%i1) load(abs_integrate); > >> ARRSTORE: use_fast_arrays=false; allocate a new property hash table for > >> $INTABLE2 > >> (%o1) > >> /mnt/opt/Sage/sage-dev/local/share/maxima/5.41.0/share/contrib/integrati\ > >> on/abs_integrate.mac > >> (%i3) display2d : false; > >> (%o3) false > >> (%i4) integrate(sqrt(1+cos(x)^2),x); > >> > >> (%o4) ((2*sin(3*x)+6*sin(x))*false-sin(3*x)+3*sin(x))/24 > >> > >> Which does not make much sense, and apparently Sage gets the bit of it > >> after "false"... > >> > >> Dima > >> > > >> > sage: f = sqrt(1+cos(x)^2) > >> > sage: maxima.integrate(f._maxima_(),x) > >> > 'integrate(sqrt(cos(_SAGE_VAR_x)^2+1),_SAGE_VAR_x) > >> > > >> > which is the same result we get with sympy and fricas, and even by maxima > >> > itself: > >> > > >> > Maxima 5.41.0 http://maxima.sourceforge.net > >> > using Lisp ECL 16.1.2 > >> > Distributed under the GNU Public License. See the file COPYING. > >> > Dedicated to the memory of William Schelter. > >> > The function bug_report() provides bug reporting information. > >> > (%i1) integrate(sqrt(1+cos(x)^2),x); > >> > / > >> > [ 2 > >> > (%o1) I sqrt(cos (x) + 1) dx > >> > ] > >> > / > >> > > >> > So something strange is going on when we call maxima internally to > >> > compute > >> > that integral. I have tried to trace it, but I got lost in the > >> > intrincancies of the maxima interface. > >> > > >> > Does somebody know what exactly is causing this discrepancy? > >> > > >> > -- > >> > 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+...@googlegroups.com. > >> > To post to this group, send email to sage-...@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. -- 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: Cernay 2019: math software developers workshop: Sage, GAP, ...
Great!! My schedule is finally flexible enough this year! Looking forward to the dates. Is there going to be funding avaialble for students, postdoc from ODK? Best, J-P Le dimanche 17 mars 2019 09:02:05 UTC+1, Nicolas M. Thiéry a écrit : > >Hello, > > I am planning to organize this Spring one of our regular math software > developers workshop in Cernay (near Paris), in the the spirit of our > previous ones, including: > > - Sage Days 77: Sage developer days on packaging, portability, > documentation tools (2016) > https://wiki.sagemath.org/days77 > Sage & GAP days 85: packaging, portability, documentation tools (2017) > - https://wiki.sagemath.org/days85 > - Workshop on interfacing (math) software with low level libraries (2018) > https://github.com/OpenDreamKit/OpenDreamKit/issues/251 > > Themes will include packaging, portability, interfaces between > systems; more themes and projects are welcome; please edit the page: > > https://hackmd.io/j5FzB173Q4uaExUw-6Glpg > > If you are tentatively interested in participating, please fill in the > date poll before March 21st (next Thursday): > > https://framadate.org/EemimQr2YPZJlNnx > > Please forward to the relevant mailing lists (GAP, Oscar, Pari/GP, > Singular, Polymake, ...) or people. > > Once the date is fixed, I'll send an official announcement. > > Cheers, > Nicolas > -- > Nicolas M. Thiéry "Isil" > > http://Nicolas.Thiery.name/ > -- 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: Suggestion to speed up nauty_geng()?
OK, more explanation.
* * *
First I compare time for generating graphs in Nauty and in Sage. As plain
graphs(n) uses nauty, I have test.sage containing
print(sum(1 for _ in graphs(9)))
It takes about 11½ seconds to run. I tested this with
time ./sage test.sage
Then,
./local/bin/geng 9 > /dev/null
says "274668 graphs generated in 0.12 sec". So, if we just want to sample
few graphs, we can get the speedup of ~50x. In other words, it is slow to
convert data to Python internal format.
OTOH number of many finite structures up to isomorphism grows very fast.
So you can for example test some hypothesis to n=10 on a mobile phone,
n=11 on a desktop computer and n=13 on a supercomputer. Same happens when
you optimize code.
* * *
Next, does geng use multiple cpu cores? No. There is no difference between
time taskset -c 1 ./local/bin/geng 9 > /dev/null
time taskset -c 1-4 ./local/bin/geng 9 > /dev/null
(You could also use "top" to see cpu usage.)
* * *
Now, how to use geng, make a sample, and then get them to Sage? First I
generated all graphs (here to n=9 for speed):
$ ./local/bin/geng 9 > g9
>A ./local/bin/geng -d0D8 n=9 e=0-36
>Z 274668 graphs generated in 0.12 sec
OK, now I have a big list of strings:
$ head -3 g9 ; tail -3 g9
H??
HA?
HB?
H]~
H^~
H~~
Every line is an encoded graph. I want to make a sample, lets say every
1000:th line. Every line is (HERE, not when n=12) 8 bytes long. So,
$ i=0; while [[ i -lt 274668 ]]; do dd if=g9 bs=8 skip=$i count=1 >> g9sample
2> /dev/null; i=$((i+1000)); done
will give you a file of 275 lines:
$ wc -l g9sample
275 g9sample
And now I did a test2.sage -file:
with open('g9sample', 'r') as fp:
c = 0
n = 0
for line in fp:
g = Graph(line, format='graph6')
n += 1
if g.is_connected():
c += 1
print("About %s percent are connected" % round(100.0*c/n))
and
$ ./sage test2.sage
About 95 percent are connected
Of course there are many other ways for this. For example you could read
the whole file with Python and just skip 99,9% of lines, or skip every
line with propability of 0.999 etc. Hopefully you get the idea from this.
--
Jori Mäntysalo
Tampereen yliopisto - Ihminen ratkaisee
--
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: Suggestion to speed up nauty_geng()?
Hi David, On 2019-03-22, David Coudert wrote: > Our interface to nauty geng is in Python, but the difficulty is not here. > >- It takes time to build graphs from graph6 strings, and also to build >Sandpiles (12 for each graph) >- The number of biconnected graphs with 12 nodes is huge: 153.620.333.545 > >See https://oeis.org/A002218 > > Some parallelism could certainly help here, but there will be no miracle. If I understand correctly, this thread is about how to create an iterator for these graphs that does not try to generate all of them at once (and if I understand correctly, nauty/geng provides such iterator, it just isn't wrapped, but could easily be, since the output of geng, which is a stand-alone executable, can be read as a string [by a wrapper in Sage] and then translated into a graph). The miracle would be that in a doc test you could probably iterate over the first 10 graphs, demonstrating that you do not need to create the remaining 153,620,333,535. 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] Suggestion to speed up nauty_geng()?
On Thu, 21 Mar 2019 at 18:42, Ai Bo wrote:
> I found it. Thank you.
> I also tried the command listed above.
> I am confused. Where is this "I]~~w"?
> Is it a file? How did Graph load this?
>
> In my program, my code looks like this:
> i=12
> for G in graphs.nauty_geng(str(i) + " -C"):
> q = True
> for j in range (0,i):
> S = Sandpile(G,j)
> if S.identity() != S.max_stable():
> q = False
> break
>
>
>
> If I use geng to generate graphs, how should I load them in my for loop so
> I can check with Sandpile?
>
I think the bottleneck in you computation is not geng, but Sandpile: you
spend much more time computing Sandpile compared with asking geng for the
next graph.
> On Thursday, March 21, 2019 at 8:46:56 AM UTC-7, Dima Pasechnik wrote:
>>
>> On Thu, Mar 21, 2019 at 3:03 PM Ai Bo wrote:
>>
>> > is this "nauty26r7/geng" a program available?
>>
>> geng is installed in local/bin/ sub-directory of your Sage
>> installation, as a part of Sage's standard package nauty.
>>
>> > Also, as Python is slow, any part of the nautygen can be written in
>> other language, such as C/C++?
>>
>> it is written in C, so it's quite fast in this sense.
>>
>> >
>> > Thanks,
>> > Laura
>> >
>> > On Wednesday, March 20, 2019 at 11:48:38 PM UTC-7, Jori Mäntysalo (TAU)
>> wrote:
>> >>
>> >> On Thu, 21 Mar 2019, Ai Bo wrote:
>> >>
>> >> > Is there a way to "random access"? For example, access the nth
>> element
>> >> > in the "generator", instead of one by one?
>> >>
>> >> Kind of. As a most time is propably spent by creating Python data
>> >> structures for SageMath, you can use nautygen directly to generate
>> huge
>> >> number of graphs.
>> >>
>> >> As an example, it takes below 5 seconds to generate all biconnected
>> graphs
>> >> on 10 vertices, and I took third last one:
>> >>
>> >> $ nauty26r7/geng 10 -C | tail -3 | head -1
>> >> >A /home/jm58660/lat-koe/nauty26r7/geng -Cd2D9 n=10 e=10-45
>> >> >Z 9743542 graphs generated in 4.59 sec
>> >> I]~~w
>> >>
>> >> and now
>> >>
>> >> sage: g = Graph('I]~~w', format='graph6')
>> >> sage: g.is_biconnected()
>> >> True
>> >>
>> >>
>> >> --
>> >> Jori Mäntysalo
>> >>
>> >> Tampereen yliopisto - Ihminen ratkaisee
>> >
>> > --
>> > 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+...@googlegroups.com.
>> > To post to this group, send email to sage-...@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.
>
--
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] Suggestion to speed up nauty_geng()?
Thu 2019-03-21 18:47:37 UTC, Dima Pasechnik: > > Ideally one should create a fast interface from Python > to geng, probably using Cython, if it is not already done. PyNauty is discussed at - Sage Trac ticket 25506: Nauty interface for isomorphism checking and automorphism group computing https://trac.sagemath.org/ticket/25506 (needs review) -- 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] Suggestion to speed up nauty_geng()?
If you want to use the command that Jori gave in Sage, you can use the fact
that nauty_geng just runs geng and appends the option string after the
command. So if you want to generate the last three graphs that are returned
by geng for biconnected graphs on 10 vertices you can do this:
for g in graphs.nauty_geng("10 -C | tail -3"):
print g
Cheers
Nico
Op vr 22 mrt. 2019 om 08:29 schreef David Coudert :
> Our interface to nauty geng is in Python, but the difficulty is not here.
>
>- It takes time to build graphs from graph6 strings, and also to build
>Sandpiles (12 for each graph)
>- The number of biconnected graphs with 12 nodes is huge: 153.620.333.545
>See https://oeis.org/A002218
>
> Some parallelism could certainly help here, but there will be no miracle.
> A faster method for the tests on Sandpile is needed.
>
>
> Le jeudi 21 mars 2019 19:47:37 UTC+1, Dima Pasechnik a écrit :
>>
>>
>>
>> On Thu, 21 Mar 2019 18:42 Ai Bo, wrote:
>>
>>> I found it. Thank you.
>>> I also tried the command listed above.
>>> I am confused. Where is this "I]~~w"?
>>>
>>
>> This is a particular way to encode graph as a string of characters (8
>> bits per character).
>> Read Sage docs on Graph for details.
>>
>> Is it a file? How did Graph load this?
>>>
>>> In my program, my code looks like this:
>>> i=12
>>> for G in graphs.nauty_geng(str(i) + " -C"):
>>> q = True
>>> for j in range (0,i):
>>> S = Sandpile(G,j)
>>> if S.identity() != S.max_stable():
>>> q = False
>>> break
>>>
>>>
>>>
>>> If I use geng to generate graphs, how should I load them in my for loop
>>> so I can check with Sandpile?
>>>
>>
>> Ideally one should create a fast interface from Python to geng, probably
>> using Cython, if it is not already done.
>>
>>
>>> On Thursday, March 21, 2019 at 8:46:56 AM UTC-7, Dima Pasechnik wrote:
On Thu, Mar 21, 2019 at 3:03 PM Ai Bo wrote:
> is this "nauty26r7/geng" a program available?
geng is installed in local/bin/ sub-directory of your Sage
installation, as a part of Sage's standard package nauty.
> Also, as Python is slow, any part of the nautygen can be written in
other language, such as C/C++?
it is written in C, so it's quite fast in this sense.
>
> Thanks,
> Laura
>
> On Wednesday, March 20, 2019 at 11:48:38 PM UTC-7, Jori Mäntysalo
(TAU) wrote:
>>
>> On Thu, 21 Mar 2019, Ai Bo wrote:
>>
>> > Is there a way to "random access"? For example, access the nth
element
>> > in the "generator", instead of one by one?
>>
>> Kind of. As a most time is propably spent by creating Python data
>> structures for SageMath, you can use nautygen directly to generate
huge
>> number of graphs.
>>
>> As an example, it takes below 5 seconds to generate all biconnected
graphs
>> on 10 vertices, and I took third last one:
>>
>> $ nauty26r7/geng 10 -C | tail -3 | head -1
>> >A /home/jm58660/lat-koe/nauty26r7/geng -Cd2D9 n=10 e=10-45
>> >Z 9743542 graphs generated in 4.59 sec
>> I]~~w
>>
>> and now
>>
>> sage: g = Graph('I]~~w', format='graph6')
>> sage: g.is_biconnected()
>> True
>>
>>
>> --
>> Jori Mäntysalo
>>
>> Tampereen yliopisto - Ihminen ratkaisee
>
> --
> 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+...@googlegroups.com.
> To post to this group, send email to sage-...@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+...@googlegroups.com.
>>> To post to this group, send email to sage-...@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.
>
--
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
Re: [sage-devel] Re: how does the res/mod in "geng" work?
Why would you want to modify geng.c? From your previous comments I get the impression that you are not familiar with the algorithm that geng uses. You're not even familiar with the way geng encodes graphs. In that case it is almost guaranteed that you will break something if you modify it. So again, why would you want to modify it? If it is to obtain an even split, then you can only do this by generating all graphs and then splitting the output. The commands to do this without translating the intermediate graphs to the Sage data structure have been shown in the other thread. For anything larger than 12 this will still be too slow since there are just so many graphs. The builtin splitting in geng works by generating the graphs and at a certain depth in the generation tree counting the branches and only proceeding if the number modulo mod is equal to res. This way not everything is generated and if this is done at a suitable depth then the splitting will be fairly equal. Cheers Nico Op vr 22 mrt. 2019 om 06:06 schreef Ai Bo : > Sorry for not being clear. > I meant I used geng —help. > Apparently, the equal divide doesn’t help in my example case. > Where is this geng.c file? If I modify geng.c, how should I build geng? > > On Thu, Mar 21, 2019 at 9:58 PM John H Palmieri > wrote: > >> >> >> On Thursday, March 21, 2019 at 9:38:03 PM UTC-7, Ai Bo wrote: >>> >>> Saw this in the document: >>> res/mod : only generate subset res out of subsets 0..mod-1 >>> >> >> It would help if you gave some context for this. I'm guessing that most >> Sage users won't know what "geng" is. I certainly didn't. I found by >> searching the source code that you found this help message in the method >> "nauty_geng" in graph_generators.py: you should have said this at the start >> instead of just "saw this in the document". This makes it look like the >> program "geng" comes from nauty. Now look at the nauty source code (there >> is a tar file in the "upstream" directory, if you have a source code >> version of Sage, also available at >> http://files.sagemath.org/spkg/upstream/nauty/index.html). The nauty >> manual says >> >> res/mod : only generate subset res out of subsets 0..mod-1 >> >> and >> >> See program text for much more information. >> >> The file geng.c says >> >> mod, res = a way to restrict the output to a subset. >> All the graphs in G(n,mine..maxe) are divided >> into >> disjoint classes C(0,mod),C(1,mod),...,C(mod-1, >> mod), >> of very approximately equal size. >> Only the class C(res,mod) is written. >> >> If the -x or -X switch is used, they must have >> the >> same value for different values of res; >> otherwise >> the partitioning may not be valid. In this case >> (-x,-X with constant value), the usual >> relationships >> between modulo classes are obeyed; for example >> C(3,4) = C(3,8) union C(7,8). This is not true >> if 3/8 and 7/8 are done with -x or -X values >> different from those used for 3/4. >> >> >> >>> >>> How is the output divided? >>> >>> I tried with : ../sage-8.6/local/bin/geng 6 -C 0/7 >>> and then I iterated from 0/7, 1/7, 2/7, 3/7 >>> Why the output is 27, 21, 7, 1, 0, 0, ... >>> >>> How is the subset generated? >>> >>> Thank you. >>> >> -- >> You received this message because you are subscribed to a topic in the >> Google Groups "sage-devel" group. >> To unsubscribe from this topic, visit >> https://groups.google.com/d/topic/sage-devel/FJZoODSZK3Q/unsubscribe. >> To unsubscribe from this group and all its topics, 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. > -- 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] Suggestion to speed up nauty_geng()?
Our interface to nauty geng is in Python, but the difficulty is not here.
- It takes time to build graphs from graph6 strings, and also to build
Sandpiles (12 for each graph)
- The number of biconnected graphs with 12 nodes is huge: 153.620.333.545
See https://oeis.org/A002218
Some parallelism could certainly help here, but there will be no miracle. A
faster method for the tests on Sandpile is needed.
Le jeudi 21 mars 2019 19:47:37 UTC+1, Dima Pasechnik a écrit :
>
>
>
> On Thu, 21 Mar 2019 18:42 Ai Bo, > wrote:
>
>> I found it. Thank you.
>> I also tried the command listed above.
>> I am confused. Where is this "I]~~w"?
>>
>
> This is a particular way to encode graph as a string of characters (8 bits
> per character).
> Read Sage docs on Graph for details.
>
> Is it a file? How did Graph load this?
>>
>> In my program, my code looks like this:
>> i=12
>> for G in graphs.nauty_geng(str(i) + " -C"):
>> q = True
>> for j in range (0,i):
>> S = Sandpile(G,j)
>> if S.identity() != S.max_stable():
>> q = False
>> break
>>
>>
>>
>> If I use geng to generate graphs, how should I load them in my for loop
>> so I can check with Sandpile?
>>
>
> Ideally one should create a fast interface from Python to geng, probably
> using Cython, if it is not already done.
>
>
>> On Thursday, March 21, 2019 at 8:46:56 AM UTC-7, Dima Pasechnik wrote:
>>>
>>> On Thu, Mar 21, 2019 at 3:03 PM Ai Bo wrote:
>>>
>>> > is this "nauty26r7/geng" a program available?
>>>
>>> geng is installed in local/bin/ sub-directory of your Sage
>>> installation, as a part of Sage's standard package nauty.
>>>
>>> > Also, as Python is slow, any part of the nautygen can be written in
>>> other language, such as C/C++?
>>>
>>> it is written in C, so it's quite fast in this sense.
>>>
>>> >
>>> > Thanks,
>>> > Laura
>>> >
>>> > On Wednesday, March 20, 2019 at 11:48:38 PM UTC-7, Jori Mäntysalo
>>> (TAU) wrote:
>>> >>
>>> >> On Thu, 21 Mar 2019, Ai Bo wrote:
>>> >>
>>> >> > Is there a way to "random access"? For example, access the nth
>>> element
>>> >> > in the "generator", instead of one by one?
>>> >>
>>> >> Kind of. As a most time is propably spent by creating Python data
>>> >> structures for SageMath, you can use nautygen directly to generate
>>> huge
>>> >> number of graphs.
>>> >>
>>> >> As an example, it takes below 5 seconds to generate all biconnected
>>> graphs
>>> >> on 10 vertices, and I took third last one:
>>> >>
>>> >> $ nauty26r7/geng 10 -C | tail -3 | head -1
>>> >> >A /home/jm58660/lat-koe/nauty26r7/geng -Cd2D9 n=10 e=10-45
>>> >> >Z 9743542 graphs generated in 4.59 sec
>>> >> I]~~w
>>> >>
>>> >> and now
>>> >>
>>> >> sage: g = Graph('I]~~w', format='graph6')
>>> >> sage: g.is_biconnected()
>>> >> True
>>> >>
>>> >>
>>> >> --
>>> >> Jori Mäntysalo
>>> >>
>>> >> Tampereen yliopisto - Ihminen ratkaisee
>>> >
>>> > --
>>> > 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+...@googlegroups.com.
>>> > To post to this group, send email to sage-...@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+...@googlegroups.com .
>> To post to this group, send email to sage-...@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.
