Matrix_Chain.H File Reference

Matrix-chain multiplication optimization via interval DP. More...

#include <limits>
#include <string>
#include <cstddef>
#include <ah-errors.H>
#include <tpl_array.H>

Include dependency graph for Matrix_Chain.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	Aleph::Matrix_Chain_Result
	Result of matrix-chain multiplication optimization. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.
namespace	Aleph::matrix_chain_detail

Functions
size_t	Aleph::matrix_chain_detail::checked_add (const size_t a, const size_t b, const char *ctx)
size_t	Aleph::matrix_chain_detail::checked_mul (const size_t a, const size_t b, const char *ctx)
size_t	Aleph::matrix_chain_detail::scalar_cost (const size_t di, const size_t dk, const size_t dj)
void	Aleph::matrix_chain_detail::build_parens (const Array< Array< size_t > > &s, size_t i, size_t j, std::string &out)
Matrix_Chain_Result	Aleph::matrix_chain_order (const Array< size_t > &dims)
	Compute the optimal matrix-chain multiplication order.
size_t	Aleph::matrix_chain_min_cost (const Array< size_t > &dims)
	Compute only the minimum multiplication cost (value only).

Detailed Description

Matrix-chain multiplication optimization via interval DP.

The matrix-chain multiplication problem is a classic optimization problem that seeks the most efficient way to multiply a given sequence of matrices. Since matrix multiplication is associative, the order in which we parenthesize the product can significantly affect the number of scalar multiplications required.

This header provides an interval dynamic programming solution to find:

• The minimum number of scalar multiplications needed.
• The optimal parenthesization (e.g., "((A1 A2) A3)").

Complexity

Algorithm	Time	Space
matrix_chain_order	O(n^3)	O(n^2)
matrix_chain_min_cost	O(n^3)	O(n^2)

Example

// Suppose we have four matrices:
// A1: 10 x 30
// A2: 30 x 5
// A3: 5 x 60
// A4: 60 x 10
Array<size_t> dims = {10, 30, 5, 60, 10};
 
// Find optimal order and parenthesization
auto res = Aleph::matrix_chain_order(dims);
 
// res.min_multiplications = 5000
// res.parenthesization = "((A1 A2) (A3 A4))"
 
// Or just get the cost
size_t cost = Aleph::matrix_chain_min_cost(dims); // Returns 5000

Definition in file Matrix_Chain.H.