Week 2 - Chain Matrix Multiply

The goal is this problem is, given a number of matrices what is the most efficient way to multiply them together?

Lets say we have matrices , , and and they have different sizes such that we can multiply . Whilst matrix multiplication might be associative there might be a more efficient way to multiply them together!

Cost of multiplying two matrices

Lets say with have two matrices (of size ) and (of size ) we set their product to be (of size ). To calculate a single entry in we need to multiply a row of (of size ) with a column of (of size ) which takes multiplications and additions. As has size this involves multiplications and additions.

Here the multiplications are the more costly operations so this is what we will focus on for the cost of this single operation.

Statement

Chain Matrix Multiply problem

For matrices , where has size , what is the minimum cost for computing ?

Link to original

Dynamic program set up

Let with be the minimum cost of multiplying .

The solution to the problem will be .

The base case will be .

The recursion step will be

To calculate we need to iteratively increase the difference between , the base case is the last case will be .

from typing import List
 
 
class UpperDiagonalMatrix:
    _matrix_size: int
    _matrix_values: List
 
    def __init__(self, matrix_size: int):
        self._matrix_size = matrix_size
        self._matrix_values = [0] * int((matrix_size * (matrix_size + 1)) / 2)
 
    def get(self, row: int, column: int) -> int:
        self._check_row_column(row, column)
        return self._matrix_values[self._get_index(row, column)]
 
    def set(self, row: int, column: int, value: int) -> None:
        self._check_row_column(row, column)
        self._matrix_values[self._get_index(row, column)] = value
 
    def _get_index(self, row: int, column: int) -> int:
        return self._get_column_offset(column) + (row - 1)
 
    def _get_column_offset(self, column: int) -> int:
        return int((column * (column - 1)) / 2)
 
    def _check_row_column(self, row: int, column: int) -> None:
        if row > column:
            raise ValueError("Row must be less than or equal to column")
        if row < 1:
            raise ValueError("Row must be greater than or equal to 0")
        if column > self._matrix_size:
            raise ValueError("Column must be less than matrix size")
 
 
class ChainMultiplySolver:
    _solution_array: UpperDiagonalMatrix
    _sizes: List[int]
    _number_of_matrices: int
 
    def solve(self, sizes: List[int]) -> int:
        self._setup_problem(sizes)
        self._fill_matrix_diagonally()
        return self._solution_array.get(1, self._number_of_matrices)
 
    def _setup_problem(self, sizes: List[int]) -> None:
        self._sizes = sizes
        self._number_of_matrices = len(sizes) - 1
        self._solution_array = UpperDiagonalMatrix(self._number_of_matrices)
 
    def _fill_matrix_diagonally(self) -> None:
        for difference in range(1, self._number_of_matrices):
            for lower_index in range(1, self._number_of_matrices-difference+1):
                upper_index = lower_index + difference
                self._solution_array.set(
                    lower_index,
                    upper_index,
                    self._solve_for_single_value(lower_index, upper_index),
                )
 
    def _solve_for_single_value(
	    self,
	    lower_index: int,
	    upper_index: int)
	-> int:
        return min(
            [
                self._solution_array.get(lower_index, split_index)
                + self._solution_array.get(split_index + 1, upper_index)
                + self._get_cost_of_multiplying_matrices(
                    lower_index, split_index, upper_index
                )
                for split_index in range(lower_index, upper_index)
            ]
        )
 
    def _get_cost_of_multiplying_matrices(
        self, left_index: int, middle_index: int, right_index: int
    ) -> int:
        return (
            self._sizes[left_index - 1]
            * self._sizes[middle_index]
            * self._sizes[right_index]
        )
 
 
if __name__ == "__main__":
    sizes = [5, 10, 5, 10, 5, 10, 5]
    solver = ChainMultiplySolver()
    print(solver.solve(sizes))

Lets look at the run time of this algorithm, let the number of sizes be . First _setup_problem takes as we have to fill half a matrix.

Working inside out, _get_cost_of_multiplying_matrices takes . Then _solve_for_single_value calls _get_cost_of_multiplying_matrices up to times so takes . Lastly _fill_matrix_diagonally has two for loops calling _solve_for_single_value up to times each giving the run time of _fill_matrix_diagonally to be .

So the cost of running solve .

Further questions

From Algorithms by S. Dasgupta, C. Papadimitriou, and U. Vazirani.

6.20 Optimal BST

Suppose you are given a list of words and their frequencies . We want to design a binary search tree such that at any node with word on the tree all child nodes to the left of the node have words that are alphabetically lower than whereas all child nodes to the right of the node have words that are alphabetically greater than it. We want to design such a tree where the average access time with respect to is minimised. i.e. if word has depth we want to minimise Write a dynamic program that solves this problem efficiently with the following:

Input: words (in sorted order); frequencies . Output: The binary search tree of lowest cost. (Not just the cost!)

6.7 Palindrome subsequence

Given a sequence devise an algorithm that returns the length of the longest palindromic subsequence. Its running time should be .

6.7 Palindrome substring (altered)

Given a sequence devise an algorithm that returns the length of the longest palindromic substring. Its running time should be .

Tips

• First find a solution using substrings.
• Then consider if substrings was necessary, could you use prefixes?