Matrix Chain Multiplications and Temporary Storage

Abstract:     Evaluating an expression in linear algebra using the known Basic Linear Algebra Subprograms library often requires temporary storage to hold intermediate results. However, matrix chain multiplication is typically analyzed in terms of time complexity, with the goal of minimizing the number of floating point operations (flops) for an expression. This paper investigates the less explored aspect, the space complexity of matrix chain multiplication. The focus is on finding all possible ways to translate an expression consisting of a matrix chain and a parenthesization into executable code, in order to explore the possibility of finding an evaluation order that require less storage requirement. The solution involves reframing the problem into finding all topological orderings for the input and translating the topological orderings into executable code. A driver function is employed to determine the evaluation order that minimizes the amount of storage required for a given set of dimensions. An empirical study yielded results indicating that, on average, only approximately 4.8 percent of the evaluated orderings fulfilled the minimum temporary storage requirement. Furthermore, the study confirmed that the evaluation order of an expression consisting of a matrix chain and a parenthesization does indeed impact the storage requirement.