Saturday, August 24, 2019

M4RI library

This is just a quick note referencing the M4RI library that implements the "Method of four Russians (M4RM)", and the Strassen-Winograd algorithm, see these references.

Among other things, the M4RI library provides matrix inversion in GF(2) and computing the row-echelon form of a given matrix in GF(2) which is relevant for
  • finding the polynomial generating an LFSR sequence (see here and here), and
  • for detecting the presence of convolutional codes in a given bit stream by analyzing rank-deficiencies (see here and here).

M4RI seems to be available on most linux distributions. Although its latest release is from 2014, it looks quite mature and there are recent commits to the M4RI repository.

It is now being used in https://github.com/hcab14/signal-analysis.

No comments: