Step by Step solution about How to resolve the algorithm Matrix chain multiplication step by step in the Julia programming language

Overview

This Julia code implements the algorithm for optimizing the order of matrix multiplications to minimize the total number of scalar multiplications. It uses dynamic programming with the u and v tables to store the best solutions for subproblems. The optim function returns the minimum number of scalar multiplications and the optimal order of matrix multiplications as a string.

Algorithm

The algorithm works by iterating over the possible subproblems, which are defined by the start and end indices of the matrices to be multiplied. For each subproblem, it evaluates all possible ways to split the matrices into two smaller subproblems and calculates the total number of scalar multiplications required for each split. The best split is the one that minimizes the total number of scalar multiplications. The algorithm stores the best split for each subproblem in the u table and the minimum number of scalar multiplications in the v table.

Once the algorithm has computed the best split for each subproblem, it constructs the optimal order of matrix multiplications by recursively calling the aux function. The aux function returns a string representing the order of matrix multiplications, where each matrix is represented by its start and end indices.

Example

The following is an example of how to use the algorithm to optimize the order of matrix multiplications:

julia> using MatrixChainMultiplications

julia> a = [1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2]

julia> MatrixChainMultiplications.optim(a)
(61000, "(1×(2×(3×(4×5×6×7))))×(8×(9×(10×(11×(12×13×14))))×15)")

In this example, the optimal order of matrix multiplications is to first multiply matrices 1 and 2, then multiply that result by matrix 3, and so on. This order minimizes the total number of scalar multiplications to 61,000.

module MatrixChainMultiplications

using OffsetArrays

function optim(a)
    n = length(a) - 1
    u = fill!(OffsetArray{Int}(0:n, 0:n), 0)
    v = fill!(OffsetArray{Int}(0:n, 0:n), typemax(Int))
    u[:, 1] .= -1
    v[:, 1] .= 0
    for j in 2:n, i in 1:n-j+1, k in 1:j-1
        c = v[i, k] + v[i+k, j-k] + a[i] * a[i+k] * a[i+j]
        if c < v[i, j]
            u[i, j] = k
            v[i, j] = c
        end
    end
    return v[1, n], aux(u, 1, n)
end

function aux(u, i, j)
    k = u[i, j]
    if k < 0
        return sprint(print, i)
    else
        return sprint(print, '(', aux(u, i, k), '×', aux(u, i + k, j - k), ")")
    end
end

end  # module MatrixChainMultiplications


println(MatrixChainMultiplications.optim([1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2]))
println(MatrixChainMultiplications.optim([1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10]))