1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
%
% teil1.tex -- Beispiel-File für das Paper
%
% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
%
\section{Problemstellung}
\rhead{Problemstellung}
Wegen der breiten Anwendung der Matrizenmultiplikation ist eine effiziente L\"osung dieser Operation von grosser Bedeutung.
Das Ziel dieses Papers ist, verschiedenen Algorithmen der Matrizenmultiplikation vorzustellen.
Gezielt wird auf Algorithmen eingegange, welche das Problem schneller als der Standard Algorithmus l\"osen.
\subsection{Big $\mathcal{O}$ Notation}
\label{muliplikation:sec:bigo}
Die Big $\mathcal{O}$ Notation beschreibt die Laufzeitkomplexit\"at eines Algorithmus in Abhänigkeit zur Inputgrösse \cite{multiplikation:bigo}.
$f(x) \in \mathcal{O}(g(x))$ besagt, dass die Funktion $f$ nicht wesentlich schneller w\"achst als $g$ wenn $x \rightarrow \infty$.
Als Beispiel: benötigt eine Funktion $g$, $\mathcal{O}\left(n+n^2 \right)$ Multiplikationen so wächst $f$ mit $\mathcal{O}\left(n^2 \right)$ nicht wesentlich schneller als $g$.
Vereinfacht werden f\"ur Algorithmen die folgende Notation verwendet:
\begin{itemize}
\item $f \in \mathcal{O}(1) \rightarrow f$ ist beschr\"ankt
\item $f \in \mathcal{O}(n) \rightarrow f$ w\"achst linear
\item $f \in \mathcal{O}\left (n^2 \right ) \rightarrow f$ w\"achst quadratisch
\item $f \in \mathcal{O}(\log n) \rightarrow f$ w\"achst logarithmisch
\item $f \in \mathcal{O}(n \log n) \rightarrow f$ hat super-lineares Wachstum
\item $f \in \mathcal{O}\left (e^n \right ) \rightarrow f$ w\"achst exponentiell
\item usw.
\end{itemize}
In der Abbildung \ref{multiplikation:fig:bigo} k\"onnen die verschiedenen Laufzeiten miteinander verglichen werden.
\begin{figure}
\center
\includegraphics[]{papers/multiplikation/images/bigo}
\caption{Verschiedene Laufzeiten}
\label{multiplikation:fig:bigo}
\end{figure}
\subsubsection{Beispiel Algorithmen}
Es folgen einige Beispiele von Algorithmen welche zu einer bestimmten Zeitkomplexit\"atsklasse zugeteilt werden k\"onnen.
\begin{minipage}{0.4\textwidth}
\begin{algorithm}[H]\footnotesize\caption{}
\label{multiplikation:alg:b1}
\setlength{\lineskip}{7pt}
\begin{algorithmic}
\Function{B1}{$a, b$}
\State \textbf{return} $a+b$
\EndFunction
\end{algorithmic}
\end{algorithm}
\begin{algorithm}[H]\footnotesize\caption{}
\setlength{\lineskip}{7pt}
\begin{algorithmic}
\label{multiplikation:alg:linear}
\Function{L}{$\mathbf{a}, \mathbf{b}$,n}
\State $ sum \gets 0$
\For{$i = 0,1,2 \dots,n$}
\State $ sum \gets sum + A[i] \cdot B[i] $
\EndFor
\State \textbf{return} $sum$
\EndFunction
\end{algorithmic}
\end{algorithm}
\end{minipage}
\hspace{2cm}
\begin{minipage}{0.4\textwidth}
\begin{algorithm}[H]\footnotesize\caption{}
\label{multiplikation:alg:b2}
\setlength{\lineskip}{7pt}
\begin{algorithmic}
\Function{B2}{$a, b$}
\State $ x \gets a+b $
\State $ y \gets a \cdot b $
\State \textbf{return} $x+y$
\EndFunction
\end{algorithmic}
\end{algorithm}
\begin{algorithm}[H]\footnotesize\caption{}
\label{multiplikation:alg:q1}
\setlength{\lineskip}{7pt}
\begin{algorithmic}
\Function{Q}{$\mathbf{A}, \mathbf{B}$,n}
\State $ sum \gets 0$
\For{$i = 0,1,2 \dots,n$}
\For{$j = 0,1,2 \dots,n$}
\State $ sum \gets sum + A[i] \cdot B[j] $
\EndFor
\EndFor
\State \textbf{return} $sum$
\EndFunction
\end{algorithmic}
\end{algorithm}
\end{minipage}
\paragraph{Beschr\"ankter Algorithmus}
Ein Beispiel eines Beschr\"ankter Verhalten $\mathcal{O}(1)$, kann im Algorithmus \ref{multiplikation:alg:b1} entnommen werden. Da $a$ und $b$ Skalare sind, hat keine Gr\"osse $n$ einen einfluss auf die Laufzeit.
Konstanten werden nicht beachtet, der Algorithmus \ref{multiplikation:alg:b2} f\"uhrt ebenso zu $\mathcal{O}(1)$ und nicht zu $\mathcal{O}(2)$.
\paragraph{Linearer Algorithmus}
Der Algorithmus \ref{multiplikation:alg:linear} hat ein lineares Verhalten.
Die \texttt{for}-Schleife wird $n$-mal durchlaufen und f\"uhrt deshalb zu $\mathcal{O}(n)$.
\paragraph{Quadratischer Algorithmus}
Der Algorithmus \ref{multiplikation:alg:q1} hat ein quadratisches Verhalten.
Die beiden \texttt{for}-Schleifen werden jeweils $n$-mal durchglaufen und f\"uhrt deshalb zu $\mathcal{O}\left(n^2\right)$.
|
