Matrix_Chain.H File Reference

Matrix-chain multiplication ordering 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 optimal matrix-chain multiplication order.
size_t	Aleph::matrix_chain_min_cost (const Array< size_t > &dims)
	Compute only the minimum multiplication cost.

Detailed Description

Matrix-chain multiplication ordering via interval DP.

Given a chain of matrices A1 x A2 x ... x An with dimensions dims[0] x dims[1], dims[1] x dims[2], ..., dims[n-1] x dims[n], computes the optimal parenthesization that minimizes scalar multiplications.

Definition in file Matrix_Chain.H.