Matrix multiplication for finite algebraic systems (Q1813190)

We consider finite algebraic systems having an arbitrary multiplication operator and an associative, commutative addition operator. We show that, for each such algebraic system, matrix multiplication is linear-time reducible to integer matrix multiplication. A consequence is that any fast algorithm for integer matrix multiplication can be converted into a fast algorithm for matrix multiplication over most finite algebraic systems. The number of integer matrix multiplications required depends only on the size of the given algebraic system. Thus, the reduction is linear for each algebraic system that is additively a finite commutative semigroup. We then show that our reduction is applicable not only to sequential computation, but can be extended to parallel computation. Finally, we apply these reductions to matrix closure where the finite algebraic system is a closed semiring.