Skip to content

Fast parallel calculations in pure mathematics, e.g. Gröbner Bases

License

Notifications You must be signed in to change notification settings

DaveBarton/calculi

Repository files navigation

calculi

“Use all your cores”

Code size in bytes License

Pure mathematics is a rich source of cpu-intensive problems with very precise semantics. Typically its algorithms and data structures are side-effect free, which makes them surprisingly easy to parallelize efficiently in Haskell. Calculating Gröbner Bases is a good first example. So far, we have implemented the improved Buchberger algorithm for the case of polynomials over ℤ/pℤ, achieving near-linear speedups for up to at least 6 cores, and currently about 25x speedups counting garbage collection, or 32x not counting gc, for 60 cores. The Buchberger algorithm is not obviously or "embarrassingly" parallel, and we believe this is the first successful attempt to parallelize it.

You can see some timings at timings/timings.txt. If you want to compile and run these calculations on your machine, the quickest way is probably:

  1. Download and install ghcup, ghc 9.4.8 or later, and cabal from GHCup or Getting started - GHCup, if you haven't already.

  2. Download, or fork and clone, this repository (calculi).

  3. cd into your calculi directory, and run cabal run time-gb -- +RTS -N6 with "6" replaced by the number of cores you want to use (we suggest the number of physical performance cores on your machine minus 1 or 2, not counting hyperthreading or efficiency cores). You can also run cabal run time-gb -- --help to see more options.

About

Fast parallel calculations in pure mathematics, e.g. Gröbner Bases

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published