How to resolve the algorithm Matrix chain multiplication step by step in the Lua programming language

Published on 12 May 2024 09:40 PM
#Lua

How to resolve the algorithm Matrix chain multiplication step by step in the Lua programming language

Table of Contents

Problem Statement

Using the most straightfoward algorithm (which we assume here), computing the product of two matrices of dimensions (n1,n2) and (n2,n3) requires n1n2n3 FMA operations. The number of operations required to compute the product of matrices A1, A2... An depends on the order of matrix multiplications, hence on where parens are put. Remember that the matrix product is associative, but not commutative, hence only the parens can be moved. For instance, with four matrices, one can compute A(B(CD)), A((BC)D), (AB)(CD), (A(BC))D, (AB)C)D. The number of different ways to put the parens is a Catalan number, and grows exponentially with the number of factors. Here is an example of computation of the total cost, for matrices A(5,6), B(6,3), C(3,1): In this case, computing (AB)C requires more than twice as many operations as A(BC). The difference can be much more dramatic in real cases. Write a function which, given a list of the successive dimensions of matrices A1, A2... An, of arbitrary length, returns the optimal way to compute the matrix product, and the total cost. Any sensible way to describe the optimal solution is accepted. The input list does not duplicate shared dimensions: for the previous example of matrices A,B,C, one will only pass the list [5,6,3,1] (and not [5,6,6,3,3,1]) to mean the matrix dimensions are respectively (5,6), (6,3) and (3,1). Hence, a product of n matrices is represented by a list of n+1 dimensions. Try this function on the following two lists: To solve the task, it's possible, but not required, to write a function that enumerates all possible ways to parenthesize the product. This is not optimal because of the many duplicated computations, and this task is a classic application of dynamic programming. See also Matrix chain multiplication on Wikipedia.

Let's start with the solution:

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

Source code in the lua programming language

-- Matrix A[i] has dimension dims[i-1] x dims[i] for i = 1..n
local function MatrixChainOrder(dims)
    local m = {}
    local s = {}
    local n = #dims - 1;
    -- m[i,j] = Minimum number of scalar multiplications (i.e., cost)
    -- needed to compute the matrix A[i]A[i+1]...A[j] = A[i..j]
    -- The cost is zero when multiplying one matrix
    for i = 1,n do
        m[i] = {}
        m[i][i] = 0
        s[i] = {}
    end

    for len = 2,n do -- Subsequence lengths
        for i = 1,(n - len + 1) do
            local j = i + len - 1
            m[i][j] = math.maxinteger
            for k = i,(j - 1) do
                local cost = m[i][k] + m[k+1][j] + dims[i]*dims[k+1]*dims[j+1];
                if (cost < m[i][j]) then
                    m[i][j] = cost;
                    s[i][j] = k; --Index of the subsequence split that achieved minimal cost
                end
            end
        end
    end
    return m,s
end

local function printOptimalChainOrder(s)
    local function find_path(start,finish)
        local chainOrder = ""
        if (start == finish) then
            chainOrder = chainOrder .."A"..start
        else
            chainOrder = chainOrder .."(" .. 
                         find_path(start,s[start][finish]) ..
                         find_path(s[start][finish]+1,finish) .. ")"
        end
        return chainOrder
    end
    print("Order : "..find_path(1,#s))
end

local dimsList = {{5, 6, 3, 1},{1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2},{1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10}}

for k,dim in ipairs(dimsList) do
    io.write("Dims  : [")
    for v=1,(#dim-1) do
        io.write(dim[v]..", ")
    end
    print(dim[#dim].."]")
    local m,s = MatrixChainOrder(dim)
    printOptimalChainOrder(s)
    print("Cost  : "..tostring(m[1][#s]).."\n")
end

You may also check:How to resolve the algorithm Numerical integration step by step in the Lua programming language
You may also check:How to resolve the algorithm Arrays step by step in the Maxima programming language
You may also check:How to resolve the algorithm Guess the number step by step in the Mercury programming language
You may also check:How to resolve the algorithm Parameterized SQL statement step by step in the Arturo programming language
You may also check:How to resolve the algorithm Hamming numbers step by step in the Nim programming language