Hitro množenje matrik

delo diplomskega seminarja

Matej Marinko (Avtor), Klemen Šivic (Mentor)

Povzetek

Množenje matrik je v linearni algebri preprosta operacija, ki se pogosto pojavlja v rešitvah najrazličnejših problemov. Prav zato je bilo v iskanje hitrih algoritmov za množenje matrik vloženega že veliko dela. V diplomskem delu definiramo problem iskanja zgornje meje eksponenta matričnega množenja in razvijemo teorijo ranga in mejnega ranga bilinearnih preslikav. Predstavimo več algoritmov za hitro množenje matrik, ki slonijo na tej teoriji. Izbrane algoritme tudi implementiramo, jih primerjamo med seboj in ocenimo njihovo uporabnost v praksi.

Ključne besede

množenje matrik;eksponent matričnega množenja;rang tenzorjev;mejni rang;algoritmi;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2020
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FMF - Fakulteta za matematiko in fiziko
Založnik:	[M. Marinko]
UDK:	004:512
COBISS:	58244355
Št. ogledov:	847
Št. prenosov:	163
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Fast matrix multiplication
Sekundarni povzetek:	Matrix multiplication is one of the most basic operations in linear algebra and thus very common in various scientific disciplines. Consequently, the computation complexity of matrix multiplication has been extensively studied. In this work, we define a problem of finding the upper bound for the exponent of matrix multiplication and present the theory of rank and border rank of bilinear maps. We describe multiple fast matrix multiplication algorithms based on this theory. In the end, we implement some selected algorithms, compare them, and discuss their value in practical applications.
Sekundarne ključne besede:	matrix multiplication;exponent of matrix multiplication;tensor rank;border rank;
Vrsta dela (COBISS):	Delo diplomskega seminarja/zaključno seminarsko delo/naloga
Študijski program:	0
Konec prepovedi (OpenAIRE):	1970-01-01
Komentar na gradivo:	Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 1. stopnja
Strani:	51 str.
ID:	12039033