aboutsummaryrefslogtreecommitdiffstats
path: root/buch/papers
diff options
context:
space:
mode:
authorNunigan <michael.schmid2@ost.ch>2021-08-06 17:37:58 +0200
committerNunigan <michael.schmid2@ost.ch>2021-08-06 17:37:58 +0200
commit872595e81de60c85b18408f8de5a49c535518edc (patch)
tree05f76c1e3a183286b938013b3683b47c7c4a77c2 /buch/papers
parentMerge branch 'AndreasFMueller:master' into master (diff)
downloadSeminarMatrizen-872595e81de60c85b18408f8de5a49c535518edc.tar.gz
SeminarMatrizen-872595e81de60c85b18408f8de5a49c535518edc.zip
update multiplikation
Diffstat (limited to '')
-rw-r--r--buch/papers/multiplikation/code/MM.py46
-rw-r--r--buch/papers/multiplikation/code/c_meas_4096.pdfbin17400 -> 17448 bytes
-rw-r--r--buch/papers/multiplikation/code/meas/MM.txt4
-rw-r--r--buch/papers/multiplikation/code/meas/blas.txt2
-rw-r--r--buch/papers/multiplikation/code/meas/strassen.txt2
-rw-r--r--buch/papers/multiplikation/code/meas/winograd.txt2
-rw-r--r--buch/papers/multiplikation/code/meas_1024.pdfbin18813 -> 18813 bytes
-rw-r--r--buch/papers/multiplikation/images/bigo.pdfbin27173 -> 28372 bytes
-rw-r--r--buch/papers/multiplikation/images/bigo.tex24
-rw-r--r--buch/papers/multiplikation/images/meas_c.pdfbin0 -> 23161 bytes
-rw-r--r--buch/papers/multiplikation/images/meas_c.tex143
-rw-r--r--buch/papers/multiplikation/images/meas_python.pdfbin0 -> 21700 bytes
-rw-r--r--buch/papers/multiplikation/images/meas_python.tex137
-rwxr-xr-xbuch/papers/multiplikation/loesungsmethoden.tex44
-rwxr-xr-xbuch/papers/multiplikation/problemstellung.tex33
15 files changed, 363 insertions, 74 deletions
diff --git a/buch/papers/multiplikation/code/MM.py b/buch/papers/multiplikation/code/MM.py
index 47bd6ab..7220ae1 100644
--- a/buch/papers/multiplikation/code/MM.py
+++ b/buch/papers/multiplikation/code/MM.py
@@ -226,28 +226,28 @@ def plot_c_res(ave, num):
MM_t = MM[:,0]
MM_n = MM[:,1]
- MM_t = np.mean(MM_t.reshape(-1,ave),axis=1)
- MM_n = np.mean(MM_n.reshape(-1,ave),axis=1)
+ # MM_t = np.mean(MM_t.reshape(-1,ave),axis=1)
+ # MM_n = np.mean(MM_n.reshape(-1,ave),axis=1)
MM_dc_t = MM_dc[:,0]
MM_dc_n = MM_dc[:,1]
- MM_dc_t = np.mean(MM_dc_t.reshape(-1,ave),axis=1)
- MM_dc_n = np.mean(MM_dc_n.reshape(-1,ave),axis=1)
+ # MM_dc_t = np.mean(MM_dc_t.reshape(-1,ave),axis=1)
+ # MM_dc_n = np.mean(MM_dc_n.reshape(-1,ave),axis=1)
strassen_t = strassen[:,0]
strassen_n = strassen[:,1]
- strassen_t = np.mean(strassen_t.reshape(-1,ave),axis=1)
- strassen_n = np.mean(strassen_n.reshape(-1,ave),axis=1)
+ # strassen_t = np.mean(strassen_t.reshape(-1,ave),axis=1)
+ # strassen_n = np.mean(strassen_n.reshape(-1,ave),axis=1)
winograd_t = winograd[:,0]
winograd_n = winograd[:,1]
- winograd_t = np.mean(winograd_t.reshape(-1,ave),axis=1)
- winograd_n = np.mean(winograd_n.reshape(-1,ave),axis=1)
+ # winograd_t = np.mean(winograd_t.reshape(-1,ave),axis=1)
+ # winograd_n = np.mean(winograd_n.reshape(-1,ave),axis=1)
blas_t = blas[:,0]
blas_n = blas[:,1]
- blas_t = np.mean(blas_t.reshape(-1,ave),axis=1)
- blas_n = np.mean(blas_n.reshape(-1,ave),axis=1)
+ # blas_t = np.mean(blas_t.reshape(-1,ave),axis=1)
+ # blas_n = np.mean(blas_n.reshape(-1,ave),axis=1)
def func(x, a,b):
return b*x**a
@@ -261,14 +261,16 @@ def plot_c_res(ave, num):
plt.rc('axes', labelsize=23)
plt.rc('xtick', labelsize=23)
plt.rc('ytick', labelsize=23)
- plt.plot(MM_n, MM_t, label='3 For Loops', lw=5)
- plt.plot(winograd_n, winograd_t, label='Winograd MM', lw=5)
- plt.plot(blas_n, blas_t, label='Blas', lw=5)
- plt.plot(strassen_n, strassen_t, label='Strassen', lw=5)
- plt.plot(MM_dc_n, MM_dc_t, label='Divide and Conquer', lw=5)
+ plt.loglog(MM_n, MM_t, label='3 For Loops', lw=5)
+ plt.loglog(winograd_n, winograd_t, label='Winograd MM', lw=5)
+ plt.loglog(blas_n, blas_t, label='Blas', lw=5)
+ plt.loglog(strassen_n, strassen_t, label='Strassen', lw=5)
+ plt.loglog(MM_dc_n, MM_dc_t, label='Divide and Conquer', lw=5)
plt.xlabel("n")
+ # plt.yscale('log', base=10)
+ # plt.xscale('log', base=2)
plt.ylabel("time (s)")
- plt.grid(True)
+ plt.grid(True, which="both", ls="-")
plt.tight_layout()
plt.legend(fontsize=19)
plt.savefig('c_meas_' + str(num)+ '.pdf')
@@ -278,15 +280,17 @@ def plot_c_res(ave, num):
# plt.plot(blas_n, func(blas_n, *popt2), 'r-', label='fit MM: a=%5.5f, b=%5.10f' % tuple(popt2))
plt.legend()
-
+ # return [MM_n,winograd_n,blas_n,strassen_n,MM_dc_n]
+ return [MM_t,winograd_t,blas_t,strassen_t,MM_dc_t]
+
# test%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
if __name__ == '__main__':
- # plot_c_res(1, 4096)
+ # A = plot_c_res(1, 4096)
- # arr = plot(1024)
- n = np.logspace(1,12,12,base=2,dtype=(np.int))
+ arr = plot(1024)
+ # n = np.logspace(1,12,12,base=2,dtype=(np.int))
# n = np.arange(1,50,2)
# A = np.random.randint(-10, 6, (5,3))
# B = np.random.randint(-10, 6, (3,5))
@@ -297,7 +301,7 @@ if __name__ == '__main__':
# print(C_test)
# print(np.equal(C, C_test))
- t_np = test_perfomance(n)
+ # t_np = test_perfomance(n)
# C = strassen(A, B)
# C_test = A@B
diff --git a/buch/papers/multiplikation/code/c_meas_4096.pdf b/buch/papers/multiplikation/code/c_meas_4096.pdf
index 304015a..5236afb 100644
--- a/buch/papers/multiplikation/code/c_meas_4096.pdf
+++ b/buch/papers/multiplikation/code/c_meas_4096.pdf
Binary files differ
diff --git a/buch/papers/multiplikation/code/meas/MM.txt b/buch/papers/multiplikation/code/meas/MM.txt
index 13b6312..e296dd7 100644
--- a/buch/papers/multiplikation/code/meas/MM.txt
+++ b/buch/papers/multiplikation/code/meas/MM.txt
@@ -1,5 +1,5 @@
-0.000000,2
-0.000000,4
+0.000001,2
+0.000001,4
0.000001,8
0.000010,16
0.000081,32
diff --git a/buch/papers/multiplikation/code/meas/blas.txt b/buch/papers/multiplikation/code/meas/blas.txt
index c3ec7ec..92a61b9 100644
--- a/buch/papers/multiplikation/code/meas/blas.txt
+++ b/buch/papers/multiplikation/code/meas/blas.txt
@@ -1,5 +1,5 @@
0.000001,2
-0.000000,4
+0.000001,4
0.000001,8
0.000003,16
0.000022,32
diff --git a/buch/papers/multiplikation/code/meas/strassen.txt b/buch/papers/multiplikation/code/meas/strassen.txt
index 69ea472..fdfbf2b 100644
--- a/buch/papers/multiplikation/code/meas/strassen.txt
+++ b/buch/papers/multiplikation/code/meas/strassen.txt
@@ -1,4 +1,4 @@
-0.000000,2
+0.000001,2
0.000003,4
0.000010,8
0.000066,16
diff --git a/buch/papers/multiplikation/code/meas/winograd.txt b/buch/papers/multiplikation/code/meas/winograd.txt
index 6e6208a..d185906 100644
--- a/buch/papers/multiplikation/code/meas/winograd.txt
+++ b/buch/papers/multiplikation/code/meas/winograd.txt
@@ -1,4 +1,4 @@
-0.000000,2
+0.000001,2
0.000001,4
0.000002,8
0.000011,16
diff --git a/buch/papers/multiplikation/code/meas_1024.pdf b/buch/papers/multiplikation/code/meas_1024.pdf
index 3312420..f489a7d 100644
--- a/buch/papers/multiplikation/code/meas_1024.pdf
+++ b/buch/papers/multiplikation/code/meas_1024.pdf
Binary files differ
diff --git a/buch/papers/multiplikation/images/bigo.pdf b/buch/papers/multiplikation/images/bigo.pdf
index c29a891..8a53398 100644
--- a/buch/papers/multiplikation/images/bigo.pdf
+++ b/buch/papers/multiplikation/images/bigo.pdf
Binary files differ
diff --git a/buch/papers/multiplikation/images/bigo.tex b/buch/papers/multiplikation/images/bigo.tex
index a415ccb..9ee3a68 100644
--- a/buch/papers/multiplikation/images/bigo.tex
+++ b/buch/papers/multiplikation/images/bigo.tex
@@ -42,56 +42,56 @@
\begin{axis}[
xmode=log, ymode=log,
- xmin=1e-0, xmax=5e1,
+ xmin=1e-0, xmax=5000,
ymin=10e-1, ymax=1e7,
grid=both,
major grid style={black!50},
- xlabel = $n$ (Data Input),
- ylabel = {$t$ (time)},
- legend pos=north east,
+ xlabel = data input size,
+ ylabel = {time},
+ legend pos=north west,
very thick,
yticklabels=\empty,
xticklabels=\empty,
scale only axis=true,
- width=12cm, height=6cm,
+ width=12cm, height=8cm,
]
\addplot [
- domain= 1:50,
+ domain= 1:5000,
samples=100,
color=red,
]
{1};
\addlegendentry{$\mathcal{O}(1)$}
\addplot [
- domain= 1:50,
+ domain= 1:5000,
samples=100,
color=green,
]
{x};
\addlegendentry{$\mathcal{O}(n)$}
\addplot [
- domain= 1:50,
+ domain= 1:50000,
samples=100,
color=blue,
]
{x^2};
\addlegendentry{$\mathcal{O}\left(n^2\right)$}
\addplot [
- domain= 1:50,
+ domain= 1:500,
samples=100,
color=purple,
]
{x^3};
\addlegendentry{$\mathcal{O}\left(n^3\right)$}
\addplot [
- domain= 1:50,
+ domain= 1:500,
samples=100,
color=black,
]
{exp(x) - 1.7};
\addlegendentry{$\mathcal{O}\left(e^n\right)$}
\addplot [
- domain= 1:50,
+ domain= 1:5000,
samples=100,
color=orange,
]
@@ -99,7 +99,7 @@
\addlegendentry{$\mathcal{O}(\log n)$}
\addplot [
- domain= 1:50,
+ domain= 1:5000,
samples=100,
color=gray,
]
diff --git a/buch/papers/multiplikation/images/meas_c.pdf b/buch/papers/multiplikation/images/meas_c.pdf
new file mode 100644
index 0000000..3a4cfd8
--- /dev/null
+++ b/buch/papers/multiplikation/images/meas_c.pdf
Binary files differ
diff --git a/buch/papers/multiplikation/images/meas_c.tex b/buch/papers/multiplikation/images/meas_c.tex
new file mode 100644
index 0000000..818a7e6
--- /dev/null
+++ b/buch/papers/multiplikation/images/meas_c.tex
@@ -0,0 +1,143 @@
+
+\documentclass[border=10pt,varwidth]{standalone}
+\usepackage[left=25mm,right=25mm,top=25mm,bottom=25mm]{geometry}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+\usepackage{times}
+\usepackage{geometry}
+\usepackage{amsmath}
+\usepackage{amssymb}
+\usepackage{mathrsfs}
+\usepackage{amsfonts}
+\usepackage{amsthm}
+\usepackage{lipsum}
+\usepackage{amscd}
+\usepackage{graphicx}
+\usepackage{fancyhdr}
+\usepackage{textcomp}
+\usepackage{pgfplots}
+\usepackage{txfonts}
+\usepackage[all]{xy}
+\usepackage{paralist}
+\usepackage[colorlinks=true]{hyperref}
+\usepackage{array}
+\usepackage{tikz}
+\usepackage{slashed}
+\usepackage{pdfpages}
+\usepackage{cite}
+\usepackage{url}
+\usepackage{amsmath,amsfonts,amssymb}
+\usepackage{tikz}
+\usepackage{pgfplotstable}
+\usetikzlibrary{arrows,matrix,positioning}
+\usetikzlibrary{overlay-beamer-styles}
+\usetikzlibrary{matrix.skeleton}
+\usetikzlibrary{automata,positioning}
+\usetikzlibrary{decorations.text}
+\usepackage{listings}
+\usepackage{multirow}
+\usepackage{color}
+
+\begin{document}
+
+\begin{tikzpicture}
+\begin{axis}[
+xmode=log, ymode=log,
+xmin=60, xmax=5000,
+ymin=1e-4, ymax=2e3,
+grid=both,
+major grid style={black!50},
+xlabel = data Input ($n$),
+ylabel = {time ($s$)},
+legend pos=north west,
+very thick,
+scale only axis=true,
+width=12cm, height=8cm,
+ log basis x={10}
+]
+\addlegendentry{Winograd}
+\addplot[ color=purple,
+] coordinates {
+% (2, 0.000001)
+% (4, 0.000001)
+% (8, 0.000002)
+% (16, 0.000011)
+% (32, 0.000100)
+(64, 0.000654)
+(128, 0.005229)
+(256, 0.057440)
+(512, 0.517850)
+(1024,4.539413)
+(2048,130.627663)
+(4096,1179.261048)
+};
+\addlegendentry{Strassen}
+\addplot [ color=black,
+]coordinates {
+ % (2,0.000001 )
+ % (4,0.000003 )
+ % (8,0.000010 )
+ % (16,0.000066 )
+ % (32,0.000470 )
+ (64,0.003368 )
+ (128,0.024232 )
+ (256,0.172000 )
+ (512,1.209262 )
+(1024,8.457472 )
+(2048,59.267256)
+(4096,414.648901)
+};
+
+\addlegendentry{MM div and conq}
+\addplot[ color=green,
+] coordinates {
+ % (2,0.000003 )
+ % (4,0.000002 )
+ % (8,0.000010 )
+ % (16,0.000068 )
+ % (32,0.000594 )
+ (64,0.004264 )
+ (128,0.036289 )
+ (256,0.324645 )
+ (512,2.612010 )
+(1024,19.928951 )
+(2048,159.333884 )
+(4096,1147.106865)
+};
+
+\addlegendentry{MM}
+\addplot [ color=red,
+]coordinates {
+ % (2,0.000001 )
+ % (4,0.000001 )
+ % (8,0.000001 )
+ % (16,0.000010 )
+ % (32,0.000081 )
+ (64,0.000654 )
+ (128,0.005556 )
+ (256,0.054253 )
+ (512,0.487317 )
+(1024,4.162845 )
+(2048,125.909034 )
+(4096,1111.312696)
+};
+\addlegendentry{BLAS}
+\addplot[ color=blue,
+] coordinates {
+ % (2,0.000001 )
+ % (4,0.000001 )
+ % (8,0.000001 )
+ % (16,0.000003 )
+ % (32,0.000022 )
+ (64,0.000179 )
+ (128,0.001278 )
+ (256,0.010165 )
+ (512,0.074739 )
+(1024,0.704748 )
+(2048,6.845095 )
+(4096,55.845038)
+};
+\end{axis}
+\end{tikzpicture}
+
+\end{document}
diff --git a/buch/papers/multiplikation/images/meas_python.pdf b/buch/papers/multiplikation/images/meas_python.pdf
new file mode 100644
index 0000000..cea2232
--- /dev/null
+++ b/buch/papers/multiplikation/images/meas_python.pdf
Binary files differ
diff --git a/buch/papers/multiplikation/images/meas_python.tex b/buch/papers/multiplikation/images/meas_python.tex
new file mode 100644
index 0000000..ee4db43
--- /dev/null
+++ b/buch/papers/multiplikation/images/meas_python.tex
@@ -0,0 +1,137 @@
+
+\documentclass[border=10pt,varwidth]{standalone}
+\usepackage[left=25mm,right=25mm,top=25mm,bottom=25mm]{geometry}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+\usepackage{times}
+\usepackage{geometry}
+\usepackage{amsmath}
+\usepackage{amssymb}
+\usepackage{mathrsfs}
+\usepackage{amsfonts}
+\usepackage{amsthm}
+\usepackage{lipsum}
+\usepackage{amscd}
+\usepackage{graphicx}
+\usepackage{fancyhdr}
+\usepackage{textcomp}
+\usepackage{pgfplots}
+\usepackage{txfonts}
+\usepackage[all]{xy}
+\usepackage{paralist}
+\usepackage[colorlinks=true]{hyperref}
+\usepackage{array}
+\usepackage{tikz}
+\usepackage{slashed}
+\usepackage{pdfpages}
+\usepackage{cite}
+\usepackage{url}
+\usepackage{amsmath,amsfonts,amssymb}
+\usepackage{tikz}
+\usepackage{pgfplotstable}
+\usetikzlibrary{arrows,matrix,positioning}
+\usetikzlibrary{overlay-beamer-styles}
+\usetikzlibrary{matrix.skeleton}
+\usetikzlibrary{automata,positioning}
+\usetikzlibrary{decorations.text}
+\usepackage{listings}
+\usepackage{multirow}
+\usepackage{color}
+
+\begin{document}
+
+\begin{tikzpicture}
+\begin{axis}[
+xmode=log, ymode=log,
+xmin=30, xmax=1050,
+ymin=0.01, ymax=900,
+grid=both,
+major grid style={black!50},
+xlabel = data input ($n$),
+ylabel = {time ($s$)},
+legend pos=north west,
+very thick,
+scale only axis=true,
+width=12cm, height=8cm,
+ log basis x={10}
+]
+\addlegendentry{Winograd}
+\addplot[ color=purple,
+] coordinates {
+% (2, 2.7895e-05 )
+% (4, 0.000104904)
+% (8, 0.000552893)
+% (16, 0.0045557 )
+(32, 0.0187144 )
+(64, 0.153069 )
+(128, 1.19476 )
+(256, 8.29899 )
+(512, 68.3699 )
+(1024,537.374 )
+
+};
+\addlegendentry{Strassen}
+\addplot [ color=black,
+]coordinates {
+ % (2,2.09808e-05 )
+ % (4,0.000174284 )
+ % (8,0.000943899 )
+ % (16,0.00475407 )
+ (32,0.0485256 )
+ (64,0.220414 )
+ (128,1.44718 2 )
+ (256,9.93866 0 )
+ (512,63.961 2 )
+(1024,461.494 2 )
+};
+
+\addlegendentry{MM div and conq}
+\addplot[ color=green,
+] coordinates {
+ % (2,8.10623e-06 )
+ % (4,9.01222e-05 )
+ % (8,0.000729084 )
+ % (16,0.00497079 )
+ (32,0.02719 )
+ (64,0.26528 )
+ (128,1.77787 )
+ (256,13.27 )
+ (512,105.397 )
+(1024,847.321 )
+};
+
+\addlegendentry{MM}
+\addplot [ color=red,
+]coordinates {
+ % (2,1.85966e-05)
+ % (4,8.29697e-05 )
+ % (8,0.000547171)
+ % (16,0.00305367 )
+ (32, 0.0240743 )
+ (64, 0.186895 )
+ (128, 1.56369 )
+ (256, 11.0062 )
+ (512, 85.4768)
+(1024,750.757 )
+};
+% \addlegendentry{NumPy}
+% \addplot[ color=blue,
+% ] coordinates {
+% (2,1.83582e-05 )
+% (4,7.86781e-06)
+% (8,1.00136e-05)
+% (16,5.4121e-05 )
+% (32,4.26769e-05)
+% (64,0.000118494)
+% (128,0.000244141 )
+% (256,0.000695705 )
+% (512,0.00221705 )
+% (1024,0.0188088 )
+% };
+\end{axis}
+\end{tikzpicture}
+
+\end{document}
+
+
+
diff --git a/buch/papers/multiplikation/loesungsmethoden.tex b/buch/papers/multiplikation/loesungsmethoden.tex
index 43181d4..a7612e1 100755
--- a/buch/papers/multiplikation/loesungsmethoden.tex
+++ b/buch/papers/multiplikation/loesungsmethoden.tex
@@ -15,7 +15,7 @@ Die Standardmethode kann im Algorithmus \ref{multiplikation:alg:smm} entnommen w
Hierf\"ur wurde die Gleichung \eqref{multiplikation:eq:MM} direkt implementiert.
Die \texttt{for i} Schleife iteriert \"uber alle Zeilen der $\mathbf{A}$ Matrix, die \texttt{for j} Schleife iteriert \"uber alle Spalten der $\mathbf{B}$ Matrix und die \texttt{for k} Schleife iteriert \"uber alle Eintr\"age dieser Zeilen bzw. Spalten.
-\begin{algorithm}\footnotesize\caption{Matrix Multiplication}
+\begin{algorithm}\footnotesize\caption{Matrizenmultiplikation}
\label{multiplikation:alg:smm}
\setlength{\lineskip}{7pt}
\begin{algorithmic}[1]
@@ -50,7 +50,7 @@ Das bekannteste Beispiel ist wohl die \textit{Fast Fourier Transform} wobei die
Die Matrizenmultiplikation kann ebenfalls mit solch einem Ansatz berechnet werden.
Zur vereinfachten Veranschaulichung kann die Situation mit $\mathbf{A}$ und $\mathbf{B}$ der Gr\"osse $2^n \times 2^n$ verwendet werden.
Die Matrizen $\mathbf{A}$ und $\mathbf{B}$ werden in jeweils vier Blockmatrizen der Gr\"osse $2^{n-1} \times 2^{n-1}$ aufgeteilt.
-Das Matrizen produklt
+Das Matrizen Produkt
\begin{equation}
\mathbf{A}\mathbf{B}=
\begin{bmatrix}
@@ -76,7 +76,7 @@ ist identisch zu der Gleichung \eqref{multiplikation:eq:MM}, f\"ur die Multiplik
Der Algorithmus \ref{multiplikation:alg:devide_mm} zeigt den \textit{Divide and Conquer} Ansatz,
Der Grundstruktur dieser Methode besteht aus dem rekursiven Aufruf der Funktion mit den erzeugten Blockmatrizen.
Der rekursive Aufruf wird bis zu der Gr\"osse der Matrizen von $N = 2 \times 2$ durchgef\"uhrt.
-\begin{algorithm}\footnotesize\caption{Divide and Conquer Matrix Multiplication}
+\begin{algorithm}\footnotesize\caption{Divide and Conquer Matrizenmultiplikation}
\setlength{\lineskip}{7pt}
\label{multiplikation:alg:devide_mm}
\begin{algorithmic}
@@ -105,7 +105,7 @@ Der rekursive Aufruf wird bis zu der Gr\"osse der Matrizen von $N = 2 \times 2$
\end{algorithmic}
\end{algorithm}
-Die Laufzeit dieser rekursiven Funktion kann mit dem \textit{Master Theorem} \cite{multiplikation:master_theorem} berechnet werden. Das \textit{Master Theorem} bestimmt die Zeitkomplexit\"at von rekursiven Algortihmen.
+Die Laufzeit dieser rekursiven Funktion kann mit dem \textit{Master Theorem} \cite{multiplikation:master_theorem} berechnet werden. Das \textit{Master Theorem} bestimmt die Zeitkomplexit\"at von rekursiven Algorithmen.
Ohne auf dieses vertieft einzugehen, bestimmt die Anzahl rekursiver Aufrufe $\mathcal{T} $ der Funktion die Laufzeit.
In diesem Fall wird die Funktion pro Durchlauf acht mal rekursiv aufgerufen, dies f\"uhrt
\begin{equation} \label{multiplikation:eq:laufzeitdac}
@@ -141,7 +141,7 @@ aus $\mathbf{A}$ und $\mathbf{B}$, werden f\"ur die Berechnung der Bl\"ocke
\end{split}
\end{equation}
der Matrix $\mathbf{C}$ gebraucht.
-\begin{algorithm}\footnotesize\caption{Strassen Matrix Multiplication}
+\begin{algorithm}\footnotesize\caption{Strassen Matrizenmultiplikation}
\label{multiplikation:alg:strassen}
\setlength{\lineskip}{7pt}
\begin{algorithmic}
@@ -186,7 +186,7 @@ der Matrix $\mathbf{C}$ gebraucht.
\EndFunction
\end{algorithmic}
\end{algorithm}
-Strassen's Methode wird in der Abbildung \ref{multiplikation:fig:strassen} grafisch dargestellt.
+Strassens Methode wird in der Abbildung \ref{multiplikation:fig:strassen} grafisch dargestellt.
Jedes Feld steht f\"ur eine Multiplikation zweier Matrizenelementen von $\mathbf{A}$ oder $\mathbf{B}$ .
Die gr\"unen Felder auf der linken Seite, zeigen die Addition, welche f\"ur den dazugeh\"origen Term ben\"otigt wird.
Die sieben Spalten beschreiben die Matrizen $\mathbf{P,Q,R, \dotsb, V}$.
@@ -194,7 +194,7 @@ Rote Felder stehen f\"ur eine Subtraktion und die gr\"unen f\"ur eine Addition.
\begin{figure}
\center
\includegraphics[width=\linewidth]{papers/multiplikation/images/strassen.pdf}
- \caption{Strassen's Algorithmus}
+ \caption{Strassens Algorithmus}
\label{multiplikation:fig:strassen}
\end{figure}
@@ -207,7 +207,7 @@ Dies f\"uhrt nach dem \textit{Master Theorem} zu einer Laufzeit von
und ist somit schneller als die Standardmethode.
Man beachte, dass die Anzahl von Additionen und Subtraktionen gr\"osser und die Anzahl der Multiplikationen kleiner wurde.
-\subsection{Winograd's Algorithmus}
+\subsection{Winograds Algorithmus}
Einen weiteren Ansatz lieferte Shmuel Winograd im Jahre 1968 \cite{multiplikation:winograd_1968}.
Er beschrieb einen neuen Algorithmus f\"ur das Skalarprodukt
@@ -232,9 +232,10 @@ Das Skalarprodukt ist nun geben mit
\displaystyle \quad \sum_{j=1}^{ \lfloor n/2 \rfloor} (x_{2j-1} + y_{2j})(x_{2j}+y_{2j-1})-\xi - \eta + x_n y_n & \text{wenn $n$ ungerade}.
\end{cases}
\end{equation}
-Das Skalarprodukt kann also mit $ \lfloor \frac{n+1}{2} \rfloor$ weiteren Multiplikationen brechnet werden.
+Das Skalarprodukt kann also mit $ \lfloor \frac{n+1}{2} \rfloor$ weiteren Multiplikationen berechnet werden.
Angenommen man hat $N$ Vektoren mit welchen man $T$ Skalarprodukte berechnen m\"ochte.
Daf\"ur werden $N\lfloor n/2 \rfloor + T\lfloor (n+1)/2 \rfloor $ Multiplikationen ben\"otigt.
+Die Summen f\"ur $\xi$ und $\eta$ m\"ussen nur einmal berechnet werden.
Für die Gleichung \eqref{multiplikation:eq:skalar} benötigt man $Tn$ Multiplikationen.
Im Vergleich mit der neuen Methode
\begin{equation}
@@ -254,15 +255,20 @@ Dies f\"uhrt zu
Multiplikationen.
Wenn $m,p,n$ gross werden, dominiert der Term $\frac{mpn}{2}$ und es werden $\frac{mpn}{2}$ Multiplikationen ben\"otigt.
Was im Vergleich zu den $mpn$ Multiplikation der Standardmethode nur die H\"alfte ist.
-Mit dem glichen Ansatz wie in der Gleichung \ref{multiplikation:eq:eff} aber mit quadratischen Matrizen, muss
+Mit dem gleichen Ansatz wie in der Gleichung \ref{multiplikation:eq:eff} aber mit quadratischen Matrizen, muss
\begin{equation}
- N=2n \ll T=n^2
+ \begin{split}
+N=2n, \quad T = n^2 \\
+ 2n \leq n^2 \\
+ 2 \leq n
+\end{split}
\end{equation}
-damit man etwas einspart.
+sein, damit man etwas einspart.
Die Implementation kann Algorithmus \ref{multiplikation:alg:winograd} entnommen werden.
-Falls $m=n=p$ werden $\frac{n^3}/{2}$ Multiplikationen benötigt. Im Abschnitt \ref{muliplikation:sec:bigo} wurde bereits erläutert: falls $n \rightarrow \infty$ können Konstanten vernachlässigt werden und
+Falls $m=n=p$ werden $\frac{n^3}/{2}$ Multiplikationen benötigt.
+Im Abschnitt \ref{muliplikation:sec:bigo} wurde bereits erläutert: falls $n \rightarrow \infty$ können Konstanten vernachlässigt werden und
somit entsteht für diesen Algorithmus wieder die Ursprüngliche Laufzeit von $\mathcal{O}\left(n^3 \right)$.
-\begin{algorithm}\footnotesize\caption{Winograd Matrix Multiplication}
+\begin{algorithm}\footnotesize\caption{Winograds Matrizenmultiplikation}
\setlength{\lineskip}{7pt}
\label{multiplikation:alg:winograd}
\begin{algorithmic}
@@ -374,8 +380,8 @@ Folgende Algorithmen wurden jeweils in \texttt{C} und \texttt{Python} implementi
\begin{itemize}
\item Standard Matrizenmultiplikation
\item \textit{Devide and Conquer} Matrizenmultiplikation
- \item Strassen's Matrizenmultiplikation
- \item Winograd's Matrizenmultiplikation
+ \item Strassens Matrizenmultiplikation
+ \item Winograds Matrizenmultiplikation
\item \texttt{BLAS} Matrizenmultiplikation in \texttt{C}
\item \texttt{Numpy} Matrizenmultiplikation in \texttt{Python}
\end{itemize}
@@ -458,7 +464,7 @@ Die Hardwareinformationen des verwendeten Computers sind in der Tabelle \ref{mul
\begin{figure}
\center
- \includegraphics[width=\linewidth]{papers/multiplikation/images/c_meas_4096}
+ \includegraphics[width=\linewidth]{papers/multiplikation/images/meas_c}
\caption{Messresultate mit der Programmiersprache \texttt{C}}
\label{multiplikation:fig:c_meas_4096}
\end{figure}
@@ -466,7 +472,7 @@ Die Hardwareinformationen des verwendeten Computers sind in der Tabelle \ref{mul
\begin{figure}
\center
- \includegraphics[width=\linewidth]{papers/multiplikation/images/meas_1024}
+ \includegraphics[width=\linewidth]{papers/multiplikation/images/meas_python}
\caption{Messresultate mit der Programmiersprache \texttt{Python}}
\label{multiplikation:fig:python}
\end{figure}
@@ -474,7 +480,7 @@ Die Hardwareinformationen des verwendeten Computers sind in der Tabelle \ref{mul
\section{Fazit}
\rhead{Fazit}
-Wie man im Abschnit \ref{multiplikation:section:Implementation} sehen kann, sind die gezeigten Algorithmen trotz den theoretisch geringeren Zeitkomplexitäten, den Implementationen der numerischen Bibliotheken klar unterlegen.
+Wie man im Abschnitt \ref{multiplikation:section:Implementation} sehen kann, sind die gezeigten Algorithmen trotz den theoretisch geringeren Zeitkomplexitäten, den Implementationen der numerischen Bibliotheken klar unterlegen.
Ein optimierter Speicherzugriff hat einen weitaus grösseren Einfluss auf die Laufzeit als die Zeitkomplexität des Algorithmus.
Doch haben Entdeckungen wie jene von Strassen und Winograd ihre Daseinsberechtigung.
diff --git a/buch/papers/multiplikation/problemstellung.tex b/buch/papers/multiplikation/problemstellung.tex
index c6fd10e..e53b0de 100755
--- a/buch/papers/multiplikation/problemstellung.tex
+++ b/buch/papers/multiplikation/problemstellung.tex
@@ -7,13 +7,14 @@
\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.
+Gezielt wird auf Algorithmen eingegangen, 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}.
+Die Big $\mathcal{O}$ Notation beschreibt die Laufzeitkomplexit\"at eines Algorithmus in Abhängigkeit 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$.
+% Es gibt eine Konstante $K$ derart, dass $f(x) \le K g(x)$ für $x\to\infty$
+Als Beispiel: benötigt eine Funktion $g$ $\mathcal{O}\left(n^2 \right)$ Multiplikationen, so wächst $f$ mit $\mathcal{O}\left(n+ n^2 \right)$ nicht wesentlich schneller falls $x\to\infty$.
Vereinfacht werden f\"ur Algorithmen die folgende Notation verwendet:
\begin{itemize}
\item $f \in \mathcal{O}(1) \rightarrow f$ ist beschr\"ankt
@@ -26,13 +27,9 @@ Vereinfacht werden f\"ur Algorithmen die folgende Notation verwendet:
\end{itemize}
In der Abbildung \ref{multiplikation:fig:bigo} k\"onnen die verschiedenen Laufzeiten miteinander verglichen werden.
+Bei einer logarithmischen Darstellung werden Polynome der Form $f(x) = x^k$ als Gerade und Exponentialfunktionen der Form $f(x) = a^x$ als nach oben gekr\"ummte Kurven dargestellt.
+Sch\"on zu erkennen ist, dass Logarithmische Kurven beschr\"ankt sind.
-\begin{figure}
- \center
- \includegraphics[]{papers/multiplikation/images/bigo}
- \caption{Verschiedene Laufzeiten}
- \label{multiplikation:fig:bigo}
-\end{figure}
\subsubsection{Beispiel Algorithmen}
@@ -101,23 +98,25 @@ Es folgen einige Beispiele von Algorithmen welche zu einer bestimmten Zeitkomple
\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.
-
-
+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)$.
+Die beiden \texttt{for}-Schleifen werden jeweils $n$-mal durchlaufen und f\"uhrt deshalb zu $\mathcal{O}\left(n^2\right)$.
+
+
+\begin{figure}
+ \center
+ \includegraphics[]{papers/multiplikation/images/bigo}
+ \caption{Verschiedene Laufzeiten}
+ \label{multiplikation:fig:bigo}
+\end{figure}