1968 var Strassens algoritm en av de stora genombrotten inom matrisanalyser. I denna rapport kommer teorin av Volker Strassens algoritm för matrismultiplikationer tillsammans med teorier om precisioner att presenteras. Även fördelar med att använda denna algoritm jämfört med naiva matrismultiplikation och dess implikationer, samt hur den presterar jämfört med den naiva algoritmen kommer att presenteras. Strassens algoritm kommer också att bli bedömd på hur dess resultat skiljer sig för olika precisioner när matriserna blir större, samt hur dess teoretiska komplexitet skiljer sig gentemot den erhållna komplexiteten. Studier hittade att Strassens algoritm överträffade den naiva algoritmen för matriser av storlek 1024×1024 och större. Den erhållna komplexiteten var lite större än Volker Strassens teoretiska. Den optimala precisionen i detta fall var dubbelprecisionen, Float64. Sättet algoritmen implementeras på i koden påverkar dess prestanda. Ett flertal olika faktorer behövs ha i åtanke för att förbättra Strassens algoritm: optimera dess avbrottsvillkor, sättet som matriserna paddas för att de ska vara mer användbara för rekursiv tillämpning och hur de implementeras t.ex. parallella beräkningar. Även om det kunde bevisas att Strassen algoritm överträffade den naiva efter en viss matrisstorlek så är den inte den mest effektiva; t.ex visades detta med Strassen-Winograd. Man behöver vara uppmärksam på hur undermatriserna allokeras, för att inte ta upp onödigt minne. För fördjupning kan man läsa på om cache-oblivious och cache-aware algoritmer. / Strassen’s algorithm was one of the breakthroughs in matrix analysis in 1968. In this report the thesis of Volker Strassen’s algorithm for matrix multipli- cations along with theories about precisions will be shown. The benefits of using this algorithm compared to naive matrix multiplication and its implica- tions, how its performance compare to the naive algorithm, will be displayed. Strassen’s algorithm will also be assessed on how the output differ when the matrix sizes grow larger, as well as how the theoretical complexity of the al- gorithm differs from the achieved complexity. The studies found that Strassen’s algorithm outperformed the naive matrix multiplication at matrix sizes 1024 1024 and above. The achieved complex- ity was a little higher compared to Volker Strassen’s theoretical. The optimal precision for this case were the double precision, Float64. How the algorithm is implemented in code matters for its performance. A number of techniques need to be considered in order to improve Strassen’s algorithm, optimizing its termination criterion, the manner by which it is padded in order to make it more usable for recursive application and the way it is implemented e.g. parallel computing. Even tough it could be proved that Strassen’s algorithm outperformed the Naive after reaching a certain matrix size, it is still not the most efficient one; e.g. as shown with Strassen-Winograd. One need to be careful of how the sub-matrices are being allocated, to not use unnecessary memory. For further reading one can study cache-oblivious and cache-aware algorithms.

Den här studien beskriver hur grafikkort kan användas på en bredare front änmultimedia. Arbetet förklarar och diskuterar huvudsakliga alternativ som finnstill att använda grafikkort till generella operationer i dagsläget. Inom denna studieanvänds Nvidias CUDA arkitektur. Studien beskriver hur grafikkort användstill egna operationer rent praktiskt ur perspektivet att vi redan kan programmerai högnivåspråk och har grundläggande kunskap om hur en dator fungerar. Vianvänder s.k. accelererade bibliotek på grafikkortet (THRUST och CUBLAS) föratt uppnå målet som är utveckling av programvara och prestandatest. Resultatetär program som använder GPU:n till generella och prestandatest av dessa,för lösning av olika problem (matrismultiplikation, sortering, binärsökning ochvektor-inventering) där grafikkortet jämförs med processorn seriellt och parallellt.Resultat visar att grafikkortet exekverar upp till ungefär 50 gånger snabbare(tidsmässigt) kod jämfört med seriella program på processorn. / This study describes how we can use graphics cards for general purpose computingwhich differs from the most usual field where graphics cards are used, multimedia.The study describes and discusses present day alternatives for usinggraphic cards for general operations. In this study we use and describe NvidiaCUDA architecture. The study describes how we can use graphic cards for generaloperations from the point of view that we have programming knowledgein some high-level programming language and knowledge of how a computerworks. We use accelerated libraries (THRUST and CUBLAS) to achieve our goalson the graphics card, which are software development and benchmarking. Theresults are programs countering certain problems (matrix multiplication, sorting,binary search, vector inverting) and the execution time and speedup forthese programs. The graphics card is compared to the processor in serial andthe processor in parallel. Results show a speedup of up to approximatly 50 timescompared to serial implementations on the processor.

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.

The increasing demand for mobile data has placed significant strain on radio access networks (RANs), leading to a continuous need for increased network capacity. In keeping with that, a significant advancement in modern RANs is the ability to utilize several receivers and transmitters, to allow for beamforming. One way to increase the capacity of the network is therefore to optimize the resource allocation by preprocessing the transmitted signals, which involves several costly matrix multiplications (MMs). The aim of the project was to investigate the potential of accelerating Ericsson's RAN simulations by using AI based approximate matrix multiplication (AMM) algorithms. The main focus was on the multiply additionless (MADDNESS) algorithm, a product quantization technique that has achieved speedups of up to 100 times compared to exact MM, and 10 times faster than previous AMM methods. A complex matrix handling version of MADDNESS was implemented in Java and Python respectively, and its speed and accuracy were evaluated against Ericsson's current MM implementation. The proposed implementation did not beat the benchmark with respect to speed, instead resulting in a 4-10 times slowdown in runtime. However, this may largely be due to the fact that the used languages do not allow for complete control over memory resource allocation. As such, the implementations at hand do not incorporate all the crucial features of the algorithm. Particularly, the handicapped version does not fully leverage the vectorization potential, which is one of the key contributors to the speed of the algorithm. Consequently, further improvements are necessary before employing the techniques in an end-to-end implementation. / Den växande efterfrågan på mobildata har ökat belastningen på dagens radionätverk (RAN) och har medfört ett behov av att utvidga dess kapacitet. En betydande innovation inom RAN är beamforming, vilket är förmågan att fokusera digitala signaler mot mottagaren och på så vis öka singalstyrkan. En metod för att öka kapaciteten i ett nätverk är att optimera både kvaliteten av och resursallokeringen mellan nätverkets digitala kanaler, vilket medför tidskrävande matrismultiplikationer. Syftet med denna studie var att utforska om AI-baserade approximativa matrismultiplikationsalgoritmer har potentialen att accelerera Ericssons digitala tvilling-simuleringar. Studien fokuserade i huvudsak på produktkvantiseringsalgoritmen MADDNESS som påvisat potentialen att accelerera exakta matrismultiplikationer med en faktor 100, samt en faktor 10 snabbare än jämförbara approximativa metoder. En modifierad version av MADDNESS, som behandlar komplexa matriser, implementerades i Java samt Python, varefter precisionen och hastigheten utvärderades. Den föreslagna implementationen resulterade i en försämring med avseende på hastigheten med en faktor 4-10 jämfört med Ericssons nuvarande algoritmer. Den föreslagna implementationen saknar effektiv minnesallokering och misslyckas följaktligen att till fullo ta tillvara på vektoriseringspotentialen i MADDNESS. Detta indikerar att det är nödvändigt för ytterligare förbättringar innan algoritmen är användbar i den givna simuleringsmiljön.