Matrix Multiplication over Small Finite Fields on MIMD Architectures

Many problems in computational representation theory of finite groups require calculations with huge dense matrices over very small finite fields (cf. [5] and [7]). In this paper, we concentrate on matrix multiplication of matrices over GF(2) though most of the ideas can be generalized in some way to other matrix algorithms and to other small finite fields.In the first chapter, we present some ideas how to accelerate earlier programs and considerations how to choose the best possible corresponding tuning parameters. We show that these considerations and the running times of an implementation on one thin node of an IBM SP/2 fit well together.In the second chapter, we discuss different approaches for the parallelization of the algorithms, which all use the message-passing paradigm. We study the influences between the tuning parameters and different communication patterns. This is explained looking at several examples performed on the SP/2.