Matrix multiplication is associative, so every bracketing gives the same product, but the cost can differ enormously. This example finds the cheapest bracketing with dynamic programming, written as a tabled relation over intervals of the chain.
Run it in the playground · Source
Multiplying a p×q matrix by a q×r matrix takes p·q·r scalar multiplications. For the chain A1 (30×35), A2 (35×15), A3 (15×5), A4 (5×10), A5 (10×20), A6 (20×25), which bracketing minimizes the total?
dim(0, 30).
dim(1, 35).
dim(2, 15).
dim(3, 5).
dim(4, 10).
dim(5, 20).
dim(6, 25).
matrix_count(6).
Matrix i has dimensions dim(i-1) × dim(i), so seven numbers describe six
matrices.
:- table cost/3.
cost(I, I, 0) :- matrix_count(N), between(1, N, I).
cost(I, J, Cost) :-
(I < J),
aggregate_min(Splitcost, K,
(between(I, J, K),
(K < J),
cost(I, K, Left),
(K1 is K + 1),
cost(K1, J, Right),
(I0 is I - 1),
dim(I0, Rows),
dim(K, Shared),
dim(J, Cols),
(First is Rows * Shared),
(Multcost is First * Cols),
(Partial is Left + Right),
(Splitcost is Partial + Multcost)),
Cost, _bestk).
The cheapest way to multiply matrices I..J is the best split K: multiply I..K,
multiply K+1..J, then combine the two results. :- table cost/3. stores each
interval’s answer, turning an exponential recursion into 21 shared
subproblems.
eyeprolog examples/matrix-chain-order.pl
matrix_chain_answer(min_cost, 15125).
matrix_chain_answer(best_split_1_6, 3).
matrix_chain_answer(best_order, product(product(matrix(1), product(matrix(2), matrix(3))), product(product(matrix(4), matrix(5)), matrix(6)))).
matrix_chain_answer(subproblem_count, 21).
The best order is (A1(A2A3))((A4A5)A6), costing 15,125 multiplications, with the top-level split after A3.
step(matrix_chain_answer(min_cost, 15125), rule(15), ['Cost' = 15125], [cost(1, 6, 15125)]).
step(cost(1, 6, 15125),
rule(11),
['I' = 1, 'J' = 6, 'Cost' = 15125],
[1 < 6,
aggregate_min(Key, Value, (between(1, 6, Value), Value < 6, cost(1, Value, Left), K1 is Value + 1, cost(K1, 6, Right), I0 is 1 - 1, dim(I0, Rows), dim(Value, Shared), dim(6, Cols), First is Rows * Shared, Multcost is First * Cols, Partial is Left + Right, Key is Partial + Multcost), 15125, 3)]).
The minimum cost of the whole chain comes from the recursive rule: the
aggregate_min/5 over all split points found 15,125 at split 3.
condition('C1', resolution, ok, 21).
condition('C5', re_decision, ok, 10).
steps(38).
verified(21).
recomputed(10).
trusted(7).
verdict(checked_with_obligations).
21 rule steps replay and 10 arithmetic steps are recomputed. The 7 trusted
steps are aggregates: six aggregate_min/5 choices of a best split and one
countall/2. They are listed as obligations because the checker does not
re-run a whole optimization; it records exactly which minimum each conclusion
relies on.
dim(3, 5) to dim(3, 50) and predict whether the best split moves.:- table cost/3. and compare the run time. What does --stats
show?naive_cost/2 for the left-to-right order ((((A1A2)A3)A4)A5)A6 and
compare it with 15,125.Learn more in The Art of EyeProlog, Chapter 13.