High Performance Combinatorics
Time: 11:00 -- Location: Salle Philippe Flajolet du LIX
partly joint with Jean Fromentin
In this talk, I will report on several experiments around large scale enumerations in enumerative and algebraic combinatorics.
In a first part, I'll present a small framework implemented in Sagemath allowing to perform map/reduce like computations on large recursively defined sets. Though it doesn't really qualify as HPC, it allowed to efficiently parallelize a dozen of experiments ranging from Coxeter group and representation theory of monoids to the combinatorial study of the C3 linearization algorithm used to compute the method resolution order (MRO) in script language such as Python and Perl.
In a second part, I'll describe a methodology used to achieve large speedups in several enumeration problems. Indeed, in many combinatorial structures (permutations, partitions, monomials, young tableaux), the data can be encoded as a small sequence of small integers that can often efficiently be handled by a creative use of vector instructions. Through the challenging example of numerical monoids, I will then report on how Cilkplus allows for a extremely fast parallelization of the enumeration. Indeed, we have been able to enumerate sets with more that 10^15 elements on a single multicore machine.