Amri, this is quiet an impressive speed difference! If it's not too difficult I'd be interested in seeing the timings for computing the full character tables using your implemenentation of Murnaghan-Nakayama, symmetric functions and the "in-built" character_table() method for the symmetric groups..
Cheers, Andrew Saturday, 21 December 2013 18:29:47 UTC+1, Amri wrote: > > Just to convince (myself and) Nicolas, I have a quick and dirty > implementation of the recursive Murnaghan-Nakayama formula. > https://www.dropbox.com/s/8xfz4jo8bzjf7kf/mnr.py > There are two functions implemented here, both of which compute a > character value of the symmetric group. > The first uses symmetric functions exactly as suggested by Darij and is > called X > The second used the recursive Murnaghan-Nakayama formula and is called MNR > > A typical timeit for a partition of 40: > > sage: la = Partitions(40).random_element() > sage: mu = Partitions(40).random_element() > sage: timeit('X(la,mu)') > 5 loops, best of 3: 854 ms per loop > sage: timeit('MNR(la,mu)') > 125 loops, best of 3: 2.62 ms per loop > > And most importantly: > > sage: X(la,mu)==MNR(la,mu) > True > > So if you just need one character value of a large symmetric group, the > recursive formula of Murnaghan-Nakayama is 300 times faster. > > Another question: what is a good name for this function? > > best, > Amri. > > On Saturday, December 21, 2013 5:14:56 PM UTC+5:30, darijgrinberg wrote: >> >> Hi Nicolas, >> >> the question is, I think, the one of doing it for one partition vs. >> doing it for all partitions of n. In the latter case, I think we >> should do what we say (replace Symmetrica if we can do it better, or >> leave it be if we can't), but Amri has been talking about the former >> case and there is definitely room for improvement there when n is >> large. And I think it conceptually fits into partition.py, although >> most people like myself probably won't ever use n's greater than 20 or >> so. >> >> Best regards, >> Darij >> >> On Fri, Dec 20, 2013 at 3:11 PM, Nicolas M. Thiery >> <nicolas...@u-psud.fr> wrote: >> > Hi! >> > >> > On Fri, Dec 20, 2013 at 12:37:51PM +0100, Darij Grinberg wrote: >> >> But you are right in saying that this is not an optimal solution, >> and it >> >> might be better to implement the Murnaghan-Nakayama rule directly >> as a >> >> hook-removal algorithm rather than by building the whole s and p >> bases of >> >> Sym. >> > >> > Well, "building the whole s and p bases of Sym" is not a deal as big >> > as the formulation may suggest :-) On a fresh Sage session: >> > >> > sage: %time SymmetricFunctions(QQ).s() >> > CPU times: user 0.19 s, sys: 0.03 s, total: 0.23 s >> > Wall time: 0.27 s >> > Symmetric Functions over Rational Field in the Schur basis >> > sage: %time SymmetricFunctions(QQ).p() >> > CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s >> > Wall time: 0.00 s >> > Symmetric Functions over Rational Field in the powersum basis >> > >> > And from now on the overhead of going through Sym to compute >> > characters is essentially negligible. If really you want to save on >> > this minimal overhead, look at the symmetric functions code, and call >> > Symmetrica directly. >> > >> > On the other hand, what would be costly would be to have to maintain >> > two implementations of the MN rules just because they are used in >> > different places. If someone has an alternative implementation of MN >> > that is more efficient than that of Symmetrica, then we should drop >> > that piece of Symmetrica, and have the symmetric function code use the >> > alternative implementation. >> > >> > Cheers, >> > Nicolas >> > -- >> > Nicolas M. Thiéry "Isil" <nth...@users.sf.net> >> > http://Nicolas.Thiery.name/ >> > >> > -- >> > You received this message because you are subscribed to the Google >> Groups "sage-combinat-devel" group. >> > To unsubscribe from this group and stop receiving emails from it, send >> an email to sage-combinat-devel+unsubscr...@googlegroups.com. >> > To post to this group, send email to sage-comb...@googlegroups.com. >> > Visit this group at http://groups.google.com/group/sage-combinat-devel. >> >> > For more options, visit https://groups.google.com/groups/opt_out. >> > -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-combinat-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-combinat-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-combinat-devel. For more options, visit https://groups.google.com/groups/opt_out.
