Matrix Chain Multiplications and Temporary Storage

  • Nilsson, Emil
ORKG logo Add to ORKG
Publication date
January 2023
Publisher
Umeå universitet, Institutionen för datavetenskap

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...

Extracted data

Loading...

Related items

O(n) ALGORITHM FOR DETERMINING A NEAR-OPTIMAL COMPUTATION ORDER OF MATRIX CHAIN PRODUCTS.
  • Chin, Francis Y
January 1978

Discussion of the computation of matrix chain products of the form M//1 multiplied by M//2 multiplie...

COMPUTATION OF MATRIX CHAIN PRODUCTS. PART I*
  • T. C. Hut
  • M. T. Shing
November 2015

Abstract. This paper considers the computation of matrix chain products of the form M1 x M2 ’’"...

Contents
  • Lars Karlsson
January 2009

We develop a prototype library for in-place (dense) matrix storage for-mat conversion between the ca...

We use cookies to provide a better user experience.