and the lower-right is . Wherever the operations require it, dimensions of are zero padded to first. Note, for instance, that the product is only used in the lower row of the output, so is only required to be rows high; and thus the left factor used to generate it need only be rows high; accordingly, there is no need to pad that sum to rows; it is only necessary to pad to columns to match . Furthermore, there is no need for the matrices to be square. Non-square matrices can be split in half using the same methods, yielding smaller non-square matrices. If the matrices are sufficiently non-square it will be worthwhile reducing the initial operation to more square products, using simple methods which are essentially , for instance: A product of size can be done as 20 separate operations, arranged to form the result; A product of size can be done as 10 separate operations, summed to form the result. These techniques will make the implementation more complicated, compared to simply padding to a power-of-two square; however, it is a reasonable assumption that anyone undertaking an implementation of Strassen, rather than conventional multiplication, will place a higher priority on computational efficiency than on simplicity of the implementation. In practice, Strassen's algorithm can be implemented to attain better performance than conventional multiplication even for small matrices, for matrices that are not at all square, and without requiring workspace beyond buffers that are already needed for a high-performance conventional multiplication. See also Computational complexity of mathematical operations Gauss–Jordan elimination Coppersmith–Winograd algorithm Z-order matrix representation Karatsuba algorithm, for multiplying n-digit integers in instead of in time Toom-Cook algorithm, a faster generalization of the Karatsuba algorithm that permits recursive divide-and-conquer decomposition into more than 2 blocks at a time Gauss's complex multiplication algorithm multiplies two complex numbers using 3 real multiplications instead of 4 References Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. . Chapter 28: Section 28.2: Strassen's algorithm for matrix multiplication, pp. 735–741. External links (also includes formulas for fast matrix inversion) Tyler J. Earnest, Strassen's Algorithm on the Cell Broadband Engine Matrix multiplication algorithms