Four Russians and Mailman algorithms for multiplication by zero-one matrices
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.