Skip to content

Latest commit

 

History

History

CompilerForCAP

README.md

CompilerForCAP View code

Speed up and verify categorical algorithms

Documentation Latest Release Build Status of CAP_project Code Coverage
HTML stable documentation PDF stable documentation version date Build Status Code Coverage

Installation

  1. Install GAP.
  2. Download the latest version of CAP_project.
  3. Locate your user specific GAP root directory, for example by looking at the value of GAPInfo.UserGapRoot in a GAP session. Create this directory if it does not yet exist.
  4. Create a subdirectory named pkg of the user specific GAP root directory located in step 3.
  5. Extract the file downloaded in step 2 into the subdirectory pkg created in step 4.
  6. Launch GAP and execute LoadPackage( "CompilerForCAP" ); to verify that the installation was successful.

Introduction

Using the notions of category theory initially comes with a measurable performance overhead when implementing algorithms in CAP. The most obvious reason for this is the excessive amount of superfluous boxing and unboxing occurring during complex computations once we use several category constructors. As an example, consider the category

= FreydCategory( AdditiveClosure( RingAsCategory( R ) ) ).

built from a ring using category constructors available in FreydCategoriesForCAP.

We can visualize a computation in this category consisting of three operations as follows:

We start with an input in the top category and first have to successively unbox it to get the defining data in the ring where the actual computation is done. When this computation is finished, the result is successively boxed again so we can interpret it in the top category, producing the first intermediate result. Now this intermediate result has to be immediately unboxed again to perform the computations for the second operation, and the result of these computations is boxed again producing the second intermediate result. This process is repeated once more to get the final result.

CompilerForCAP was started to avoid repeatedly boxing and then subsequently unboxing the same data during a computation. It rewrites code so objects and morphisms in the input only have to be unboxed once at the beginning of a computation and boxed again once the computation is finished:

Thus, there is no penalty in writing high-level code: Using CompilerForCAP, any arbitrary high tower of categorical constructions can be transformed into low-level code, while writing the low-level code by hand would be error-prone if not impossible due to its complexity.

Additional features:

  • The example above highlights another problem: Although AdditiveClosure( RingAsCategory( R ) ) is equivalent to the category of matrices over R, we do not use existing, highly optimised matrix data structures and algorithms in the underlying computer algebra systems but instead descend all the way down to ring elements as our basic data structure. CompilerForCAP is able to detect such situations and replaces algorithms which iterate over ring elements by matrix operations in the underlying computer algebra systems where possible.
  • CAP can use the linear algebra in OSCAR/Nemo via the package NemoLinearAlgebraForCAP. If this package is used, CompilerForCAP is able to generate native OSCAR-code, see this pull request.
  • [planned] In some settings, e.g. in product categories, opportunities for parallelisation arise naturally. CompilerForCAP should be able to detect such situations and parallelise code using HPC-GAP or Julia where possible.

Funding