aboutsummaryrefslogtreecommitdiffstats
path: root/buch/papers/multiplikation
diff options
context:
space:
mode:
authorJODBaer <JODBaer@github.com>2021-08-07 14:34:58 +0200
committerJODBaer <JODBaer@github.com>2021-08-07 14:34:58 +0200
commit2257ffca3c2ff48af74e5bbfb85b505feef6c1ab (patch)
tree7e3f85bc6e98a9a9a5d48642d7dd08cd35f4f2af /buch/papers/multiplikation
parentMerge pull request #64 from Kuehnee/master (diff)
parentplot-green (diff)
downloadSeminarMatrizen-2257ffca3c2ff48af74e5bbfb85b505feef6c1ab.tar.gz
SeminarMatrizen-2257ffca3c2ff48af74e5bbfb85b505feef6c1ab.zip
Merge remote-tracking branch 'origin/Baer'
Diffstat (limited to '')
-rwxr-xr-xbuch/papers/multiplikation/code/MMbin26848 -> 26848 bytes
-rwxr-xr-xbuch/papers/multiplikation/code/MM.c2
-rw-r--r--buch/papers/multiplikation/code/MM.py109
-rw-r--r--buch/papers/multiplikation/code/c_matrix.h114
-rw-r--r--buch/papers/multiplikation/code/c_meas_4096.pdfbin15865 -> 17448 bytes
-rw-r--r--buch/papers/multiplikation/code/meas/MM.txt24
-rw-r--r--buch/papers/multiplikation/code/meas/MM_dc.txt24
-rw-r--r--buch/papers/multiplikation/code/meas/blas.txt18
-rw-r--r--buch/papers/multiplikation/code/meas/strassen.txt20
-rw-r--r--buch/papers/multiplikation/code/meas/winograd.txt17
-rw-r--r--buch/papers/multiplikation/code/meas_1024.pdfbin17660 -> 18813 bytes
-rw-r--r--buch/papers/multiplikation/code/meas_1024.txt10
-rw-r--r--buch/papers/multiplikation/code/meas_128.pdfbin17961 -> 18120 bytes
-rw-r--r--buch/papers/multiplikation/code/meas_128.txt10
-rw-r--r--buch/papers/multiplikation/code/meas_256.pdfbin18067 -> 17715 bytes
-rw-r--r--buch/papers/multiplikation/code/meas_256.txt10
-rw-r--r--buch/papers/multiplikation/code/meas_32.pdfbin17078 -> 17964 bytes
-rw-r--r--buch/papers/multiplikation/code/meas_32.txt10
-rw-r--r--buch/papers/multiplikation/code/meas_4096.pdfbin0 -> 12952 bytes
-rw-r--r--buch/papers/multiplikation/code/meas_4096.txt0
-rw-r--r--buch/papers/multiplikation/code/meas_64.pdfbin17678 -> 17747 bytes
-rw-r--r--buch/papers/multiplikation/code/meas_64.txt10
-rwxr-xr-xbuch/papers/multiplikation/einlteung.tex22
-rw-r--r--buch/papers/multiplikation/images/bigo.pdfbin24288 -> 28372 bytes
-rw-r--r--buch/papers/multiplikation/images/bigo.tex42
-rw-r--r--buch/papers/multiplikation/images/c_meas_4096.pdfbin0 -> 17400 bytes
-rw-r--r--buch/papers/multiplikation/images/meas_1024.pdfbin0 -> 18813 bytes
-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
-rw-r--r--buch/papers/multiplikation/images/strassen.pdfbin15850 -> 19970 bytes
-rw-r--r--buch/papers/multiplikation/images/strassen.tex14
-rwxr-xr-xbuch/papers/multiplikation/loesungsmethoden.tex306
-rwxr-xr-xbuch/papers/multiplikation/main.tex22
-rwxr-xr-xbuch/papers/multiplikation/problemstellung.tex164
-rwxr-xr-xbuch/papers/multiplikation/references.bib37
37 files changed, 909 insertions, 356 deletions
diff --git a/buch/papers/multiplikation/code/MM b/buch/papers/multiplikation/code/MM
index f07985f..d52dda4 100755
--- a/buch/papers/multiplikation/code/MM
+++ b/buch/papers/multiplikation/code/MM
Binary files differ
diff --git a/buch/papers/multiplikation/code/MM.c b/buch/papers/multiplikation/code/MM.c
index 04c4dab..a897d4f 100755
--- a/buch/papers/multiplikation/code/MM.c
+++ b/buch/papers/multiplikation/code/MM.c
@@ -31,7 +31,7 @@ int main() {
run_algo(strassen, "strassen",0);
run_algo(MM, "MM", 0);
- // run_algo(winograd, "winograd", 0);
+ run_algo(winograd, "winograd", 0);
run_algo_cblas(0);
return 0;
diff --git a/buch/papers/multiplikation/code/MM.py b/buch/papers/multiplikation/code/MM.py
index 626b82d..7220ae1 100644
--- a/buch/papers/multiplikation/code/MM.py
+++ b/buch/papers/multiplikation/code/MM.py
@@ -132,6 +132,10 @@ def winograd2(A, B):
return C
def test_perfomance(n):
+
+ import mkl
+ mkl.set_num_threads(1)
+
t_mm = []
t_mm_dc = []
t_mm_strassen = []
@@ -144,21 +148,21 @@ def test_perfomance(n):
# A = np.random.randint(-100, 100,(i, i))
# B = np.random.randint(-100, 100,(i, i))
- start = time.time()
- C3 = strassen(A, B)
- t_mm_strassen.append(time.time() - start)
+ # start = time.time()
+ # C3 = strassen(A, B)
+ # t_mm_strassen.append(time.time() - start)
- start = time.time()
- C1 = MM(A, B)
- t_mm.append(time.time() - start)
+ # start = time.time()
+ # C1 = MM(A, B)
+ # t_mm.append(time.time() - start)
- start = time.time()
- C2 = MM_dc(A, B)
- t_mm_dc.append(time.time() - start)
+ # start = time.time()
+ # C2 = MM_dc(A, B)
+ # t_mm_dc.append(time.time() - start)
- start = time.time()
- C4 = winograd2(A, B)
- t_wino.append(time.time() - start)
+ # start = time.time()
+ # C4 = winograd2(A, B)
+ # t_wino.append(time.time() - start)
start = time.time()
C = A@B
@@ -169,22 +173,23 @@ def test_perfomance(n):
plt.rc('axes', labelsize=23)
plt.rc('xtick', labelsize=23)
plt.rc('ytick', labelsize=23)
- plt.plot(n, t_mm, label='Standard', lw=5)
- plt.plot(n, t_mm_dc, label='Divide and conquer', lw=5)
- plt.plot(n, t_mm_strassen, label='Strassen', lw=5)
- plt.plot(n, t_wino, label='Winograd', lw=5)
+ # plt.plot(n, t_mm, label='Standard', lw=5)
+ # plt.plot(n, t_mm_dc, label='Divide and conquer', lw=5)
+ # plt.plot(n, t_mm_strassen, label='Strassen', lw=5)
+ # plt.plot(n, t_wino, label='Winograd', lw=5)
plt.plot(n, t_np, label='NumPy A@B', lw=5)
+ # plt.xscale('log', base=2)
plt.legend()
plt.xlabel("n")
plt.ylabel("time (s)")
- plt.grid(True)
+ plt.grid(True, which="both", ls="-")
plt.tight_layout()
# plt.yscale('log')
plt.legend(fontsize=19)
- plt.savefig('meas_' + str(max(n))+ '.pdf')
- arr = np.array([n, t_mm, t_mm_dc, t_mm_strassen, t_wino, t_np])
- np.savetxt('meas_' + str(max(n))+ '.txt',arr)
- return arr
+ # plt.savefig('meas_' + str(max(n))+ '.pdf')
+ # arr = np.array([n, t_mm, t_mm_dc, t_mm_strassen, t_wino, t_np])
+ # np.savetxt('meas_' + str(max(n))+ '.txt',arr)
+ return t_np
def plot(num):
@@ -198,10 +203,11 @@ def plot(num):
plt.plot(n, t_mm, label='3 For Loops', lw=5)
plt.plot(n, t_mm_dc, label='Divide and Conquer', lw=5)
plt.plot(n, t_mm_strassen, label='Strassen', lw=5)
- # plt.plot(n, t_wino, label='Winograd', lw=5)
+ plt.plot(n, t_wino, label='Winograd', lw=5)
plt.plot(n, t_np, label='NumPy A@B', lw=5)
plt.legend()
plt.xlabel("n")
+ # plt.yscale('log', base=10)
plt.ylabel("time (s)")
plt.grid(True)
plt.tight_layout()
@@ -211,36 +217,37 @@ def plot(num):
return arr
def plot_c_res(ave, num):
+
MM = np.loadtxt("meas/MM.txt", delimiter=',')
- # winograd = np.loadtxt("meas/winograd.txt", delimiter=',')
+ winograd = np.loadtxt("meas/winograd.txt", delimiter=',')
blas = np.loadtxt("meas/blas.txt", delimiter=',')
MM_dc = np.loadtxt("meas/MM_dc.txt", delimiter=',')
strassen = np.loadtxt("meas/strassen.txt", delimiter=',')
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 = 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)
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
@@ -254,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')
@@ -271,23 +280,25 @@ 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)
- # plot(8)
- # n = np.logspace(1,10,10,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, 10, (5,3))
- B = np.random.randint(-10, 10, (3,5))
+ # A = np.random.randint(-10, 6, (5,3))
+ # B = np.random.randint(-10, 6, (3,5))
- C = winograd2(A, B)
- C_test = A@B
- print(C)
- print(C_test)
+ # C = winograd2(A, B)
+ # C_test = A@B
+ # print(C)
+ # print(C_test)
# print(np.equal(C, C_test))
# t_np = test_perfomance(n)
diff --git a/buch/papers/multiplikation/code/c_matrix.h b/buch/papers/multiplikation/code/c_matrix.h
index 13df55d..14389fc 100644
--- a/buch/papers/multiplikation/code/c_matrix.h
+++ b/buch/papers/multiplikation/code/c_matrix.h
@@ -1,97 +1,97 @@
-/* Seminar Matrizen, autogenerated File, Michael Schmid, 30/05/2021, 22:00:57 */
+/* Seminar Matrizen, autogenerated File, Michael Schmid, 02/08/2021, 22:48:43 */
#include <stdint.h>
const int A0[][2] =
{
- {-15,68},
- {49,86}
+ {75,47},
+ {-41,-24}
};
const int B0[][2] =
{
- {33,73},
- {38,-76}
+ {-53,-95},
+ {-93,30}
};
const double dB0[][2] =
{
- {33,73},
- {38,-76}
+ {-53,-95},
+ {-93,30}
};
const double dA0[][2] =
{
- {-15,68},
- {49,86}
+ {75,47},
+ {-41,-24}
};
const int A1[][4] =
{
- {75,-38,-32,-65},
- {37,74,-31,29},
- {15,-62,-20,-20},
- {-31,-35,-89,47}
+ {47,11,-66,8},
+ {36,98,39,82},
+ {-32,12,40,-79},
+ {61,-20,-85,-98}
};
const int B1[][4] =
{
- {71,90,78,-98},
- {4,63,12,-47},
- {11,-44,75,-69},
- {95,-15,64,23}
+ {37,75,-53,9},
+ {37,-33,-67,38},
+ {70,39,-93,43},
+ {43,41,23,-4}
};
const double dB1[][4] =
{
- {71,90,78,-98},
- {4,63,12,-47},
- {11,-44,75,-69},
- {95,-15,64,23}
+ {37,75,-53,9},
+ {37,-33,-67,38},
+ {70,39,-93,43},
+ {43,41,23,-4}
};
const double dA1[][4] =
{
- {75,-38,-32,-65},
- {37,74,-31,29},
- {15,-62,-20,-20},
- {-31,-35,-89,47}
+ {47,11,-66,8},
+ {36,98,39,82},
+ {-32,12,40,-79},
+ {61,-20,-85,-98}
};
const int A2[][8] =
{
- {80,42,3,-16,6,55,87,16},
- {-99,-14,21,-1,-94,-56,91,10},
- {-47,-55,-59,62,12,-53,87,-65},
- {-60,94,-67,23,-62,33,-63,-72},
- {12,-75,16,21,22,-37,1,16},
- {-100,-99,82,-66,2,64,-13,44},
- {59,-100,-90,8,36,-24,18,88},
- {73,-58,75,-100,-19,-29,85,-19}
+ {-54,-87,87,69,52,-21,-86,55},
+ {19,-75,-61,-50,-55,-23,66,-92},
+ {-73,-67,-36,19,84,-11,24,46},
+ {-98,62,-76,57,-100,6,-23,-51},
+ {62,46,1,-64,42,-9,85,-12},
+ {35,-59,-17,-47,78,86,-50,74},
+ {-15,45,33,-59,-9,-81,49,96},
+ {-57,22,-43,7,-30,-45,-5,13}
};
const int B2[][8] =
{
- {-61,88,69,49,-53,47,73,45},
- {16,14,-88,-11,-67,-73,-20,43},
- {-60,-63,26,32,-29,18,-44,-69},
- {1,21,21,38,7,-100,-61,-76},
- {-90,95,-99,88,49,-80,27,-36},
- {24,-12,-47,-7,29,15,52,37},
- {-98,-76,29,76,-41,-75,97,79},
- {62,-90,-35,-14,-30,-42,-95,52}
+ {-71,-82,-80,-78,83,-97,48,-24},
+ {15,75,15,-60,-63,-53,1,-50},
+ {-84,63,67,-2,78,93,-13,95},
+ {61,-26,-88,56,56,27,26,1},
+ {2,54,21,36,9,-41,53,53},
+ {85,-11,42,-51,-6,3,27,97},
+ {10,-2,90,-76,-75,0,8,-37},
+ {10,-64,47,-69,66,-50,89,-66}
};
const double dB2[][8] =
{
- {-61,88,69,49,-53,47,73,45},
- {16,14,-88,-11,-67,-73,-20,43},
- {-60,-63,26,32,-29,18,-44,-69},
- {1,21,21,38,7,-100,-61,-76},
- {-90,95,-99,88,49,-80,27,-36},
- {24,-12,-47,-7,29,15,52,37},
- {-98,-76,29,76,-41,-75,97,79},
- {62,-90,-35,-14,-30,-42,-95,52}
+ {-71,-82,-80,-78,83,-97,48,-24},
+ {15,75,15,-60,-63,-53,1,-50},
+ {-84,63,67,-2,78,93,-13,95},
+ {61,-26,-88,56,56,27,26,1},
+ {2,54,21,36,9,-41,53,53},
+ {85,-11,42,-51,-6,3,27,97},
+ {10,-2,90,-76,-75,0,8,-37},
+ {10,-64,47,-69,66,-50,89,-66}
};
const double dA2[][8] =
{
- {80,42,3,-16,6,55,87,16},
- {-99,-14,21,-1,-94,-56,91,10},
- {-47,-55,-59,62,12,-53,87,-65},
- {-60,94,-67,23,-62,33,-63,-72},
- {12,-75,16,21,22,-37,1,16},
- {-100,-99,82,-66,2,64,-13,44},
- {59,-100,-90,8,36,-24,18,88},
- {73,-58,75,-100,-19,-29,85,-19}
+ {-54,-87,87,69,52,-21,-86,55},
+ {19,-75,-61,-50,-55,-23,66,-92},
+ {-73,-67,-36,19,84,-11,24,46},
+ {-98,62,-76,57,-100,6,-23,-51},
+ {62,46,1,-64,42,-9,85,-12},
+ {35,-59,-17,-47,78,86,-50,74},
+ {-15,45,33,-59,-9,-81,49,96},
+ {-57,22,-43,7,-30,-45,-5,13}
};
const int *Ap[3] = {(int*) A0,(int*) A1,(int*) A2};
const int *Bp[3] = {(int*) B0,(int*) B1,(int*) B2};
diff --git a/buch/papers/multiplikation/code/c_meas_4096.pdf b/buch/papers/multiplikation/code/c_meas_4096.pdf
index 547d794..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 1a0cd5d..e296dd7 100644
--- a/buch/papers/multiplikation/code/meas/MM.txt
+++ b/buch/papers/multiplikation/code/meas/MM.txt
@@ -1,12 +1,12 @@
-0.000000,2
-0.000000,4
-0.000002,8
-0.000011,16
-0.000080,32
-0.000653,64
-0.005397,128
-0.045147,256
-0.487710,512
-3.964180,1024
-128.863544,2048
-996.370209,4096
+0.000001,2
+0.000001,4
+0.000001,8
+0.000010,16
+0.000081,32
+0.000654,64
+0.005556,128
+0.054253,256
+0.487317,512
+4.162845,1024
+125.909034,2048
+1111.312696,4096
diff --git a/buch/papers/multiplikation/code/meas/MM_dc.txt b/buch/papers/multiplikation/code/meas/MM_dc.txt
index 0d5580a..f6be928 100644
--- a/buch/papers/multiplikation/code/meas/MM_dc.txt
+++ b/buch/papers/multiplikation/code/meas/MM_dc.txt
@@ -1,12 +1,12 @@
-0.000006,2
-0.000007,4
-0.000035,8
-0.000228,16
-0.001310,32
-0.007204,64
-0.034338,128
-0.267511,256
-2.131212,512
-17.177403,1024
-146.112874,2048
-1156.777565,4096
+0.000003,2
+0.000002,4
+0.000010,8
+0.000068,16
+0.000594,32
+0.004264,64
+0.036289,128
+0.324645,256
+2.612010,512
+19.928951,1024
+159.333884,2048
+1147.106865,4096
diff --git a/buch/papers/multiplikation/code/meas/blas.txt b/buch/papers/multiplikation/code/meas/blas.txt
index 6b7cd0b..92a61b9 100644
--- a/buch/papers/multiplikation/code/meas/blas.txt
+++ b/buch/papers/multiplikation/code/meas/blas.txt
@@ -1,12 +1,12 @@
0.000001,2
-0.000000,4
+0.000001,4
0.000001,8
0.000003,16
-0.000021,32
-0.000164,64
-0.001240,128
-0.009657,256
-0.072523,512
-0.735149,1024
-6.895747,2048
-56.812183,4096
+0.000022,32
+0.000179,64
+0.001278,128
+0.010165,256
+0.074739,512
+0.704748,1024
+6.845095,2048
+55.845038,4096
diff --git a/buch/papers/multiplikation/code/meas/strassen.txt b/buch/papers/multiplikation/code/meas/strassen.txt
index 89cf41a..fdfbf2b 100644
--- a/buch/papers/multiplikation/code/meas/strassen.txt
+++ b/buch/papers/multiplikation/code/meas/strassen.txt
@@ -1,12 +1,12 @@
-0.000000,2
+0.000001,2
0.000003,4
0.000010,8
-0.000086,16
-0.000476,32
-0.003366,64
-0.025547,128
-0.184593,256
-1.248713,512
-9.007700,1024
-61.079879,2048
-424.493037,4096
+0.000066,16
+0.000470,32
+0.003368,64
+0.024232,128
+0.172000,256
+1.209262,512
+8.457472,1024
+59.267256,2048
+414.648901,4096
diff --git a/buch/papers/multiplikation/code/meas/winograd.txt b/buch/papers/multiplikation/code/meas/winograd.txt
index 3a4d88b..d185906 100644
--- a/buch/papers/multiplikation/code/meas/winograd.txt
+++ b/buch/papers/multiplikation/code/meas/winograd.txt
@@ -1,11 +1,12 @@
-0.000000,2
+0.000001,2
0.000001,4
0.000002,8
0.000011,16
-0.000091,32
-0.000663,64
-0.005182,128
-0.046038,256
-0.533429,512
-4.257458,1024
-130.378038,2048
+0.000100,32
+0.000654,64
+0.005229,128
+0.057440,256
+0.517850,512
+4.539413,1024
+130.627663,2048
+1179.261048,4096
diff --git a/buch/papers/multiplikation/code/meas_1024.pdf b/buch/papers/multiplikation/code/meas_1024.pdf
index fd0a108..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/code/meas_1024.txt b/buch/papers/multiplikation/code/meas_1024.txt
index c5ce619..ab507a2 100644
--- a/buch/papers/multiplikation/code/meas_1024.txt
+++ b/buch/papers/multiplikation/code/meas_1024.txt
@@ -1,6 +1,6 @@
2.000000000000000000e+00 4.000000000000000000e+00 8.000000000000000000e+00 1.600000000000000000e+01 3.200000000000000000e+01 6.400000000000000000e+01 1.280000000000000000e+02 2.560000000000000000e+02 5.120000000000000000e+02 1.024000000000000000e+03
-1.502037048339843750e-05 6.628036499023437500e-05 4.780292510986328125e-04 2.713203430175781250e-03 2.115225791931152344e-02 1.758832931518554688e-01 1.338865518569946289e+00 1.009106445312500000e+01 8.192077994346618652e+01 7.835870332717895508e+02
-6.675720214843750000e-06 7.200241088867187500e-05 5.540847778320312500e-04 3.144979476928710938e-03 2.545046806335449219e-02 2.083067893981933594e-01 1.659256219863891602e+00 1.319160294532775879e+01 1.046767003536224365e+02 9.679818902015686035e+02
-1.668930053710937500e-05 1.628398895263671875e-04 7.648468017578125000e-04 4.426956176757812500e-03 2.922415733337402344e-02 1.800994873046875000e-01 1.286747694015502930e+00 9.412034273147583008e+00 6.263725924491882324e+01 4.427414393424987793e+02
-2.408027648925781250e-05 8.463859558105468750e-05 4.761219024658203125e-04 2.339839935302734375e-03 1.682758331298828125e-02 1.299476623535156250e-01 1.048770904541015625e+00 8.114667415618896484e+00 6.373566389083862305e+01 6.489995403289794922e+02
-1.573562622070312500e-05 7.152557373046875000e-06 7.152557373046875000e-06 2.074241638183593750e-05 5.388259887695312500e-05 6.365776062011718750e-05 3.257751464843750000e-03 1.396179199218750000e-03 3.274917602539062500e-03 2.186250686645507812e-02
+1.859664916992187500e-05 8.296966552734375000e-05 5.471706390380859375e-04 3.053665161132812500e-03 2.407431602478027344e-02 1.868948936462402344e-01 1.563691616058349609e+00 1.100623321533203125e+01 8.547679090499877930e+01 7.507572824954986572e+02
+8.106231689453125000e-06 9.012222290039062500e-05 7.290840148925781250e-04 4.970788955688476562e-03 2.718997001647949219e-02 2.652802467346191406e-01 1.777865171432495117e+00 1.327002429962158203e+01 1.053971357345581055e+02 8.473208103179931641e+02
+2.098083496093750000e-05 1.742839813232421875e-04 9.438991546630859375e-04 4.754066467285156250e-03 4.852557182312011719e-02 2.204136848449707031e-01 1.447179555892944336e+00 9.938656568527221680e+00 6.396102952957153320e+01 4.614939928054809570e+02
+2.789497375488281250e-05 1.049041748046875000e-04 5.528926849365234375e-04 4.555702209472656250e-03 1.871442794799804688e-02 1.530685424804687500e-01 1.194762229919433594e+00 8.298985958099365234e+00 6.836994743347167969e+01 5.373736469745635986e+02
+1.835823059082031250e-05 7.867813110351562500e-06 1.001358032226562500e-05 5.412101745605468750e-05 4.267692565917968750e-05 1.184940338134765625e-04 2.441406250000000000e-04 6.957054138183593750e-04 2.217054367065429688e-03 1.880884170532226562e-02
diff --git a/buch/papers/multiplikation/code/meas_128.pdf b/buch/papers/multiplikation/code/meas_128.pdf
index ed1ec63..c54648f 100644
--- a/buch/papers/multiplikation/code/meas_128.pdf
+++ b/buch/papers/multiplikation/code/meas_128.pdf
Binary files differ
diff --git a/buch/papers/multiplikation/code/meas_128.txt b/buch/papers/multiplikation/code/meas_128.txt
index 976bbdf..f3a5beb 100644
--- a/buch/papers/multiplikation/code/meas_128.txt
+++ b/buch/papers/multiplikation/code/meas_128.txt
@@ -1,6 +1,6 @@
2.000000000000000000e+00 4.000000000000000000e+00 8.000000000000000000e+00 1.600000000000000000e+01 3.200000000000000000e+01 6.400000000000000000e+01 1.280000000000000000e+02
-1.978874206542968750e-05 1.134872436523437500e-04 4.298686981201171875e-04 2.815246582031250000e-03 2.616596221923828125e-02 1.767718791961669922e-01 1.293319463729858398e+00
-6.675720214843750000e-06 1.251697540283203125e-04 4.818439483642578125e-04 3.490447998046875000e-03 2.465796470642089844e-02 2.014584541320800781e-01 1.630620479583740234e+00
-2.408027648925781250e-05 2.126693725585937500e-04 1.172780990600585938e-03 4.364490509033203125e-03 3.148293495178222656e-02 2.010228633880615234e-01 1.429297924041748047e+00
-2.932548522949218750e-05 1.466274261474609375e-04 4.270076751708984375e-04 2.837419509887695312e-03 1.723575592041015625e-02 1.308519840240478516e-01 1.015527009963989258e+00
-3.337860107421875000e-05 1.096725463867187500e-05 9.536743164062500000e-06 3.600120544433593750e-05 2.837181091308593750e-05 5.912780761718750000e-05 1.981019973754882812e-03
+1.239776611328125000e-05 5.507469177246093750e-05 3.888607025146484375e-04 2.762079238891601562e-03 2.097773551940917969e-02 1.672370433807373047e-01 1.410297393798828125e+00
+5.483627319335937500e-06 5.888938903808593750e-05 3.871917724609375000e-04 3.364324569702148438e-03 2.481031417846679688e-02 2.047052383422851562e-01 1.712310314178466797e+00
+1.358985900878906250e-05 1.189708709716796875e-04 6.430149078369140625e-04 5.586385726928710938e-03 3.101944923400878906e-02 1.874091625213623047e-01 1.327976465225219727e+00
+1.978874206542968750e-05 7.224082946777343750e-05 4.618167877197265625e-04 3.294944763183593750e-03 1.755571365356445312e-02 1.360688209533691406e-01 1.028253555297851562e+00
+1.215934753417968750e-05 5.722045898437500000e-06 2.074241638183593750e-05 4.339218139648437500e-05 2.813339233398437500e-05 5.292892456054687500e-05 1.921653747558593750e-04
diff --git a/buch/papers/multiplikation/code/meas_256.pdf b/buch/papers/multiplikation/code/meas_256.pdf
index 5f049dc..2eb177b 100644
--- a/buch/papers/multiplikation/code/meas_256.pdf
+++ b/buch/papers/multiplikation/code/meas_256.pdf
Binary files differ
diff --git a/buch/papers/multiplikation/code/meas_256.txt b/buch/papers/multiplikation/code/meas_256.txt
index 15035c6..62e77cb 100644
--- a/buch/papers/multiplikation/code/meas_256.txt
+++ b/buch/papers/multiplikation/code/meas_256.txt
@@ -1,6 +1,6 @@
2.000000000000000000e+00 4.000000000000000000e+00 8.000000000000000000e+00 1.600000000000000000e+01 3.200000000000000000e+01 6.400000000000000000e+01 1.280000000000000000e+02 2.560000000000000000e+02
-1.049041748046875000e-05 5.340576171875000000e-05 5.936622619628906250e-04 2.707719802856445312e-03 2.246093750000000000e-02 1.631326675415039062e-01 1.335460901260375977e+00 1.052024245262145996e+01
-4.768371582031250000e-06 5.531311035156250000e-05 8.208751678466796875e-04 3.099203109741210938e-03 2.490711212158203125e-02 2.070860862731933594e-01 1.739669799804687500e+00 1.384817218780517578e+01
-1.478195190429687500e-05 1.132488250732421875e-04 5.970001220703125000e-04 3.906726837158203125e-03 3.041696548461914062e-02 2.000186443328857422e-01 1.392681598663330078e+00 9.388872385025024414e+00
-1.716613769531250000e-05 6.866455078125000000e-05 5.314350128173828125e-04 2.688407897949218750e-03 1.695108413696289062e-02 1.297233104705810547e-01 1.087257385253906250e+00 8.699601650238037109e+00
-2.336502075195312500e-05 4.529953002929687500e-06 8.106231689453125000e-06 4.291534423828125000e-05 6.008148193359375000e-05 8.988380432128906250e-05 1.647472381591796875e-04 4.460811614990234375e-04
+1.144409179687500000e-05 5.507469177246093750e-05 3.774166107177734375e-04 3.177404403686523438e-03 2.508044242858886719e-02 2.120554447174072266e-01 1.431464910507202148e+00 1.076412820816040039e+01
+5.722045898437500000e-06 5.745887756347656250e-05 4.494190216064453125e-04 3.611087799072265625e-03 3.317713737487792969e-02 2.292332649230957031e-01 2.090558290481567383e+00 1.306217479705810547e+01
+1.788139343261718750e-05 1.168251037597656250e-04 5.981922149658203125e-04 4.416465759277343750e-03 3.002405166625976562e-02 2.104022502899169922e-01 1.488269329071044922e+00 9.164114713668823242e+00
+1.955032348632812500e-05 7.224082946777343750e-05 3.829002380371093750e-04 2.558946609497070312e-03 2.043128013610839844e-02 1.361320018768310547e-01 1.089214324951171875e+00 8.553364753723144531e+00
+2.384185791015625000e-05 5.245208740234375000e-06 6.437301635742187500e-06 2.455711364746093750e-05 4.148483276367187500e-05 8.702278137207031250e-05 3.793239593505859375e-04 6.709098815917968750e-04
diff --git a/buch/papers/multiplikation/code/meas_32.pdf b/buch/papers/multiplikation/code/meas_32.pdf
index 94c3731..b926095 100644
--- a/buch/papers/multiplikation/code/meas_32.pdf
+++ b/buch/papers/multiplikation/code/meas_32.pdf
Binary files differ
diff --git a/buch/papers/multiplikation/code/meas_32.txt b/buch/papers/multiplikation/code/meas_32.txt
index afdb6d5..0fdc18d 100644
--- a/buch/papers/multiplikation/code/meas_32.txt
+++ b/buch/papers/multiplikation/code/meas_32.txt
@@ -1,6 +1,6 @@
2.000000000000000000e+00 4.000000000000000000e+00 8.000000000000000000e+00 1.600000000000000000e+01 3.200000000000000000e+01
-1.215934753417968750e-05 5.459785461425781250e-05 3.700256347656250000e-04 3.249406814575195312e-03 1.996850967407226562e-02
-4.529953002929687500e-06 5.650520324707031250e-05 4.577636718750000000e-04 4.029273986816406250e-03 2.444481849670410156e-02
-1.311302185058593750e-05 1.165866851806640625e-04 6.275177001953125000e-04 4.323244094848632812e-03 2.624726295471191406e-02
-1.835823059082031250e-05 6.890296936035156250e-05 3.914833068847656250e-04 2.423048019409179688e-03 1.761770248413085938e-02
-1.263618469238281250e-05 5.006790161132812500e-06 5.960464477539062500e-06 1.144409179687500000e-05 3.600120544433593750e-05
+1.239776611328125000e-05 5.507469177246093750e-05 3.802776336669921875e-04 2.795457839965820312e-03 2.073740959167480469e-02
+5.006790161132812500e-06 5.841255187988281250e-05 3.988742828369140625e-04 3.505229949951171875e-03 2.511668205261230469e-02
+1.335144042968750000e-05 1.149177551269531250e-04 6.387233734130859375e-04 4.088878631591796875e-03 2.969408035278320312e-02
+1.955032348632812500e-05 8.058547973632812500e-05 3.998279571533203125e-04 2.514839172363281250e-03 1.842117309570312500e-02
+1.215934753417968750e-05 8.583068847656250000e-06 6.675720214843750000e-06 2.694129943847656250e-05 2.789497375488281250e-05
diff --git a/buch/papers/multiplikation/code/meas_4096.pdf b/buch/papers/multiplikation/code/meas_4096.pdf
new file mode 100644
index 0000000..e889d17
--- /dev/null
+++ b/buch/papers/multiplikation/code/meas_4096.pdf
Binary files differ
diff --git a/buch/papers/multiplikation/code/meas_4096.txt b/buch/papers/multiplikation/code/meas_4096.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/buch/papers/multiplikation/code/meas_4096.txt
diff --git a/buch/papers/multiplikation/code/meas_64.pdf b/buch/papers/multiplikation/code/meas_64.pdf
index 3a90949..92af29b 100644
--- a/buch/papers/multiplikation/code/meas_64.pdf
+++ b/buch/papers/multiplikation/code/meas_64.pdf
Binary files differ
diff --git a/buch/papers/multiplikation/code/meas_64.txt b/buch/papers/multiplikation/code/meas_64.txt
index ae6ff9b..b4fc7a1 100644
--- a/buch/papers/multiplikation/code/meas_64.txt
+++ b/buch/papers/multiplikation/code/meas_64.txt
@@ -1,6 +1,6 @@
2.000000000000000000e+00 4.000000000000000000e+00 8.000000000000000000e+00 1.600000000000000000e+01 3.200000000000000000e+01 6.400000000000000000e+01
-1.645088195800781250e-05 7.295608520507812500e-05 3.807544708251953125e-04 2.672195434570312500e-03 2.010774612426757812e-02 1.662156581878662109e-01
-7.390975952148437500e-06 7.843971252441406250e-05 4.265308380126953125e-04 3.107070922851562500e-03 2.457642555236816406e-02 2.122807502746582031e-01
-1.931190490722656250e-05 1.568794250488281250e-04 7.593631744384765625e-04 3.937005996704101562e-03 3.596329689025878906e-02 2.131938934326171875e-01
-2.622604370117187500e-05 9.226799011230468750e-05 3.504753112792968750e-04 2.469539642333984375e-03 1.652932167053222656e-02 1.281068325042724609e-01
-1.788139343261718750e-05 7.152557373046875000e-06 6.914138793945312500e-06 1.120567321777343750e-05 2.884864807128906250e-05 6.914138793945312500e-05
+2.145767211914062500e-05 6.175041198730468750e-05 4.422664642333984375e-04 3.235816955566406250e-03 2.289748191833496094e-02 1.855163574218750000e-01
+1.025199890136718750e-05 6.341934204101562500e-05 5.202293395996093750e-04 3.566026687622070312e-03 3.026723861694335938e-02 2.312932014465332031e-01
+2.384185791015625000e-05 1.807212829589843750e-04 6.821155548095703125e-04 4.796504974365234375e-03 2.968001365661621094e-02 2.291278839111328125e-01
+3.504753112792968750e-05 1.106262207031250000e-04 4.322528839111328125e-04 2.696514129638671875e-03 2.188420295715332031e-02 1.477701663970947266e-01
+3.218650817871093750e-05 1.144409179687500000e-05 7.390975952148437500e-06 4.625320434570312500e-05 3.814697265625000000e-05 5.435943603515625000e-05
diff --git a/buch/papers/multiplikation/einlteung.tex b/buch/papers/multiplikation/einlteung.tex
index bc4bfcf..9f1cb04 100755
--- a/buch/papers/multiplikation/einlteung.tex
+++ b/buch/papers/multiplikation/einlteung.tex
@@ -7,7 +7,7 @@
\rhead{Einleitung}
Die Multiplikation zweier Matrizen ist eine wichtige Operation die in verschiedensten Teilen der Mathematik Anwendung findet.
-Die Beschreibung der Multiplikation aus der Definition 2.10 (\textcolor{blue} {Kein Hyperlink zu einer Definition?)}:
+Die Beschreibung der Multiplikation aus der Definition 2.10:
Eine $m\times n$-Matrix $\mathbf{A}\in M_{m\times n}(\Bbbk)$ und eine
$n\times p$-Matrix $\mathbf{B}\in M_{n\times l}(\Bbbk)$ haben als Produkt
@@ -17,14 +17,8 @@ Koeffizienten
c_{ij} = \sum_{k=1}^n a_{ik} b_{kj}.
\label{multiplikation:eq:MM}
\end{equation}
-Grafisch kann die Matrizenmultiplikation $AB=C$ wie in \ref{multiplikation:fig:mm_viz} visualisiert werden.
-\begin{figure}
- \center
- \includegraphics[]{papers/multiplikation/images/mm_visualisation}
- \caption{Matrizen Multiplikation}
- \label{multiplikation:fig:mm_viz}
-\end{figure}
-Im Fall einer Matrizengr\"osse von $2\times 2$
+Grafisch kann die Matrizenmultiplikation $\mathbf{AB}=\mathbf{C}$ wie in Abbildung \ref{multiplikation:fig:mm_viz} visualisiert werden.
+Im Fall einer Matrizengr\"osse von $2\times 2$ kann die Matrixgleichung
\begin{equation}
\begin{bmatrix}
A_{11} & A_{12}\\
@@ -40,7 +34,7 @@ C_{11} & C_{12}\\
C_{21} & C_{22}
\end{bmatrix}
\end{equation}
-kann die Gleichung der einzelnen Terme
+explizt als Gleichung
\begin{equation} \label{multiplikation:eq:MM_exp}
\begin{split}
C_{11} &= A_{11} \cdot B_{11} + A_{12} \cdot B_{21}\\
@@ -49,4 +43,10 @@ C_{21} &= A_{21} \cdot B_{11} + A_{22} \cdot B_{21}\\
C_{22} &= A_{21} \cdot B_{12} + A_{22} \cdot B_{22}
\end{split}
\end{equation}
-explizit geschrieben werden.
+der einzelnen Terme geschrieben werden.
+\begin{figure}
+ \center
+ \includegraphics[]{papers/multiplikation/images/mm_visualisation}
+ \caption{Matrizen Multiplikation}
+ \label{multiplikation:fig:mm_viz}
+\end{figure}
diff --git a/buch/papers/multiplikation/images/bigo.pdf b/buch/papers/multiplikation/images/bigo.pdf
index dfa2ba4..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 e3293e4..9ee3a68 100644
--- a/buch/papers/multiplikation/images/bigo.tex
+++ b/buch/papers/multiplikation/images/bigo.tex
@@ -39,67 +39,71 @@
\begin{document}
\begin{tikzpicture}
+
\begin{axis}[
- axis lines = left,
- xlabel = $n$ (Data Input),
- ylabel = {$t$ (time)},
- legend pos=north east,
+ xmode=log, ymode=log,
+ xmin=1e-0, xmax=5000,
+ ymin=10e-1, ymax=1e7,
+ grid=both,
+ major grid style={black!50},
+ xlabel = data input size,
+ ylabel = {time},
+ legend pos=north west,
very thick,
- ymax = 500,
yticklabels=\empty,
xticklabels=\empty,
scale only axis=true,
- width=12cm, height=6cm,
+ width=12cm, height=8cm,
]
\addplot [
- domain= 1:20,
+ domain= 1:5000,
samples=100,
color=red,
]
{1};
\addlegendentry{$\mathcal{O}(1)$}
\addplot [
- domain= 1:20,
+ domain= 1:5000,
samples=100,
color=green,
]
{x};
\addlegendentry{$\mathcal{O}(n)$}
\addplot [
- domain= 1:20,
+ domain= 1:50000,
samples=100,
color=blue,
]
{x^2};
-\addlegendentry{$\mathcal{O}(n^2)$}
+\addlegendentry{$\mathcal{O}\left(n^2\right)$}
\addplot [
- domain= 1:10,
+ domain= 1:500,
samples=100,
color=purple,
]
{x^3};
-\addlegendentry{$\mathcal{O}(n^3)$}
+\addlegendentry{$\mathcal{O}\left(n^3\right)$}
\addplot [
- domain= 1:10,
+ domain= 1:500,
samples=100,
color=black,
]
-{exp(x)};
-\addlegendentry{$\mathcal{O}(e^n)$}
+{exp(x) - 1.7};
+\addlegendentry{$\mathcal{O}\left(e^n\right)$}
\addplot [
- domain= 1:20,
+ domain= 1:5000,
samples=100,
color=orange,
]
-{log2(x)};
+{log2(x)+1};
\addlegendentry{$\mathcal{O}(\log n)$}
\addplot [
- domain= 1:20,
+ domain= 1:5000,
samples=100,
color=gray,
]
-{x*log2(x)};
+{x*log2(x)+1};
\addlegendentry{$\mathcal{O}(n \log n)$}
\end{axis}
\end{tikzpicture}
diff --git a/buch/papers/multiplikation/images/c_meas_4096.pdf b/buch/papers/multiplikation/images/c_meas_4096.pdf
new file mode 100644
index 0000000..304015a
--- /dev/null
+++ b/buch/papers/multiplikation/images/c_meas_4096.pdf
Binary files differ
diff --git a/buch/papers/multiplikation/images/meas_1024.pdf b/buch/papers/multiplikation/images/meas_1024.pdf
new file mode 100644
index 0000000..70c7ec1
--- /dev/null
+++ b/buch/papers/multiplikation/images/meas_1024.pdf
Binary files differ
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/images/strassen.pdf b/buch/papers/multiplikation/images/strassen.pdf
index 9899dcb..a30fdaa 100644
--- a/buch/papers/multiplikation/images/strassen.pdf
+++ b/buch/papers/multiplikation/images/strassen.pdf
Binary files differ
diff --git a/buch/papers/multiplikation/images/strassen.tex b/buch/papers/multiplikation/images/strassen.tex
index 797772b..5cf39b4 100644
--- a/buch/papers/multiplikation/images/strassen.tex
+++ b/buch/papers/multiplikation/images/strassen.tex
@@ -81,13 +81,13 @@
\node at (-3,-10) {$C_{12}=$} ;
\node at (-3,-5) {$C_{11}=$} ;
- \node at (5,-2) {I};
- \node at (10,-2) {II};
- \node at (15,-2) {III};
- \node at (20,-2) {IV};
- \node at (25,-2) {V};
- \node at (30,-2) {VI};
- \node at (35,-2) {VII};
+ \node at (5,-2) {P};
+ \node at (10,-2) {Q};
+ \node at (15,-2) {R};
+ \node at (20,-2) {S};
+ \node at (25,-2) {T};
+ \node at (30,-2) {U};
+ \node at (35,-2) {V};
}
diff --git a/buch/papers/multiplikation/loesungsmethoden.tex b/buch/papers/multiplikation/loesungsmethoden.tex
index 83be814..a7612e1 100755
--- a/buch/papers/multiplikation/loesungsmethoden.tex
+++ b/buch/papers/multiplikation/loesungsmethoden.tex
@@ -4,18 +4,18 @@
% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
%
-\section{L\"osungsmethoden}
-\rhead{L\"osungsmethoden}
+\section{Algorithmen}
+\rhead{Algorithmen}
-In diesem Abschnitt werden mehrere Algorithmen zur Berechnung der Matrizenmultiplikation vorgestellt, auch werden Libraries zur automatisierten Verwendung von vordefinierten Algorithmen gezeigt.
+In diesem Abschnitt werden mehrere Algorithmen zur Berechnung der Matrizenmultiplikation vorgestellt, auch werden Bibliotheken zur automatisierten Verwendung von vordefinierten Algorithmen gezeigt.
\subsection{Standard Algorithmus}
-Der Standard Methode kann im Algorithmus \ref{multiplikation:alg:smm} entnommen werden.
+Die Standardmethode kann im Algorithmus \ref{multiplikation:alg:smm} entnommen werden.
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.
+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}\caption{Matrix Multiplication}
+\begin{algorithm}\footnotesize\caption{Matrizenmultiplikation}
\label{multiplikation:alg:smm}
\setlength{\lineskip}{7pt}
\begin{algorithmic}[1]
@@ -39,16 +39,18 @@ Die \texttt{For i} Schleife iteriert \"uber alle Zeilen der $\mathbf{A}$ Matrix,
\end{algorithmic}
\end{algorithm}
-Die Laufzeit dieser Struktur mit drei \texttt{For} Schleifen ist $\mathcal{O}(n^3)$
+Die Laufzeit dieser Struktur mit drei \texttt{For} Schleifen ist $\mathcal{O}\left(n^3\right)$
\subsubsection{Divide and Conquer Methode}
-F\"ur gewisse Algorithmen f\"uhren \textit{Divide and Conquer} Ans\"atze zu markant besseren Laufzeiten.
-Das bekannteste Beispiel ist wohl die \textit{Fast Fourier Transform} wobei die Laufzeit von $\mathcal{O}(n^2)$ zu $\mathcal{O}(n \log n)$ verbessert werden kann.
+F\"ur gewisse Algorithmen f\"uhren \textit{Divide and Conquer} Ans\"atze \cite{multiplikation:DAC} zu markant besseren Laufzeiten.
+Die Grundidee ist, dass ein Problem in mehrere, meist simplere und kleinere Teilprobleme aufgeteilt wird.
+Das bekannteste Beispiel ist wohl die \textit{Fast Fourier Transform} wobei die Laufzeit von $\mathcal{O}\left(n^2\right)$ zu $\mathcal{O}(n \log n)$ verbessert werden kann.
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}$
+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 Produkt
\begin{equation}
\mathbf{A}\mathbf{B}=
\begin{bmatrix}
@@ -63,20 +65,18 @@ Die Matrizen $\mathbf{A}$ und $\mathbf{B}$ werden in jeweils vier Blockmatrizen
\begin{bmatrix}
\mathbf{C}_{11} & \mathbf{C}_{12}\\
\mathbf{C}_{21} & \mathbf{C}_{22}
-\end{bmatrix}
+\end{bmatrix},
\end{equation}
-aufgeteilt.
-Die Berechnung
\begin{equation}
-\mathbf{C}_{ij} = \sum_{k=1}^n \mathbf{A}_{ik} \mathbf{B}_{kj}
+\mathbf{C}_{ij} = \sum_{k=1}2n \mathbf{A}_{ik} \mathbf{B}_{kj}
\label{multiplikation:eq:MM_block}
\end{equation}
-ist identisch zu der Gleichung \eqref{multiplikation:eq:MM}, wobei hier f\"ur die Multiplikation die Matrizenmultiplikation verwendet wird.
+ist identisch zu der Gleichung \eqref{multiplikation:eq:MM}, f\"ur die Multiplikation der Untermatrize $\mathbf{A}_{ik}$ und $\mathbf{B}_{kj}$ wird die Matrizenmultiplikation verwendet.
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}\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,37 +105,33 @@ 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} berechnet werden.
-Ohne auf diesen vertieft einzugehen, bestimmt die Anzahl rekursiver Aufrufe der Funktion die Laufzeit.
+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}
- \mathcal{T}(n) =
- \begin{cases}
- 1 & \text{if } n \leq 2\\
- 8 \cdot \mathcal{T}(\frac{n}{2}) + n^2 & \text{if } n > 2
- \end{cases} = \mathcal{O}(n^{\log_2 8}) = \mathcal{O}(n^{3})
+ \mathcal{T}(n) = 8 \cdot \mathcal{T}\left (\frac{n}{2}\right ) + n^2 = \mathcal{O}(n^{\log_2 8}) = \mathcal{O}\left (n^{3} \right )
\end{equation}
zu einer kubischen Laufzeit.
Die Addition zweier Matrizen $\mathbf{A} + \mathbf{B} = \mathbf{C}$ hat eine Laufzeit von $\mathcal{O}(n^{2})$ und kann neben dem dominierendem Anteil von $\mathcal{O}(n^{3})$ ignoriert werden.
In diesem Fall hat der \textit{Divide and Conquer} Ansatz zu keiner Verbesserung gef\"uhrt.
-\subsection{Strassen's Algorithmus}
+\subsection{Strassens Algorithmus}
-Strassen's Algorithmus \cite{multiplikation:strassen_1969} beschreibt die Matrizenmultiplikation mit einer Vielzahl von Additionen, Subtraktionen und Multiplikationen.
-Die Grundlegenden Terme
+Strassens Algorithmus \cite{multiplikation:strassen_1969} beschreibt die Matrizenmultiplikation mit einer Vielzahl von Additionen, Subtraktionen und Multiplikationen von Blockmatrizen.
+Die sieben grundlegenden Terme
\begin{equation} \label{multiplikation:eq:strassen}
\begin{split}
-\text{\textbf{P}} &= (\mathbf{A}_{11} + \mathbf{A}_{22}) \cdot (\mathbf{B}_{11} + \mathbf{B}_{22}) \\
-\text{\textbf{Q}} &= (\mathbf{A}_{21} + \mathbf{A}_{22}) \cdot \mathbf{B}_{11} \\
-\text{\textbf{R}} &= \mathbf{A}_{11} \cdot (\mathbf{B}_{12}-\mathbf{B}_{22}) \\
-\text{\textbf{S}} &= \mathbf{A}_{22} \cdot (-\mathbf{B}_{11}+\mathbf{B}_{21}) \\
-\text{\textbf{T}} &= (\mathbf{A}_{11} + \mathbf{A}_{12}) \cdot \mathbf{B}_{22} \\
-\text{\textbf{U}} &= (-\mathbf{A}_{11} + \mathbf{A}_{21}) \cdot (\mathbf{B}_{11} + \mathbf{B}_{12}) \\
-\text{\textbf{V}} &= (\mathbf{A}_{12} - \mathbf{A}_{22}) \cdot (\mathbf{B}_{21} + \mathbf{B}_{22})
+\text{\textbf{P}} &= \left(\mathbf{A}_{11} + \mathbf{A}_{22}\right ) \cdot \left(\mathbf{B}_{11} + \mathbf{B}_{22}\right ) \\
+\text{\textbf{Q}} &= \left(\mathbf{A}_{21} + \mathbf{A}_{22}\right ) \cdot \mathbf{B}_{11} \\
+\text{\textbf{R}} &= \mathbf{A}_{11} \cdot \left(\mathbf{B}_{12}-\mathbf{B}_{22}\right ) \\
+\text{\textbf{S}} &= \mathbf{A}_{22} \cdot \left(-\mathbf{B}_{11}+\mathbf{B}_{21}\right ) \\
+\text{\textbf{T}} &= \left(\mathbf{A}_{11} + \mathbf{A}_{12}\right ) \cdot \mathbf{B}_{22} \\
+\text{\textbf{U}} &= \left(-\mathbf{A}_{11} + \mathbf{A}_{21}\right ) \cdot \left(\mathbf{B}_{11} + \mathbf{B}_{12}\right ) \\
+\text{\textbf{V}} &= \left(\mathbf{A}_{12} - \mathbf{A}_{22}\right ) \cdot \left(\mathbf{B}_{21} + \mathbf{B}_{22}\right )
\end{split}
\end{equation}
-aus $\mathbf{A}$ und $\mathbf{B}$, werden f\"ur die Berechnung der Matrix $\mathbf{C}$
+aus $\mathbf{A}$ und $\mathbf{B}$, werden f\"ur die Berechnung der Bl\"ocke
\begin{equation} \label{multiplikation:eq:strassen2}
\begin{split}
\mathbf{C}_{11} &= \text{\textbf{P}} + \text{\textbf{S}} - \text{\textbf{T}} + \text{\textbf{V}} \\
@@ -144,8 +140,8 @@ aus $\mathbf{A}$ und $\mathbf{B}$, werden f\"ur die Berechnung der Matrix $\math
\mathbf{C}_{22} &= \text{\textbf{P}} + \text{\textbf{R}} - \text{\textbf{Q}} + \text{\textbf{U}}
\end{split}
\end{equation}
-gebraucht.
-\begin{algorithm}\caption{Strassen Matrix Multiplication}
+der Matrix $\mathbf{C}$ gebraucht.
+\begin{algorithm}\footnotesize\caption{Strassen Matrizenmultiplikation}
\label{multiplikation:alg:strassen}
\setlength{\lineskip}{7pt}
\begin{algorithmic}
@@ -190,52 +186,67 @@ gebraucht.
\EndFunction
\end{algorithmic}
\end{algorithm}
-Strassens'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}$.
+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}
Die Funktion wird sieben mal rekursiv aufgerufen.
-Dies f\"uhrt zu einer Laufzeit von
+Dies f\"uhrt nach dem \textit{Master Theorem} zu einer Laufzeit von
\begin{equation} \label{multiplikation:eq:laufzeitstrassen}
\mathcal{T}(n) =
-\begin{cases}
-1 & \text{if } n \leq 2\\
-7 \cdot \mathcal{T}(\frac{n}{2}) + n^2 & \text{if } n > 2
-\end{cases} = \mathcal{O}(n^{\log_2 7}) = \mathcal{O}(n^{2.8074})
+7 \cdot \mathcal{T}(\frac{n}{2}) + n^2 = \mathcal{O}\left(n^{\log_2 7}\right ) = \mathcal{O}\left(n^{2.8074} \right )
\end{equation}
-und ist somit schneller als die Standard Methode.
+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}
-Ein weiterer Ansatz lieferte Shmuel Winograd im Jahre 1968 \cite{multiplikation:winograd_1968}.
-Er zeigte einen neuen Algorithmus f\"ur das
-\begin{equation}
- \langle x,y \rangle = \sum_{i=1}^{n}x_i y_i
+Einen weiteren Ansatz lieferte Shmuel Winograd im Jahre 1968 \cite{multiplikation:winograd_1968}.
+Er beschrieb einen neuen Algorithmus f\"ur das Skalarprodukt
+\begin{equation} \label{multiplikation:eq:skalar}
+ \langle x,y \rangle = \sum_{i=1}^{n}x_i y_i.
\end{equation}
-Skalarprodukt.
F\"ur jeden Vektor berechne
\begin{equation}
\xi = \sum_{j=1}^{ \lfloor n/2 \rfloor} x_{2j-1} \cdot x_{2j}
\end{equation}
und
\begin{equation}
- \eta = \sum_{j=1}^{ \lfloor n/2 \rfloor} y_{2j-1} \cdot y_{2j}.
+ \eta = \sum_{j=1}^{ \lfloor n/2 \rfloor} y_{2j-1} \cdot y_{2j},
\end{equation}
+die jeweils nur von $x$ und $y$ abhängen.
+Dazu werden $2 \cdot \lfloor n/2 \rfloor \leq n$ Multiplikationen benötigt.
Das Skalarprodukt ist nun geben mit
\begin{equation}
\langle x,y \rangle =
\begin{cases}
- \displaystyle \quad \sum_{j=1}^{ \lfloor n/2 \rfloor} (x_{2j-1} + y_{2j})(x_{2j}+y_{2j-1})-\xi - \eta & \text{if $n$ is even}\\
- \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{if $n$ is odd}.
+ \displaystyle \quad \sum_{j=1}^{ \lfloor n/2 \rfloor} (x_{2j-1} + y_{2j})(x_{2j}+y_{2j-1})-\xi - \eta & \text{wenn $n$ gerade}\\
+ \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 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}
+ \begin{split}\label{multiplikation:eq:eff}
+ N\lfloor n/2 \rfloor + T\lfloor (n+1)/2 \rfloor \leq Tn \\
+ \approx \frac{Nn}{2} + \frac{Tn}{2} \leq Tn \\
+ \frac{Nn}{2} \leq \frac{Tn}{2} \\
+ N \leq T
+\end{split}
+\end{equation}
+spart man etwas, falls $N\leq T$.
Eine Matrizenmultiplikation mit $\mathbf{A}$ einer $m \times n$ und $\mathbf{B}$ einer $n \times p$ Matrix, entspricht $N=m+p$ Vektoren mit welchen man $T=mp$ Skalarprodukte berechnet.
Dies f\"uhrt zu
\begin{equation}
@@ -243,10 +254,21 @@ Dies f\"uhrt zu
\end{equation}
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 Standard Methode nur die H\"alfte ist.
-Die Implementation kann im Algorithmus \ref{multiplikation:alg:winograd} entnommen werden.
-
-\begin{algorithm}\caption{Winograd Matrix Multiplication}
+Was im Vergleich zu den $mpn$ Multiplikation der Standardmethode nur die H\"alfte ist.
+Mit dem gleichen Ansatz wie in der Gleichung \ref{multiplikation:eq:eff} aber mit quadratischen Matrizen, muss
+\begin{equation}
+ \begin{split}
+N=2n, \quad T = n^2 \\
+ 2n \leq n^2 \\
+ 2 \leq n
+\end{split}
+\end{equation}
+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
+ somit entsteht für diesen Algorithmus wieder die Ursprüngliche Laufzeit von $\mathcal{O}\left(n^3 \right)$.
+\begin{algorithm}\footnotesize\caption{Winograds Matrizenmultiplikation}
\setlength{\lineskip}{7pt}
\label{multiplikation:alg:winograd}
\begin{algorithmic}
@@ -297,13 +319,171 @@ Die Implementation kann im Algorithmus \ref{multiplikation:alg:winograd} entnomm
\end{algorithmic}
\end{algorithm}
-\subsection{Weitere Algorithmen}
-\textcolor{red}{TODO: BLAS}
+\subsection{Basic Linear Algebra Subprograms (BLAS)}
+
+Die gebräuchliche Methode f\"ur die Anwendung einer optimierten Matrizenmultiplikation ist die Verwendung einer Subroutine aus den \textit{Basic Linear Algebra Subprograms (BLAS)} \cite{multiplikation:BLAS}.
+Die meisten Numerischen Bibliotheken von High-Level Skriptsprachen wie \texttt{Matlab}, \texttt{NumPy (Python)}, \texttt{GNU Octave} oder \texttt{Mathematica} ben\"utzen eine Form von \textit{BLAS}.
+
+\textit{BLAS} sind dabei in drei unterschiedliche Levels aufgeteilt.
+
+\begin{itemize}
+ \item Level 1
+ \begin{itemize}
+ \item Operationen der Art: $\mathbf{y} \leftarrow \alpha \mathbf{x}+\mathbf{y}$
+ \item Dieses Level hat $\mathcal{O}(n)$ Charakteristik
+ \end{itemize}
+ \item Level 2
+ \begin{itemize}
+ \item Operationen der Art: $\mathbf{y} \leftarrow \alpha \mathbf{A}\mathbf{x}+\beta \mathbf{y}$
+ \item Dieses Level hat $\mathcal{O}\left(n^2\right)$ Charakteristik
+ \end{itemize}
+ \item Level 3
+ \begin{itemize}
+ \item Operationen der Art: $\mathbf{C} \leftarrow \alpha \mathbf{A}\mathbf{B}+\beta\mathbf{C}$
+ \item Dieses Level hat $\mathcal{O}\left(n^3\right)$ Charakteristik
+ \end{itemize}
+\end{itemize}
+
+Die \textit{BLAS} sind auf die modernen Computer Prozessoren optimiert und k\"onnen dank einer ausgeklügelter Verwendung der Speicherarchitektur zu erheblichen Leistungsoptimierungen f\"uhren.
+
+
+\subsubsection{General Matrix Multiplication (GEMM)}
-\section{Implementation}
+Die \textit{Double-GEMM} \cite{multiplikation:DGEMM} ist definiert als:
+
+\textit{DGEMM performs one of the matrix-matrix operations}
+$$
+ C := \alpha \cdot op( A )\cdot op( B ) + \beta \cdot C,
+ $$
+ \textit{where op( X ) is one of}
+$$
+op( X ) = X \quad \text{ or } \quad op( X ) = X^T,
+$$
+ \textit{alpha and beta are scalars, and A, B and C are matrices, with op( A )
+ an m by k matrix, op( B ) a k by n matrix and C an m by n matrix.
+ }
+
+%Die Implementation von $\alpha\mathbf{A}\mathbf{B} + \beta \mathbf{C} = \mathbf{C}$, wobei $\alpha = 1.0$ und $\beta = 0.0$ in der \texttt{C}-Version von \textit{BLAS}, ist als
+%\begin{lstlisting}[style=multiplikationC]
+%cblas_dgemm(CblasRowMajor, CblasNoTrans, CblasNoTrans,
+% m, n, k, 1, A, m , B, k, 0, C, m);
+%\end{lstlisting}
+%definiert.
+
+
+
+\section{Implementation}\label{multiplikation:section:Implementation}
\rhead{Implementation}
-\textcolor{red}{TODO: messresultate}
+
+Folgende Algorithmen wurden jeweils in \texttt{C} und \texttt{Python} implementiert.
+\begin{itemize}
+ \item Standard Matrizenmultiplikation
+ \item \textit{Devide and Conquer} Matrizenmultiplikation
+ \item Strassens Matrizenmultiplikation
+ \item Winograds Matrizenmultiplikation
+ \item \texttt{BLAS} Matrizenmultiplikation in \texttt{C}
+ \item \texttt{Numpy} Matrizenmultiplikation in \texttt{Python}
+\end{itemize}
+
+Der Code kann im zum Buch gehörigem \textit{GitHub} \footnote{\url{https://github.com/AndreasFMueller/SeminarMatrizen.git}} Repository gefunden werden.
+Anzumerken ist, dass die Matrizenmultiplikation von \texttt{NumPy} als einzige Implementation Multiprocessing und Multithreading verwendet, dies f\"uhrt zu den tiefen Messzeiten.
+In Abbildung \ref{multiplikation:fig:python} und Abbildung \ref{multiplikation:fig:c_meas_4096} sind de Messresultate grafisch dargestellt. Die selben Messresultate sind tabellarisch in Tabelle \ref{multiplikation:tab:messung_Python} und Tabelle \ref{multiplikation:tab:messung_C} ersichtlich.
+Die Hardwareinformationen des verwendeten Computers sind in der Tabelle \ref{multiplikation:tab:pc_config} aufgelistet.
+
+
+\begin{table}
+ \begin{center}
+ \begin{tabular}{l l l l l l}
+ \hline
+ \hline
+ \textbf{n} & \textbf{MM (\textit{s})} & \textbf{MM DC (\textit{s})} & \textbf{Strassen (\textit{s})} & \textbf{Winograd (\textit{s})} & \textbf{BLAS (\textit{s})} \\
+ \hline
+ \multicolumn{6}{c}{} \\
+ \textbf{32} & 0.000081 &0.000594 & 0.00047& 0.00010 & 0.000022 \\
+ \textbf{64} & 0.00065 & 0.0042& 0.0033& 0.00065& 0.00017 \\
+ \textbf{128} & 0.0055 & 0.036& 0.024& 0.0052 & 0.0012 \\
+ \textbf{256} & 0.054 & 0.32 & 0.17 & 0.057& 0.010 \\
+ \textbf{512} & 0.48 & 2.61 & 1.20 & 0.51 & 0.074\\
+ \textbf{1024} & 4.16 & 19.92& 8.45 & 4.53 & 0.704 \\
+ \textbf{2048} & 125.90 & 159.33& 59.26 & 130.62 & 6.84 \\
+ \textbf{4096} & 1111.31 & 1147.10& 414.64 & 1179.26 & 55.84\\
+ \multicolumn{6}{c}{} \\
+ \hline
+ \hline
+ \end{tabular}
+ \end{center}
+ \caption{Messresultate \texttt{C}}
+ \label{multiplikation:tab:messung_C}
+ \end{table}
+
+
+
+ \begin{table}
+ \begin{center}
+ \begin{tabular}{l l l l l l}
+ \hline
+ \hline
+ \textbf{n} & \textbf{MM (\textit{s})} & \textbf{MM DC (\textit{s})} & \textbf{Strassen (\textit{s})} & \textbf{Winograd (\textit{s})} & \textbf{\texttt{NumPy}(\textit{s})} \\
+ \hline
+ \multicolumn{6}{c}{} \\
+ \textbf{32} & 0.0240 &0.0271 & 0.04852& 0.01871 & 4.26e-05 \\
+ \textbf{64} & 0.186 & 0.265& 0.2204& 0.1530& 0.000118 \\
+ \textbf{128} & 1.563 & 1.777& 1.447& 1.1947 & 0.000244 \\
+ \textbf{256} & 11.006 & 13.27 & 9.938 & 8.298& 0.000695 \\
+ \textbf{512} & 85.476 & 105.397 & 63.961 & 68.36 & 0.00221\\
+ \textbf{1024} & 750.757 & 847.321& 461.494 & 537.374 & 0.0188 \\
+ \textbf{4096} & - & - & - & - & 1.633 \\
+ \multicolumn{6}{c}{} \\
+ \hline
+ \hline
+ \end{tabular}
+ \end{center}
+ \caption{Messresultate \texttt{Python}}
+ \label{multiplikation:tab:messung_Python}
+ \end{table}
+
+ \begin{table}
+ \begin{center}
+ \begin{tabular}{c c c c}
+ \hline
+ \hline
+ \textbf{CPU} & \textbf{OS} & \textbf{GPU } & \textbf{Memory } \\
+ \hline
+ \multicolumn{4}{c}{} \\
+ Intel® Core™ i7-4770K CPU & Ubuntu 20.04.2 LTS & Radeon RX 570 & 32 GB 1600 MHz \\
+ @ 3.50GHz × 8 & 64-bit & & \\
+ \multicolumn{4}{c}{} \\
+ \hline
+ \hline
+ \end{tabular}
+ \end{center}
+ \caption{Messsystem}
+ \label{multiplikation:tab:pc_config}
+ \end{table}
+
+\begin{figure}
+ \center
+ \includegraphics[width=\linewidth]{papers/multiplikation/images/meas_c}
+ \caption{Messresultate mit der Programmiersprache \texttt{C}}
+ \label{multiplikation:fig:c_meas_4096}
+\end{figure}
+
+
+\begin{figure}
+ \center
+ \includegraphics[width=\linewidth]{papers/multiplikation/images/meas_python}
+ \caption{Messresultate mit der Programmiersprache \texttt{Python}}
+ \label{multiplikation:fig:python}
+\end{figure}
\section{Fazit}
\rhead{Fazit}
+
+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.
+Nicht auf jeden Computersystemen können die \textit{BLAS} angewandt werden.
+Denke man an sehr kleine Mikrocontroller ohne Floatingpoint Recheneinheiten oder auch an \textit{Field Programmable Gate Arrays (FPGA's)}.
+Sobald sehr grosse Matrizen multipliziert werden müssen und eine Addition in weniger Taktzyklen als eine Multiplikation durchführt werden kann, können die gezeigten Algorithmen von Vorteil sein.
diff --git a/buch/papers/multiplikation/main.tex b/buch/papers/multiplikation/main.tex
index 8d0a8df..fb1908e 100755
--- a/buch/papers/multiplikation/main.tex
+++ b/buch/papers/multiplikation/main.tex
@@ -4,6 +4,28 @@
%
% (c) 2021 Hochschule Rapperswil
%
+\definecolor{mygreen}{RGB}{28,172,0} % color values Red, Green, Blue
+\definecolor{mylilas}{RGB}{170,55,241}
+\definecolor{backcolour}{rgb}{0.95,0.95,0.92}
+\lstdefinestyle{multiplikationC}{
+ numbers=left,
+ belowcaptionskip=1\baselineskip,
+ breaklines=true,
+ frame=l,
+ framerule=0pt,
+ framesep=-1pt,
+ xleftmargin=1em,
+ language=C,
+ showstringspaces=false,
+ basicstyle=\ttfamily,
+ keywordstyle=\bfseries\color{green!40!black},
+ commentstyle=\itshape\color{purple!40!black},
+ identifierstyle=\color{blue},
+ stringstyle=\color{red},
+ numberstyle=\ttfamily\tiny,
+ backgroundcolor=\color{backcolour}
+}
+
\chapter{Schnelle Matrizen Multiplikation\label{chapter:multiplikation}}
\lhead{FMM}
\begin{refsection}
diff --git a/buch/papers/multiplikation/problemstellung.tex b/buch/papers/multiplikation/problemstellung.tex
index b20a791..e53b0de 100755
--- a/buch/papers/multiplikation/problemstellung.tex
+++ b/buch/papers/multiplikation/problemstellung.tex
@@ -5,100 +5,118 @@
%
\section{Problemstellung}
\rhead{Problemstellung}
-Dank 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.
-Wobei gezielt auf Algorithmen, welche das Problem schneller als der Standard Algorithmus L\"osen eingegangen wird.
+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 eingegangen, welche das Problem schneller als der Standard Algorithmus l\"osen.
\subsection{Big $\mathcal{O}$ Notation}
-Die Big $\mathcal{O}$ Notation beschreibt die Laufzeitkomplexit\"at eines Algorithmus \cite{multiplikation:bigo}.
-$f(x) \in \mathcal{O}(g(x))$ besagt das die Funktion $f$ nicht wesentlich schneller w\"achst als $g$ wenn $x \rightarrow \infty$.
+\label{muliplikation:sec: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$.
+% 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
\item $f \in \mathcal{O}(n) \rightarrow f$ w\"achst linear
- \item $f \in \mathcal{O}(n^2) \rightarrow f$ w\"achst quadratisch
+ \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}(e^n) \rightarrow f$ w\"achst exponentiell
+ \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.
+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}
+
+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.
-
-\begin{algorithm}\caption{}
- \label{multiplikation:alg:b1}
- \setlength{\lineskip}{7pt}
- \begin{algorithmic}
- \Function{B1}{$a, b$}
- \State \textbf{return} $a+b$
- \EndFunction
- \end{algorithmic}
-\end{algorithm}
-
-Wobei Konstanten nicht beachtet werden, der Algorithmus \ref{multiplikation:alg:b2} f\"uhrt ebenso zu $\mathcal{O}(1)$ und nicht zu $\mathcal{O}(2)$.
-
-\begin{algorithm}\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}
+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}
-Folgender Algorithmus \ref{multiplikation:alg:l1} hat ein lineares $\mathcal{O}(n)$ Verhalten.
-
-\begin{algorithm}\caption{}
- \setlength{\lineskip}{7pt}
- \begin{algorithmic}
- \label{multiplikation:alg:l1}
- \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}
+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}
-Folgender Algorithmus \ref{multiplikation:alg:q1} hat ein quadratisches $\mathcal{O}(n^2)$ Verhalten.
-
-\begin{algorithm}[H]\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}
+Der Algorithmus \ref{multiplikation:alg:q1} hat ein quadratisches Verhalten.
+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}
diff --git a/buch/papers/multiplikation/references.bib b/buch/papers/multiplikation/references.bib
index 9d76e8e..8815386 100755
--- a/buch/papers/multiplikation/references.bib
+++ b/buch/papers/multiplikation/references.bib
@@ -63,3 +63,40 @@
month = {7},
day = {27}
}
+
+@online{multiplikation:master_theorem,
+ title = {Master theorem (analysis of algorithms)},
+ url = {https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)},
+ date = {2021-07-28},
+ year = {2021},
+ month = {7},
+ day = {28}
+}
+
+
+@online{multiplikation:DAC,
+ title = {Divide-and-conquer algorithm},
+ url = {https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm},
+ date = {2021-07-28},
+ year = {2021},
+ month = {7},
+ day = {28}
+}
+
+@online{multiplikation:BLAS,
+ title = {BLAS (Basic Linear Algebra Subprograms)},
+ url = {http://www.netlib.org/blas/},
+ date = {2021-08-01},
+ year = {2021},
+ month = {8},
+ day = {01}
+}
+
+@online{multiplikation:DGEMM,
+ title = {DGEMM},
+ url = {http://www.netlib.org/lapack/explore-html/d1/d54/group__double__blas__level3_gaeda3cbd99c8fb834a60a6412878226e1.html#gaeda3cbd99c8fb834a60a6412878226e1},
+ date = {2021-08-01},
+ year = {2021},
+ month = {8},
+ day = {01}
+}