Data Types

Doubles vs ints

Current Implementation:

Currently with very few exceptions all our variables are double types i.e. 64-bit floating points. This might be surprising since all matrices have integer entries so it would initially seem that int64 types are a better alternative, both for accuracy and speed. But there's a fundamental problem with using integers instead of floating points:

• MATLAB does not natively support multiplication of integer matrices. This not a limitation of MATLAB perse, but rather of the library used to perform these computations, the Intel MKL (Math Kernel Library). This closed source library includes highly optimized and multithreaded algorithms for basic operations on matrices of floating points and is widely used for industrial and scientific purposes. Integer matrices and exact linear algebra are not nearly that prevalent hence the MKL has not been updated to support operations on them.

• While we could easily write our own high level algorithms for operations on integer matrices, they would be dreadfully slow, many orders of magnitude slower than the low level MKL ones.

Possible future implementation:

Perhaps in the future if we port the project to C++ we can use optimized libraries like Eigen and integer matrices for better accuracy and without incurring a performance penalty.

Singles vs Doubles

The matrices involved in our computations can have arbitrarily large entries in absolute value. Still, the maximum value of these matrices increases very slow with n,m; in the range 0-50 the maximum value was 256. So it would seem that we could get away with using single types (32-bit floating points) as opposed to doubles and get a decent performance boost. There are a few reasons why we haven't done that:

• MATLAB initializes all variables as doubles by default. So we have to explicitly ask it for singles (converting from doubles to singles after initialization incurs a performance cost). This is very easy but takes a bit more code.

• It's expected that when moving to C8 and beyond these maximum values are also increased. Therefore doubles might eventually be needed for accuracy, so we are essentially future-proofing.

• Some of our general functions, like smithoptimal, very much need the extra precision when handling random matrices. While the matrices used by the C4 algorithms are very far from random, we didn't want to compromise on the applicability of our general functions.

Sparse vs full

MATLAB supports sparse types, i.e. matrices where only the nonzero entries are recorded. This saves significantly on memory if the matrices have many zero entries, and potentially on some computations. We don't currently use sparse anywhere as our own experiments have shown that smithoptimalhedgeall is significantly slower with sparse matrices (and that's when the matrices that come up in our calculations can be 95% sparse). There are still two things worth trying:

• Optimize the Smith algorithm for sparse types.
• Use sparse matrices outside the Smith normal form function.

Cells vs matrices of strings

In MATLAB, matrices can only hold numeric types (eg double, int, logical) and character types (character, string) but not say, other matrices. But we need arrays of matrices for things like chain complexes, and there are two ways to achieve it:

• The "officially supported" way is to use cells. Cell arrays can hold arbitrary data types, but operations on them (such as searching, reshaping etc.) are unfortunately slower than numeric/character arrays. They also can't be vectorized for speed improvements.

• The "unofficial hack" way is to convert our matrices to strings using the built-in function num2str, store them in string arrays and convert them back to matrices using str2num. These two conversions would incur performance penalties, potentially nullifying any speed increases from using matrices over cells.

Ultimately, we have chosen to go with the first option as that's the way MATLAB intends cells to be used. It's also more elegant. It'd be interesting if the second option is faster.