divide_and_conquer.strassen_matrix_multiplication

https://en.wikipedia.org/wiki/Strassen_algorithm

Attributes

matrix1

Functions

actual_strassen(→ list)

Recursive function to calculate the product of two matrices, using the Strassen

default_matrix_multiplication(→ list)

Multiplication only for 2x2 matrices

matrix_addition(matrix_a, matrix_b)

matrix_dimensions(→ tuple[int, int])

matrix_subtraction(matrix_a, matrix_b)

print_matrix(→ None)

split_matrix(→ tuple[list, list, list, list])

Given an even-length matrix, returns the top_left, top_right, bot_left, bot_right

strassen(→ list)

Multiplies two matrices using Strassen's algorithm, which runs in

Module Contents

divide_and_conquer.strassen_matrix_multiplication.actual_strassen(matrix_a: list, matrix_b: list) → list

Recursive function to calculate the product of two matrices, using the Strassen Algorithm. It only supports square matrices of any size that is a power of 2.

Strassen’s algorithm reduces the number of recursive multiplications needed to multiply two n x n matrices from the 8 required by the naive divide-and-conquer approach down to 7, at the cost of a few extra matrix additions/subtractions (which are cheaper, O(n^2), operations). Each matrix is split into four (n/2) x (n/2) quadrants; 7 products of quadrant combinations are computed recursively, and those products are combined with additions/subtractions to form the four quadrants of the result.

Time complexity: O(n^log2(7)) ~= O(n^2.807), an improvement over the O(n^3) of the standard/naive matrix multiplication algorithm. Space complexity: O(n^2) for storing the intermediate quadrant matrices, plus O(log n) recursion stack depth.

divide_and_conquer.strassen_matrix_multiplication.default_matrix_multiplication(a: list, b: list) → list

Multiplication only for 2x2 matrices

divide_and_conquer.strassen_matrix_multiplication.matrix_addition(matrix_a: list, matrix_b: list)
divide_and_conquer.strassen_matrix_multiplication.matrix_dimensions(matrix: list) → tuple[int, int]
divide_and_conquer.strassen_matrix_multiplication.matrix_subtraction(matrix_a: list, matrix_b: list)
divide_and_conquer.strassen_matrix_multiplication.print_matrix(matrix: list) → None
divide_and_conquer.strassen_matrix_multiplication.split_matrix(a: list) → tuple[list, list, list, list]

Given an even-length matrix, returns the top_left, top_right, bot_left, bot_right quadrant.

>>> split_matrix([[4,3,2,4],[2,3,1,1],[6,5,4,3],[8,4,1,6]])
([[4, 3], [2, 3]], [[2, 4], [1, 1]], [[6, 5], [8, 4]], [[4, 3], [1, 6]])
>>> split_matrix([
...     [4,3,2,4,4,3,2,4],[2,3,1,1,2,3,1,1],[6,5,4,3,6,5,4,3],[8,4,1,6,8,4,1,6],
...     [4,3,2,4,4,3,2,4],[2,3,1,1,2,3,1,1],[6,5,4,3,6,5,4,3],[8,4,1,6,8,4,1,6]
... ])
([[4, 3, 2, 4], [2, 3, 1, 1], [6, 5, 4, 3], [8, 4, 1, 6]], [[4, 3, 2, 4],
  [2, 3, 1, 1], [6, 5, 4, 3], [8, 4, 1, 6]], [[4, 3, 2, 4], [2, 3, 1, 1],
  [6, 5, 4, 3], [8, 4, 1, 6]], [[4, 3, 2, 4], [2, 3, 1, 1], [6, 5, 4, 3],
  [8, 4, 1, 6]])
divide_and_conquer.strassen_matrix_multiplication.strassen(matrix1: list, matrix2: list) → list

Multiplies two matrices using Strassen’s algorithm, which runs in O(n^log2(7)) ~= O(n^2.807) time, compared to O(n^3) for naive matrix multiplication. This implementation pads both input matrices with zeros until they are square matrices whose dimension is a power of 2 (required by the divide-and-conquer recursion in actual_strassen), performs the multiplication, then trims the padding back off the result.

>>> strassen([[2,1,3],[3,4,6],[1,4,2],[7,6,7]], [[4,2,3,4],[2,1,1,1],[8,6,4,2]])
[[34, 23, 19, 15], [68, 46, 37, 28], [28, 18, 15, 12], [96, 62, 55, 48]]
>>> strassen([[3,7,5,6,9],[1,5,3,7,8],[1,4,4,5,7]], [[2,4],[5,2],[1,7],[5,5],[7,8]])
[[139, 163], [121, 134], [100, 121]]
divide_and_conquer.strassen_matrix_multiplication.matrix1 = [[2, 3, 4, 5], [6, 4, 3, 1], [2, 3, 6, 7], [3, 1, 2, 4], [2, 3, 4, 5], [6, 4, 3, 1], [2, 3, 6,...