摘要：The well known algorithm of Volker Strassen for matrix mul- tiplication can only be used for (푚2 푘 × 푚2 푘 ) matrices. For arbitrary (푛 × 푛) matrices one has to add zero rows and columns to the given matrices to use Strassen’s algorithm. Strassen gave a strategy of how to set 푚 and 푘 for arbitrary 푛 to ensure 푛 ≤ 푚2 푘 . In this paper we study the number 푑 of ad- ditional zero rows and columns and the influence on the number of flops used by the algorithm in the worst case (푑 = 푛/16), best case (푑 = 1) and in the average case (푑 ≈ 푛/48). The aim of this work is to give a detailed analysis of the number of additional zero rows and columns and the additional work caused by Strassen’s bad parameters. Strassen used the parameters 푚 and 푘 to show that his matrix multiplication algorithm needs less than 4.7푛 log 2 7 flops. We can show in this paper, that these parameters cause an additional work of approximately 20 % in the worst case in comparison to the optimal strategy for the worst case. This is the main reason for the search for better parameters.
