High Performance Computing Experiments in Enumerative and Algebraic Combinatorics
Résumé
The goal of this abstract is to report on some parallel and high performance computations in combinatorics, each involving large datasets generated recursively: we start by presenting a small framework implemented in Sagemath [12] allowing performance of map/reduce like computations on such recursively defined sets. In the second part, we describe a methodology used to achieve large speedups in several enumeration problems involving similar map/reduced computations. We illustrate this methodology on the challenging problem of counting the number of numerical semigroups [5], and present briefly another problem about enumerating integer vectors upto the action of a permutation group [2]. We believe that these techniques are fairly general for those kinds of algorithms. 1 MAP-REDUCE IN COMBINATORICS In this first part, we present a small framework implemented in Sagemath [12] allowing performance map/reduce like computations on large recursively defined sets. Map-Reduce is a classical programming model for distributed computations where one maps a function on a large data set and uses a reduce function to summarize all the produced information. It has a large range of intensive applications in combinatorics: *