Four Russians and Mailman algorithms for multiplication by zero-one matrices

English

Séminaire Modèles et Algorithmes Déterministes: CASYS

2/07/2019 - 09:30 David Saunders Salle 106 - Batiment IMAG

An algorithm commonly known as the method of the four Russians is widely used for matrix multiplication over GF2 and GF3.  A similar but more recent method is the mailman algorithm.  It is a kind of dual to the four Russians.  I point out that these algorithms can be used over any field or ring whenever one matrix in the multiplication has very few distinct entry values, for example a graph adjacency matrix.  Mailman is best suited for certain matrix shapes which arise, for example, in applications such as the block Berlekamp/Massey algorithm.  I will present and discuss these two matrix multiplication algorithms.