Umeå universitets logga

umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Matrix Chain Multiplications and Temporary Storage
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
2023 (Engelska)Självständigt arbete på grundnivå (kandidatexamen), 10 poäng / 15 hpStudentuppsats (Examensarbete)
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.

Ort, förlag, år, upplaga, sidor
2023. , s. 27
Serie
UMNAD ; 1387
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:umu:diva-209736OAI: oai:DiVA.org:umu-209736DiVA, id: diva2:1766984
Externt samarbete
Lars Karlsson
Utbildningsprogram
Kandidatprogrammet i Datavetenskap
Presentation
2023-05-22, Umeå universitet, Umeå, 15:23 (Svenska)
Handledare
Examinatorer
Tillgänglig från: 2023-06-14 Skapad: 2023-06-13 Senast uppdaterad: 2023-06-14Bibliografiskt granskad

Open Access i DiVA

MatrixChainMultiplicationAndTemporaryStorage(2590 kB)514 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 2590 kBChecksumma SHA-512
04d5fe38218f1aa7b5e744aa8ed5242a90dfcfc01b346b0c02e2a760542650832e12f75136bf79f189a2bac071c2d7dbaa12b5f273aa767abb77fe98f03d5996
Typ fulltextMimetyp application/pdf

Sök vidare i DiVA

Av författaren/redaktören
Nilsson, Emil
Av organisationen
Institutionen för datavetenskap
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 514 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 298 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf