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

Published on 12 May 2024 09:40 PM
#Ada

How to resolve the algorithm Matrix chain multiplication step by step in the Ada 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 Ada programming language

Source code in the ada programming language

package mat_chain is
   type Vector is array (Natural range <>) of Integer;
   procedure Chain_Multiplication (Dims : Vector);
end mat_chain;


with Ada.Text_IO;           use Ada.Text_IO;
with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;

package body mat_chain is
   type Result_Matrix is
     array (Positive range <>, Positive range <>) of Integer;

   --------------------------
   -- Chain_Multiplication --
   --------------------------

   procedure Chain_Multiplication (Dims : Vector) is
      n : Natural := Dims'Length - 1;
      S : Result_Matrix (1 .. n, 1 .. n);
      m : Result_Matrix (1 .. n, 1 .. n);
      procedure Print (Item : Vector) is
      begin
         Put ("Array Dimension  = (");
         for I in Item'Range loop
            Put (Item (I)'Image);
            if I < Item'Last then
               Put (",");
            else
               Put (")");
            end if;
         end loop;
         New_Line;
      end Print;

      procedure Chain_Order (Item : Vector) is
         J    : Natural;
         Cost : Natural;
         Temp : Natural;

      begin
         for idx in 1 .. n loop
            m (idx, idx) := 0;
         end loop;

         for Len in 2 .. n loop
            for I in 1 .. n - Len + 1 loop
               J        := I + Len - 1;
               m (I, J) := Integer'Last;
               for K in I .. J - 1 loop
                  Temp := Item (I - 1) * Item (K) * Item (J);
                  Cost := m (I, K) + m (K + 1, J) + Temp;
                  if Cost < m (I, J) then
                     m (I, J) := Cost;
                     S (I, J) := K;
                  end if;
               end loop;
            end loop;
         end loop;
      end Chain_Order;

      function Optimal_Parens return String is
         function Construct
           (S : Result_Matrix; I : Natural; J : Natural)
            return Unbounded_String
         is
            Us         : Unbounded_String := Null_Unbounded_String;
            Char_Order : Character;
         begin
            if I = J then
               Char_Order := Character'Val (I + 64);
               Append (Source => Us, New_Item => Char_Order);
               return Us;
            else
               Append (Source => Us, New_Item => '(');
               Append (Source => Us, New_Item => Construct (S, I, S (I, J)));
               Append (Source => Us, New_Item => '*');
               Append
                 (Source => Us, New_Item => Construct (S, S (I, J) + 1, J));
               Append (Source => Us, New_Item => ')');
               return Us;
            end if;
         end Construct;

      begin
         return To_String (Construct (S, 1, n));

      end Optimal_Parens;

   begin
      Chain_Order (Dims);
      Print (Dims);
      Put_Line ("Cost             = " & Integer'Image (m (1, n)));
      Put_Line ("Optimal Multiply = " & Optimal_Parens);
   end Chain_Multiplication;

end mat_chain;


with Mat_Chain; use Mat_Chain;
with Ada.Text_IO; use Ada.Text_IO;

procedure chain_main is
   V1 : Vector := (5, 6, 3, 1);
   V2 : Vector := (1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2);
   V3 : Vector := (1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10);
begin
   Chain_Multiplication(V1);
   New_Line;
   Chain_Multiplication(V2);
   New_Line;
   Chain_Multiplication(V3);
end chain_main;

You may also check:How to resolve the algorithm Casting out nines step by step in the ZX Spectrum Basic programming language
You may also check:How to resolve the algorithm Vector step by step in the VBA programming language
You may also check:How to resolve the algorithm Range consolidation step by step in the Haskell programming language
You may also check:How to resolve the algorithm Number names step by step in the SQL programming language
You may also check:How to resolve the algorithm Statistics/Normal distribution step by step in the Fortran programming language