Practice Phase Template

Here is a language-agnostic practice phase template for Strassen’s algorithm:

Understand the Problem Strassen’s algorithm is used for matrix multiplication. It improves upon the naive algorithm by reducing the number of multiplication operations. Instead of performing 8 multiplications for each 2x2 matrix, Strassen’s algorithm does it in 7 multiplications.
Task: Write down the standard procedure for 2x2 matrix multiplication. Then, try to write down the 7 multiplications that Strassen’s algorithm would perform on the same matrix.
Understand the Divide and Conquer Approach Strassen’s algorithm is a classic example of a divide and conquer approach. It works by dividing each input matrix into four equal-sized submatrices, then recursively computing the necessary products of these submatrices.
Task: Sketch a diagram of how a 4x4 matrix would be divided up by Strassen’s algorithm. Label each of the submatrices.
Understand the Recursive Calls Strassen’s algorithm makes several recursive calls to itself. It’s important to understand the flow of these calls and how they correspond to the computation of the submatrix products.
Task: Write down the sequence of recursive calls that would be made by Strassen’s algorithm on a 4x4 matrix. Identify which submatrix products each call is computing.
Write the Pseudo Code Before implementing the algorithm in code, write down the pseudo code for Strassen’s algorithm.
Task: Write a step-by-step description of Strassen’s algorithm. Your description should be detailed enough that you could convert it into code without having to make any additional design decisions.
Implement in Code Finally, the time has come to convert your understanding and pseudo code into a real code implementation.
Task: Write a function that multiplies two matrices using Strassen’s algorithm. Be sure to include the divide and conquer logic and the recursive calls.
Testing and Debugging As with any coding task, you’ll need to thoroughly test your function to make sure it’s working correctly.
Task: Write a set of test cases for your function. These should include some simple cases, such as 2x2 or 3x3 matrices, as well as some larger cases. Run your function on these test cases and debug any issues that arise.

Remember, the key to Strassen’s algorithm is understanding the divide and conquer approach and the flow of the recursive calls. Be sure to spend plenty of time on these aspects during the practice phase.

Targeted Drills in Python

Let’s break down the problem and build up the necessary skills gradually:

Beginner Level

Drill 1: Understand what a Matrix is

Task: Create a 2x2 matrix in Python using lists. Print the matrix.

1
2
3
matrix = [[1, 2], [3, 4]]
for row in matrix:
    print(row)

Drill 2: Matrix Addition

Task: Write a function in Python that adds two 2x2 matrices together.

1
2
3
4
5
6
def add_matrices(matrix1, matrix2):
    result = [[0, 0], [0, 0]]
    for i in range(2):
        for j in range(2):
            result[i][j] = matrix1[i][j] + matrix2[i][j]
    return result

Drill 3: Matrix Subtraction

Task: Write a function in Python that subtracts one 2x2 matrix from another.

1
2
3
4
5
6
def subtract_matrices(matrix1, matrix2):
    result = [[0, 0], [0, 0]]
    for i in range(2):
        for j in range(2):
            result[i][j] = matrix1[i][j] - matrix2[i][j]
    return result

Intermediate Level

Drill 4: Understanding Recursive Functions

Task: Write a recursive function in Python that calculates the factorial of a number.

1
2
3
4
5
def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

Drill 5: Naive Matrix Multiplication

Task: Write a function in Python that multiplies two 2x2 matrices together using the standard method (not Strassen’s algorithm).

1
2
3
4
5
6
7
def multiply_matrices(matrix1, matrix2):
    result = [[0, 0], [0, 0]]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                result[i][j] += matrix1[i][k] * matrix2[k][j]
    return result

Advanced Level

Drill 6: Dividing a Matrix

Task: Write a function in Python that takes a 4x4 matrix and divides it into four 2x2 matrices.

1
2
3
4
5
6
7
def divide_matrix(matrix):
    mid = len(matrix) // 2
    top_left = [[matrix[i][j] for j in range(mid)] for i in range(mid)]
    top_right = [[matrix[i][j] for j in range(mid, len(matrix))] for i in range(mid)]
    bottom_left = [[matrix[i][j] for j in range(mid)] for i in range(mid, len(matrix))]
    bottom_right = [[matrix[i][j] for j in range(mid, len(matrix))] for i in range(mid, len(matrix))]
    return top_left, top_right, bottom_left, bottom_right

Drill 7: Implementing Strassen’s Algorithm

Task: Write a function in Python that multiplies two 2x2 matrices together using Strassen’s algorithm. Use your divide_matrix function to divide the matrices, and your add_matrices and subtract_matrices functions to combine the results.

Let’s implement the Strassen’s Matrix Multiplication algorithm in Python for 2x2 matrices. We’ll build upon the functions developed in the earlier drills. Here is a basic version of the Strassen’s algorithm for 2x2 matrices:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def strassen(matrix1, matrix2):
    # Base case: 1x1 matrix
    if len(matrix1) == 1:
        return [[matrix1[0][0] * matrix2[0][0]]]

    # Split matrices into quarters
    a, b, c, d = divide_matrix(matrix1)
    e, f, g, h = divide_matrix(matrix2)

    # Calculate the seven products
    p1 = strassen(a, subtract_matrices(f, h))
    p2 = strassen(add_matrices(a, b), h)
    p3 = strassen(add_matrices(c, d), e)
    p4 = strassen(d, subtract_matrices(g, e))
    p5 = strassen(add_matrices(a, d), add_matrices(e, h))
    p6 = strassen(subtract_matrices(b, d), add_matrices(g, h))
    p7 = strassen(subtract_matrices(a, c), add_matrices(e, f))

    # Combine the seven products to get the final result
    top_left = add_matrices(subtract_matrices(add_matrices(p5, p4), p2), p6)
    top_right = add_matrices(p1, p2)
    bottom_left = add_matrices(p3, p4)
    bottom_right = subtract_matrices(subtract_matrices(add_matrices(p5, p1), p3), p7)

    # Combine the quarters to get the final result
    top = top_left + top_right
    bottom = bottom_left + bottom_right
    return top + bottom

Please note that this implementation only works for 2x2 matrices. To generalize this for nxn matrices where n is not necessarily 2, you would need to add code to handle the case where the matrices cannot be evenly split, typically by padding the matrices with zeros until they reach a size that is a power of 2.

Also remember that while Strassen’s algorithm is theoretically faster for very large matrices (with a time complexity of O(n^log2(7)), in practice, the overhead of the recursive calls and the added complexity of the calculations means it’s often slower than the standard method (O(n^3)) for small-to-moderately sized matrices.