Starting with the work of Volker Strassen, algorithms for matrix multiplication have been developed which are time complexity-wise more efficient than the standard algorithm from the definition of multiplication. The general method of the developments has been viewing the bilinear mapping that matrix multiplication is as a three-dimensional tensor, where there is an exact correspondence between time complexity of the multiplication algorithm and tensor rank. The latter can be seen as a generalisation of matrix rank, being the minimum number of terms a tensor can be decomposed as. However, in contrast to matrix rank there is no general method of computing tensor ranks, with many values being unknown for important three-dimensional tensors. To further improve the theoretical bounds of the time complexity of matrix multiplication, support rank of tensors has been introduced, which is the lowest rank of tensors with the same support in some basis. The goal of this master's thesis has been to go through the history of faster matrix multiplication, as well as specifically examining the properties of support rank for general tensors. In regards to the latter, a complete classification of rank structures of support classes is made for the smallest non-degenerate tensor product space in three dimensions. From this, the size of a support can be seen affecting the pool of possible ranks within a support class. At the same time, there is in general no symmetry with regards to support size occurring in the rank structures of the support classes, despite there existing a symmetry and bijection between mirrored supports. Discussions about how to classify support rank structures for larger tensor product spaces are also included. / Från och med forskning gjord av Volker Strassen har flera algoritmer för matrismultiplikation utvecklats som är effektivare visavi tidskomplexitet än standardalgoritmen som utgår från defintionen av multiplikation. Generellt sett har metoden varit att se den bilinjära avbildningen som matrismultiplikation är som en tredimensionell tensor. Där används att det finns en exakt korrespondens mellan multiplikationsalgoritmens tidskomplexitet och tensorrang. Det sistnämnda är ett slags generalisering av matrisrang, och är minsta antalet termer en tensor kan skrivas som. Till skillnad frpn matrisrang finns ingen allmän metod för att beräkna tensorrang, och många värden är okända även för välstuderade och viktiga tensorer. För att hitta fler övre begränsningar på matrismultiplikations tidskomplexitet har stödrang av tensorer införts, som är den lägsta rangen bland tensor med samma stöd i en viss bas. Målet med detta examensarbete har varit att göra en genomgång av historien om snabbare matrismultiplikation, samt att specifikt undersöka egenskaper av stödrang för allmänna tredimensionella tensorer. För det sistnämnda görs en fullständig klassificering av rangstrukturer bland stödklasser för den minsta icke-degenererade tensorprodukten av tre vektorrum. Slutsatser är bl.a. att storleken av ett stöd kan ses påverka antalet möjliga ranger inom en stödklass. Samtidigt finns i allmänhet ingen symmetri med avseende på stödstorlek i stödklassernas rangstrukturer. Detta trots att det finns en symmetri och bijektion mellan speglade stöd. I arbetet ingår även en diskussion om hur stödrangstrukturer skulle kunna klassificeras för större tensorprodukter.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-344221 |
| Date | January 2023 |
| Creators | Andersson, Pelle |
| Publisher | KTH, Matematik (Avd.) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-SCI-GRU ; 2023:453 |
Page generated in 0.011 seconds