Umeå University's logo

umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Matrix Chain Multiplications and Temporary Storage
Umeå University, Faculty of Science and Technology, Department of Computing Science.
2023 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

    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.

Place, publisher, year, edition, pages
2023. , p. 27
Series
UMNAD ; 1387
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:umu:diva-209736OAI: oai:DiVA.org:umu-209736DiVA, id: diva2:1766984
External cooperation
Lars Karlsson
Educational program
Bachelor of Science Programme in Computing Science
Presentation
2023-05-22, Umeå universitet, Umeå, 15:23 (Swedish)
Supervisors
Examiners
Available from: 2023-06-14 Created: 2023-06-13 Last updated: 2023-06-14Bibliographically approved

Open Access in DiVA

MatrixChainMultiplicationAndTemporaryStorage(2590 kB)500 downloads
File information
File name FULLTEXT01.pdfFile size 2590 kBChecksum SHA-512
04d5fe38218f1aa7b5e744aa8ed5242a90dfcfc01b346b0c02e2a760542650832e12f75136bf79f189a2bac071c2d7dbaa12b5f273aa767abb77fe98f03d5996
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Nilsson, Emil
By organisation
Department of Computing Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 500 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 296 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf