diff options
Diffstat (limited to '')
54 files changed, 1131 insertions, 411 deletions
diff --git a/buch/papers/clifford/3d/Makefile b/buch/papers/clifford/3d/Makefile new file mode 100644 index 0000000..70dffe3 --- /dev/null +++ b/buch/papers/clifford/3d/Makefile @@ -0,0 +1,30 @@ +# +# Makefile +# +# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +# +all: dq.jpg q23.jpg q31.jpg drehung.jpg + +size="+W1920 +H1080" +size="+W3840 +H2160" + +dq.png: dq.pov common.inc + povray +A0.1 $(size) -Odq.png dq.pov +dq.jpg: dq.png + convert dq.png -density 300 -units PixelsPerInch dq.jpg + +q23.png: q23.pov common.inc + povray +A0.1 $(size) -Oq23.png q23.pov +q23.jpg: q23.png + convert q23.png -density 300 -units PixelsPerInch q23.jpg + +q31.png: q31.pov common.inc + povray +A0.1 $(size) -Oq31.png q31.pov +q31.jpg: q31.png + convert q31.png -density 300 -units PixelsPerInch q31.jpg + +drehung.png: drehung.pov common.inc + povray +A0.1 $(size) -Odrehung.png drehung.pov +drehung.jpg: drehung.png + convert drehung.png -density 300 -units PixelsPerInch drehung.jpg + diff --git a/buch/papers/clifford/3d/common.inc b/buch/papers/clifford/3d/common.inc new file mode 100644 index 0000000..54aa7fe --- /dev/null +++ b/buch/papers/clifford/3d/common.inc @@ -0,0 +1,247 @@ +// +// common.inc +// +// (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +// +#version 3.7; +#include "colors.inc" + +global_settings { + assumed_gamma 1 +} + +#declare imagescale = 0.14; +#declare r = 0.02; +#declare thick = 0.040; + +camera { + location <40, 12, 15> + look_at <0, 0, 0> + right 16/9 * x * imagescale + up y * imagescale +} + +light_source { + <40, 20, 20> color White + area_light <1,0,0> <0,0,1>, 10, 10 + adaptive 1 + jitter +} + +sky_sphere { + pigment { + color rgb<1,1,1> + } +} + +// +// draw an arrow from <from> to <to> with thickness <arrowthickness> with +// color <c> +// +#macro arrow(from, to, arrowthickness, c) +#declare arrowdirection = vnormalize(to - from); +#declare arrowlength = vlength(to - from); +union { + sphere { + from, 1.1 * arrowthickness + } + cylinder { + from, + from + (arrowlength - 5 * arrowthickness) * arrowdirection, + arrowthickness + } + cone { + from + (arrowlength - 5 * arrowthickness) * arrowdirection, + 2 * arrowthickness, + to, + 0 + } + pigment { + color c + } + finish { + specular 0.9 + metallic + } +} +#end + + +arrow(< -3, 0, 0 >, < 3, 0, 0 >, r, White) +arrow(< 0, -3, 0 >, < 0, 3, 0 >, r, White) +arrow(< 0, 0, -3 >, < 0, 0, 3 >, r, White) + +#macro circlearrow0(e1, e2, e3, r1, r2, h, winkel) + +mesh { + #declare N = 100; + #declare phi = 0; + #declare phimax = winkel - pi / 12; + #declare phistep = (phimax - phi) / N; + #while (phi < phimax - phistep/2) + triangle { + center + r1 * (cos(phi ) * e1 + sin(phi ) * e2) - h * e3, + center + r2 * (cos(phi ) * e1 + sin(phi ) * e2) - h * e3, + center + r1 * (cos(phi+phistep) * e1 + sin(phi+phistep) * e2) - h * e3 + } + triangle { + center + r1 * (cos(phi+phistep) * e1 + sin(phi+phistep) * e2) - h * e3, + center + r2 * (cos(phi ) * e1 + sin(phi ) * e2) - h * e3, + center + r2 * (cos(phi+phistep) * e1 + sin(phi+phistep) * e2) - h * e3 + } + triangle { + center + r1 * (cos(phi ) * e1 + sin(phi ) * e2) + h * e3, + center + r2 * (cos(phi ) * e1 + sin(phi ) * e2) + h * e3, + center + r1 * (cos(phi+phistep) * e1 + sin(phi+phistep) * e2) + h * e3 + } + triangle { + center + r1 * (cos(phi+phistep) * e1 + sin(phi+phistep) * e2) + h * e3, + center + r2 * (cos(phi ) * e1 + sin(phi ) * e2) + h * e3, + center + r2 * (cos(phi+phistep) * e1 + sin(phi+phistep) * e2) + h * e3 + } + triangle { + center + r1 * (cos(phi ) * e1 + sin(phi ) * e2) - h * e3, + center + r1 * (cos(phi+phistep) * e1 + sin(phi+phistep) * e2) - h * e3, + center + r1 * (cos(phi+phistep) * e1 + sin(phi+phistep) * e2) + h * e3 + } + triangle { + center + r1 * (cos(phi ) * e1 + sin(phi ) * e2) - h * e3, + center + r1 * (cos(phi+phistep) * e1 + sin(phi+phistep) * e2) + h * e3, + center + r1 * (cos(phi ) * e1 + sin(phi ) * e2) + h * e3 + } + triangle { + center + r2 * (cos(phi ) * e1 + sin(phi ) * e2) - h * e3, + center + r2 * (cos(phi+phistep) * e1 + sin(phi+phistep) * e2) - h * e3, + center + r2 * (cos(phi+phistep) * e1 + sin(phi+phistep) * e2) + h * e3 + } + triangle { + center + r2 * (cos(phi ) * e1 + sin(phi ) * e2) - h * e3, + center + r2 * (cos(phi+phistep) * e1 + sin(phi+phistep) * e2) + h * e3, + center + r2 * (cos(phi ) * e1 + sin(phi ) * e2) + h * e3 + } + #declare phi = phi + phistep; + #end + + triangle { + center + r1 * e1 - h * e3, + center + r1 * e1 + h * e3, + center + r2 * e1 + h * e3 + } + triangle { + center + r2 * e1 - h * e3, + center + r2 * e1 + h * e3, + center + r1 * e1 - h * e3 + } + triangle { + center + r1 * cos(phi) * e1 + r1 * sin(phi) * e2 - h * e3, + center + r2 * cos(phi) * e1 + r2 * sin(phi) * e2 - h * e3, + center + 0.5*(r1+r2) * (cos(phi + pi/12) * e1 + sin(phi + pi/12) * e2) - h * e3 + } + triangle { + center + r1 * cos(phi) * e1 + r1 * sin(phi) * e2 + h * e3, + center + r2 * cos(phi) * e1 + r2 * sin(phi) * e2 + h * e3, + center + 0.5*(r1+r2) * (cos(phi + pi/12) * e1 + sin(phi + pi/12) * e2) + h * e3 + } + triangle { + center + r1 * cos(phi) * e1 + r1 * sin(phi) * e2 - h * e3, + center + 0.5*(r1+r2) * (cos(phi + pi/12) * e1 + sin(phi + pi/12) * e2) - h * e3 + center + r1 * cos(phi) * e1 + r1 * sin(phi) * e2 + h * e3 + } + triangle { + center + 0.5*(r1+r2) * (cos(phi + pi/12) * e1 + sin(phi + pi/12) * e2) - h * e3 + center + r1 * cos(phi) * e1 + r1 * sin(phi) * e2 + h * e3, + center + 0.5*(r1+r2) * (cos(phi + pi/12) * e1 + sin(phi + pi/12) * e2) + h * e3 + } + triangle { + center + 0.5*(r1+r2) * (cos(phi + pi/12) * e1 + sin(phi + pi/12) * e2) - h * e3, + center + r2 * cos(phi) * e1 + r2 * sin(phi) * e2 - h * e3, + center + r2 * cos(phi) * e1 + r2 * sin(phi) * e2 + h * e3 + } + triangle { + center + 0.5*(r1+r2) * (cos(phi + pi/12) * e1 + sin(phi + pi/12) * e2) - h * e3, + center + r2 * cos(phi) * e1 + r2 * sin(phi) * e2 + h * e3, + center + 0.5*(r1+r2) * (cos(phi + pi/12) * e1 + sin(phi + pi/12) * e2) + h * e3 + } + + pigment { + color rgb<1, 0.4, 0.4> + } +} + +#end + + +#macro circlearrow(fromdirection, axis, center, r, h, winkel, anzahl) + +#declare e1 = vnormalize(fromdirection); +#declare e2 = -vnormalize(vcross(axis, fromdirection)); +#declare e3 = vnormalize(axis); + +#declare r1 = 0.4 * r; +#declare r2 = r; + +#declare w = 0; +#while (w < anzahl) + #declare a = 2 * w * pi / anzahl; + circlearrow0(e1 * cos(a) - e2 * sin(a), e1 * sin(a) + e2 * cos(a), e3, r1, r2, 1.2 * h, winkel) + #declare w = w + 1; +#end + +mesh { + #declare vlu = center - r * e1 - r * e2 - h * e3; + #declare vlo = center - r * e1 - r * e2 + h * e3; + #declare vru = center - r * e1 + r * e2 - h * e3; + #declare vro = center - r * e1 + r * e2 + h * e3; + #declare hlu = center + r * e1 - r * e2 - h * e3; + #declare hlo = center + r * e1 - r * e2 + h * e3; + #declare hru = center + r * e1 + r * e2 - h * e3; + #declare hro = center + r * e1 + r * e2 + h * e3; + triangle { vlu, vru, vro } + triangle { vlu, vro, vlo } + + triangle { vru, hru, hro } + triangle { vru, hro, vro } + + triangle { hru, hlu, hlo } + triangle { hru, hlo, hro } + + triangle { hlu, vlu, vlo } + triangle { hlu, vlo, hlo } + + triangle { vlu, vru, hru } + triangle { vlu, hru, hlu } + + triangle { vlo, vro, hro } + triangle { vlo, hro, hlo } + + pigment { + color rgb<0.6,0.6,1> + } + finish { + specular 0.96 + metallic + } +} + +#if (vlength(axis) > 0.1) +cone { + center + 1.19 * h * e3, r, center + 2 * r * e3, 0 + pigment { + color rgbt<0.6,0.6,1,0.8> + } +} +#end + +cylinder { + center, center + 2 * r * e3, 0.04*0.2 + pigment { + color rgb<1.0,0.6,0.6> + } + finish { + specular 0.96 + metallic + } +} + +#end + diff --git a/buch/papers/clifford/3d/dq.pov b/buch/papers/clifford/3d/dq.pov new file mode 100644 index 0000000..8002129 --- /dev/null +++ b/buch/papers/clifford/3d/dq.pov @@ -0,0 +1,25 @@ +// +// dq.pov -- Drehung und Quaternion +// +// (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +// +#include "common.inc" + +arrow(<0,0,0>, <1, sqrt(2), 2>, r, Red) + +#declare r = 0.2 * r; + +circlearrow(<1,0,0>, <0,0,1>, <1, sqrt(2), 0>, 1, thick, 1.8*pi/3, 3) +circlearrow(<1,0,0>, <0,1,0>, <1, 0, 2>, sqrt(2)/2, thick, 1.8*pi/3, 3) +circlearrow(<0,0,1>, <1,0,0>, <0, sqrt(2), 2>, 0.5, thick, 1.8*pi/3, 3) + +#declare l = 2.8; +#declare h = 0.0001; +union { + box { <-l,-l,-h>, <l,l,-h> } + box { <-l,-h,-l>, <l,-h,l> } + box { <-h,-l,-l>, <-h,l,l> } + pigment { + color rgbt<0.6,0.6,0.6,0.0> + } +} diff --git a/buch/papers/clifford/3d/drehung.pov b/buch/papers/clifford/3d/drehung.pov new file mode 100644 index 0000000..54b5a2e --- /dev/null +++ b/buch/papers/clifford/3d/drehung.pov @@ -0,0 +1,120 @@ +// +// drehung.pov -- Drehung um (1,1,1) +// +// (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +// +#include "common.inc" + +#declare n = vnormalize(<1,1,1>); +#declare V = <0,2.6,0>; +#declare W = <0,0,2.6>; + +#declare Vparallel = vdot(n, V) * n; +#declare Vperp = V - Vparallel; +#declare Wparallel = vdot(n, W) * n; +#declare Wperp = W - Wparallel; + +arrow(<0,0,0>, 2*n, thick, Red) + +arrow(<0,0,0>, V, thick, rgb<0.0,1.0,1.0>) +arrow(<0,0,0>, W, thick, rgb<0.0,1.0,1.0>) + +circlearrow(vnormalize(vcross(<-1,0,1>,n)), -0.01 * <1,1,1>, <0,0,0>, 1, 0.8*thick, 1.98*pi/3, 3) + +arrow(<0,0,0>, Vperp, 0.99*thick, Blue) +arrow(<0,0,0>, Wperp, 0.99*thick, Blue) + +arrow(Vperp, V, thick, Green) +arrow(Wperp, W, thick, Green) + +#declare l = 2.4; +intersection { + box { <-l,-l,-l>, <l,l,l> } + //cylinder { -n, n, 3 } + plane { n, 0.01 } + plane { -n, 0.01 } + pigment { + color rgbt<0.6,0.6,1.0,0.8> + } +} + +#declare e1 = vnormalize(Vperp); +#declare e3 = n; +#declare e2 = vnormalize(vcross(e3, e1)); +#declare r = vlength(Vperp); + +mesh { + #declare phi = 0; + #declare phimax = 2*pi/3; + #declare phistep = (phimax - phi) / N; + #while (phi < phimax - phistep/2) + triangle { + <0,0,0>, + r * (cos(phi ) * e1 + sin(phi ) * e2), + r * (cos(phi+phistep) * e1 + sin(phi+phistep) * e2) + } + #declare phi = phi + phistep; + #end + pigment { + color rgbt<0.2,0.2,1.0,0.4> + } +} + +union { + #declare phi = 0; + #declare phimax = 2*pi/3; + #declare phistep = (phimax - phi) / N; + #while (phi < phimax - phistep/2) + cylinder { + r * (cos(phi ) * e1 + sin(phi ) * e2), + r * (cos(phi+phistep) * e1 + sin(phi+phistep) * e2), + 0.01 + } + sphere { r * (cos(phi ) * e1 + sin(phi ) * e2), 0.01 } + #declare phi = phi + phistep; + #end + pigment { + color Blue + } +} + +mesh { + #declare phi = 0; + #declare phimax = 2*pi/3; + #declare phistep = (phimax - phi) / N; + #while (phi < phimax - phistep/2) + triangle { + r * (cos(phi ) * e1 + sin(phi ) * e2), + r * (cos(phi+phistep) * e1 + sin(phi+phistep) * e2), + r * (cos(phi ) * e1 + sin(phi ) * e2) + Vparallel + } + triangle { + r * (cos(phi+phistep) * e1 + sin(phi+phistep) * e2), + r * (cos(phi ) * e1 + sin(phi ) * e2) + Vparallel, + r * (cos(phi+phistep) * e1 + sin(phi+phistep) * e2) + Vparallel + } + #declare phi = phi + phistep; + #end + pigment { + color rgbt<0.2,1,0.2,0.4> + } +} + +union { + #declare phi = 0; + #declare phimax = 2*pi/3; + #declare phistep = (phimax - phi) / N; + #while (phi < phimax - phistep/2) + cylinder { + r * (cos(phi ) * e1 + sin(phi ) * e2) + Vparallel, + r * (cos(phi+phistep) * e1 + sin(phi+phistep) * e2) + Vparallel, + 0.01 + } + sphere { r * (cos(phi ) * e1 + sin(phi ) * e2) + Vparallel, 0.01 } + #declare phi = phi + phistep; + #end + pigment { + color Green + } +} + diff --git a/buch/papers/clifford/3d/q23.pov b/buch/papers/clifford/3d/q23.pov new file mode 100644 index 0000000..e3e5d49 --- /dev/null +++ b/buch/papers/clifford/3d/q23.pov @@ -0,0 +1,12 @@ +// +// q23.pov -- Drehung und Quaternion +// +// (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +// +#include "common.inc" + +circlearrow(<1,0,0>, 0.01*<0,0,-1>, <0, 0, 0>, 1.0, thick, 0.98*pi/2, 4) + +arrow( <0,0,0>, <-2.0,0,0>, 0.99*thick, Blue) +arrow( <0,0,0>, <0,2.0,0>, 0.99*thick, Blue) +arrow( <0,0,0>, <0,0,2.0>, 0.99*thick, Red) diff --git a/buch/papers/clifford/3d/q31.pov b/buch/papers/clifford/3d/q31.pov new file mode 100644 index 0000000..901f838 --- /dev/null +++ b/buch/papers/clifford/3d/q31.pov @@ -0,0 +1,12 @@ +// +// q31.pov -- Drehung und Quaternion +// +// (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +// +#include "common.inc" + +circlearrow(<1,0,0>, 0.01*<0,-1,0>, <0, 0, 0>, 1.0, thick, 0.98*pi/2, 4) + +arrow( <0,0,0>, <-2.0,0,0>, 0.99*thick, Blue) +arrow( <0,0,0>, <0,2.0,0>, 0.99*thick, Red) +arrow( <0,0,0>, <0,0,2.0>, 0.99*thick, Blue) diff --git a/buch/papers/ifs/images/Makefile b/buch/papers/ifs/images/Makefile new file mode 100644 index 0000000..c6d3fb5 --- /dev/null +++ b/buch/papers/ifs/images/Makefile @@ -0,0 +1,9 @@ +# +# Makefile +# +# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +# +chaosspiel.pdf: chaosspiel.tex \ + farnnotweight-eps-converted-to.pdf \ + farnrightwight-eps-converted-to.pdf + pdflatex chaosspiel.tex diff --git a/buch/papers/ifs/images/chaosspiel.tex b/buch/papers/ifs/images/chaosspiel.tex new file mode 100644 index 0000000..7c69ad3 --- /dev/null +++ b/buch/papers/ifs/images/chaosspiel.tex @@ -0,0 +1,37 @@ +% +% tikztemplate.tex -- template for standalon tikz images +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math} +\begin{document} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +% add image content here + +\begin{scope}[xshift=-3.6cm] +%\clip (-3.3,-3) rectangle (3.3,3); +\node at (0,0) { +\includegraphics[width=6.8cm]{farnnotweight-eps-converted-to.pdf} +}; +\node at (0.2,-5.7) {(a)}; +\end{scope} + +\begin{scope}[xshift=3.6cm] +%\clip (-3.3,-3) rectangle (3.3,3); +\node at (0,0) { +\includegraphics[width=6.8cm]{farnrightwight-eps-converted-to.pdf} +}; +\node at (0.2,-5.7) {(b)}; +\end{scope} + +\end{tikzpicture} +\end{document} + diff --git a/buch/papers/ifs/images/farnnotweight-eps-converted-to.pdf b/buch/papers/ifs/images/farnnotweight-eps-converted-to.pdf Binary files differindex 35bff32..f5e4093 100644 --- a/buch/papers/ifs/images/farnnotweight-eps-converted-to.pdf +++ b/buch/papers/ifs/images/farnnotweight-eps-converted-to.pdf diff --git a/buch/papers/ifs/images/farnrightwight-eps-converted-to.pdf b/buch/papers/ifs/images/farnrightwight-eps-converted-to.pdf Binary files differindex 3652e8f..fa69d77 100644 --- a/buch/papers/ifs/images/farnrightwight-eps-converted-to.pdf +++ b/buch/papers/ifs/images/farnrightwight-eps-converted-to.pdf diff --git a/buch/papers/ifs/teil1.tex b/buch/papers/ifs/teil1.tex index 7ce546a..caba120 100644 --- a/buch/papers/ifs/teil1.tex +++ b/buch/papers/ifs/teil1.tex @@ -15,7 +15,7 @@ Von einem Fraktal $F$ können wir folgende Eigenschaften erwarten: \item $F$ kann nicht mit der klassischen Geometrie beschrieben werden. \item Oftmals hat $F$ eine Form von Selbstähnlichkeit. Man spricht von einer selbstähnlichen Menge, wenn sich diese Menge überdecken lässt mit echten Teilmengen, die zur ganzen Menge ähnlich sind. - \item Die `fraktale Dimension´ ist grösser als die topologische Dimension + \item Die `fraktale Dimension' ist grösser als die topologische Dimension. \item Viele Fraktale lassen sich auf eine simple Art definieren. Es genügen zum Beispiel nur wenige Funktionen, welche rekursiv ausgeführt werden, um ein Fraktal zu definieren. \end{enumerate} \subsection{Koch Kurve @@ -64,7 +64,7 @@ berechnen. In jedem Schritt wird die Länge um den Faktor $\frac{4}{3}$ verlängert. Daraus resultiert, dass die Länge gegen $\infty$ divergiert. -Die Fläche der Kurve lässt sich folgendermassen berechnen +Die Fläche zwischen der Strecke von $O$ nach $(1,0)$ und der Kurve lässt sich folgendermassen berechnen \begin{align*} A_0 &= 0 \\ A_1 &= \left( \frac{a}{3}\right)^2 \frac{\sqrt{3}}{4} = a^2 \frac{\sqrt{3}}{36}\\ @@ -100,8 +100,8 @@ Ihre Ähnlichkeits-Dimension ist somit \begin{align*} D = - \frac{\log N }{\log \epsilon } = - \frac{\log 4 }{\log 1/3 } \approx 1.2619. \end{align*} -Wie wir nun sehen besitzt die Koch-Kurve alle oben beschriebenen Eigenschaften von Fraktalen. -Dies muss jedoch nicht bei allen Fraktalen der Fall sein. Sonst wäre die Frage nach einer 'richtigen' Definition einfach zu beantworten. +Wie wir nun sehen, besitzt die Koch-Kurve alle oben beschriebenen Eigenschaften von Fraktalen. +Dies muss jedoch nicht bei allen Fraktalen der Fall sein. Sonst wäre die Frage nach einer `richtigen' Definition einfach zu beantworten. \begin{figure} \centering \begin{tikzpicture} diff --git a/buch/papers/ifs/teil2.tex b/buch/papers/ifs/teil2.tex index 49c1cf3..d0110ed 100644 --- a/buch/papers/ifs/teil2.tex +++ b/buch/papers/ifs/teil2.tex @@ -8,7 +8,7 @@ \rhead{Teil 2} Wollen wir nun eine bestimmte Art anschauen, wie man Fraktale erzeugen kann. Im Beispiel auf Seite \pageref{ifs:trinagle} haben wir ein Dreieck aus 4 skalierten Kopien zusammengefügt. -Lässt man die Kopie im Zentrum des Dreiecks weg, entsteht die Grundlage des sogenannten Sierpinski-Dreieck, Abbildung \ref{ifs:sierpinski10}. +Lässt man die Kopie im Zentrum des Dreiecks weg, entsteht die Grundlage des sogenannten Sierpinski-Dreieck in Abbildung \ref{ifs:sierpinski10}. \begin{figure} \centering \includegraphics[width=0.5\textwidth]{papers/ifs/images/sierpinski} @@ -93,22 +93,22 @@ Man kann sogar noch einen Schritt weiter gehen, und sagen: Wenn wir die Funktion \label{ifs:sierpconst} \end{figure} Im Beispiel der Abbildung \ref{ifs:sierpconst} sehen wir, wie das Bild nach jeder Iteration dem Sierpinski-Dreieck ähnlicher wird. -Der `Abstand´ zum Original wird immer kleiner, und konvergiert gegen null. +Der `Abstand' zum Original wird immer kleiner, und konvergiert gegen null. \subsection{Iterierte Funktionensysteme \label{ifs:subsection:IteratedFunktionensysteme}} In diesem Abschnitt wollen wir die Erkenntnis, wie wir aus einer beliebigen Menge ein Sierpinski-Dreieck generieren können, verallgemeinern. -$S_1,\dots,S_n$ sind Kontraktionen auf der Menge $D \subset \mathbb{R}^n$. Es gilt +$S_1,\dots,S_n$ sind Kontraktionen auf einer Menge $D \subset \mathbb{R}^n$. Es gilt \begin{align} |S_i(x) - S_i(y)| \leq c_i|x - y| \end{align} für jedes i mit einem $c_i < 1$. -Der Banachsche Fixpunktsatz besagt, dass für solche Kontraktionen ein Eindeutiges $A$ existiert, für das $S_i(A) = A$ gilt. +Man kann zeigen, dass für solche Kontraktionen ein eindeutiges $A$ existiert, für das $S_i(A) = A$ gilt. Den Beweis kann man in \cite{ifs:Rousseau2012} nachlesen. -Hat man nicht nur eine sondern mehrere Kontraktionen, dann existiert eine eindeutige kompakte Menge $F$ für die gilt +Hat man nicht nur eine sondern mehrere Kontraktionen, dann existiert eine eindeutige kompakte Menge $F$, für die gilt \begin{equation} F = \bigcup\limits_{i = 1}^{m} S_i(F). \end{equation} @@ -117,12 +117,12 @@ Weiter definieren wir die Transformation S auf kompakte Mengen $E$ ohne die leer S(E) = \bigcup\limits_{i = 1}^m S_i(E). \label{ifs:transformation} \end{equation} -Wird diese Transformation Iterativ ausgeführt, das heisst $S^0(E) = E, S^k(E) = S(S^{k-1}(E))$, gilt +Wird diese Transformation iterativ ausgeführt, das heisst $S^0(E) = E, S^k(E) = S(S^{k-1}(E))$, gilt \begin{equation} F = \bigcap\limits_{k = 1}^{\infty} S^k(E). \label{ifs:ifsForm} \end{equation} -In Worte gefasst bedeutet das, dass jede Gruppe von Kontraktionen iterativ ausgeführt, gegen eine eindeutige Menge konvergiert. +In Worte gefasst bedeutet das, dass jede Gruppe von Kontraktionen iterativ ausgeführt gegen eine eindeutige Menge konvergiert. Diese Menge ist auch als Attraktor eines IFS bekannt. Der Beweis für die Existenz eines eindeutigen Attraktors ist in \cite{ifs:fractal-geometry} beschrieben. @@ -155,7 +155,7 @@ Die vier affinen Transformationen \begin{pmatrix} 0 \\ 1.6 - \end{pmatrix}\\ + \end{pmatrix},\\ & {S_3(x,y)} = \begin{pmatrix} @@ -188,7 +188,7 @@ Die vier affinen Transformationen \end{pmatrix},\\ \label{ifs:farnFormel} \end{align} -, welche für die Konstruktion des Farns benötigt werden sind in der Abbildung \ref{ifs:farncolor} farblich dargestellt. +welche für die Konstruktion des Farns benötigt werden, sind in der Abbildung \ref{ifs:farncolor} farblich dargestellt. Das gesamte Farnblatt ist in der schwarzen Box. Auf diese werden die Transformationen angewendet. $S_1$ erstellt den Stiel des Farnblattes (rot). @@ -198,12 +198,12 @@ Sie verkleinert und dreht das gesamte Bild und stellt es auf das Ende des Stiels $S_3$ bildet das gesamte Blatt auf das blaue Teilblatt unten links ab. $S_4$ spiegelt das Blatt und bildet es auf das magentafarbene Teilblatt ab. \subsection{Erzeugung eines Bildes zu einem IFS} -Es gibt zwei verschiedene Methoden um das Bild zu einem IFS zu erzeugen. +Es gibt zwei verschiedene Methoden, um das Bild zu einem IFS zu erzeugen. Die erste Methode ist wahrscheinlich die intuitivste. -Wir beginnen mit einem Startbild, zum Beispiel ein Schwarzes Quadrat, und bilden dieses mit den affinen Transformationen des IFS ab. -Das neue Bild, dass entsteht, ist die nächste Iterierte. +Wir beginnen mit einem Startbild, zum Beispiel ein schwarzes Quadrat, und bilden dieses mit den affinen Transformationen des IFS ab. +Das neue Bild, das entsteht, ist die nächste Iterierte. Dieses wird wieder mit den Transformationen abgebildet. -Wir wiederholen den letzten schritt, bis wir zufrieden mit der neusten Iterierten sind. +Wir wiederholen den letzten Schritt, bis wir zufrieden mit der neusten Iterierten sind. Diesen Vorgang haben wir beim Sierpinski-Dreieck in Abbildung \ref{ifs:sierpconst} gebraucht. In Abbildung \ref{ifs:sierpinski10} ist die zehnte Iterierte zu sehen. @@ -219,8 +219,8 @@ Es wird bei jedem Iterationsschritt nur eine Transformation $S_i$, welche zufäl Da, wie wir beim Barnsley-Farn gut sehen, nicht jede Transformation gleich viel des Bildes ausmacht, werden diese beim Chaosspiel gewichtet. Je mehr eine Transformation kontrahiert, desto weniger Punkte braucht es, um die resultierende Teilabbildung darzustellen. -Im Fall des Barnsley-Fern wird $S_1$ in $1\%$, $S_2$ in $85\%$ und $S_3$ und $S_4$ in $7\%$ der Iterationen ausgeführt. -Wir sehen auch in Abbildung \ref{ifs:farncolor} gut, dass der rote Stiel, $S_1$, einiges weniger Punkte braucht als der grüne Hauptteil des Blattes, $S_2$. +Im Fall des Barnsley-Farns wird $S_1$ in $1\%$, $S_2$ in $85\%$ und $S_3$ und $S_4$ in $7\%$ der Iterationen ausgeführt. +Wir sehen auch in Abbildung \ref{ifs:farncolor} gut, dass der rote Stiel, $S_1$, viel weniger Punkte braucht als der grüne Hauptteil des Blattes, $S_2$. In Abbildung \ref{ifs:farnNoWeight} wurden die vier gleich stark gewichtet. Man sieht, dass trotzt gleich vieler Iterationen wie in Abbildung \ref{ifs:farn}, der Farn nicht so gut abgebildet wird. @@ -248,12 +248,13 @@ In jeder Kopie des ganzen Farns fehlen die Punkte für dieses rechte untere Teil \begin{figure} \centering - \subfigure[]{ - \label{ifs:farnNoWeight} - \includegraphics[width=0.45\textwidth]{papers/ifs/images/farnnotweight}} - \subfigure[]{ - \label{ifs:farnrightWeight} - \includegraphics[width=0.45\textwidth]{papers/ifs/images/farnrightwight}} + \includegraphics{papers/ifs/images/chaosspiel.pdf} + %\subfigure[]{ + % \label{ifs:farnNoWeight} + % \includegraphics[width=0.45\textwidth]{papers/ifs/images/farnnotweight}} + %\subfigure[]{ + % \label{ifs:farnrightWeight} + % \includegraphics[width=0.45\textwidth]{papers/ifs/images/farnrightwight}} \caption{(a) Chaosspiel ohne Gewichtung (b) $S_4$ zu wenig gewichtet} \label{ifs:farnweight} \end{figure} diff --git a/buch/papers/ifs/teil3.tex b/buch/papers/ifs/teil3.tex index 1d39c6f..cebb664 100644 --- a/buch/papers/ifs/teil3.tex +++ b/buch/papers/ifs/teil3.tex @@ -8,12 +8,13 @@ \rhead{Fraktale Bildkomprimierung} Mit dem Prinzip dieser IFS ist es auch möglich, Bilder zu komprimieren. Diese Idee hatte der Mathematiker Michael Barnsley, welcher mit seinem Buch {\em Fractals Everywhere} einen wichtigen Beitrag zum Verständnis von Fraktalen geliefert hat. -Das Ziel ist es ein IFS zu finden, welches das Bild als Attraktor hat. +Das Ziel ist, ein IFS zu finden, welches das Bild als Attraktor hat. In diesem Unterkapitel wollen wir eine Methode dafür anschauen, wie sie in \cite{ifs:Rousseau2012} beschrieben ist. Es ist wohl nicht falsch zu sagen, dass Ähnlichkeiten zur gesamten Menge, wie wir sie zum Beispiel beim Barnsley Farn gesehen haben, bei Bilder aus dem Alltag eher selten anzutreffen sind. Ein IFS, wie wir es in \ref{ifs:subsection:IteratedFunktionensysteme} definiert haben, wird uns also nicht weiter helfen. -Anders sieht es mit Partitionierten IFS (PIFS) \cite{ifs:pifs} aus. +Anders sieht es mit partitionierten IFS (PIFS) \cite{ifs:pifs} aus. + In \ref{ifs:transformation} wurde definiert, dass die Kontraktionen $S_i$ bei IFS auf die gesamte Menge $E$ angewendet werden. Bei einem PIFS wird der Attraktor in disjunkte Teilmengen aufgeteilt. Für jede dieser Teilmengen $R_i$ braucht es dann eine grössere Teilmenge, welche mit einer affinen Transformation eine zu $R_i$ ähnliche Menge bildet. @@ -55,7 +56,7 @@ Zuerst brauchen wir die Transformation g_i \end{pmatrix} \end{align*} -um ein Element aus $D$ auf ein Element von $R$ Abzubilden. +um ein Element aus $D$ auf ein Element von $R$ abzubilden. Das bestimmen der besten Transformation kann man in drei Schritte aufteilen. \textbf{Schritt 1: }Wenn wir die Grauwerte ausser acht lassen, haben wir die affine Abbildung @@ -83,7 +84,7 @@ Wir sind auf folgende acht Abbildungen beschränkt: \item Drehung um 90, 180 oder 270 Grad. \item Spiegelung an der vertikalen, horizontalen und den Diagonalachsen. \end{itemize} -Da wir ein $2b \times 2b$ Feld auf ein $b \times b$ Feld abbilden möchten, müssen wir zuerst $G_j$ um $1/2$ skalieren. +Da wir ein $2b \times 2b$ Feld auf ein $b \times b$ Feld abbilden möchten, müssen wir zuerst $D_j$ um $1/2$ skalieren. Dies erreichen wir, indem wir alle disjunkten $2 \times 2$ Pixel Blöcke mit einem Pixel des Grautones deren Mittelwertes ersetzen. \textbf{Schritt 2: }Es muss nicht nur eine geometrische Abbildung, sondern auch eine Abbildung für die Grautöne gewählt werden. Letztere lässt sich mit den Parametern $s_i$ und $g_i$ beschrieben. @@ -136,7 +137,7 @@ Am Ende des Algorithmus haben wir für jeden Range-Block den zugehörigen Domain Mit den gefundenen Abbildungen lässt sich das Bild generieren. Wir beginnen wie schon im letzten Kapitel mit einer beliebigen Startmenge. In unserem Fall ist dieses ein Bild $f_0$ derselben Grösse. -Nun ersetzen wir jedes $R_i$ mit der Transformierten des zugehörigen Domain-Blocks $T(G_j)$. +Nun ersetzen wir jedes $R_i$ mit der Transformierten des zugehörigen Domain-Blocks $T(D_j)$. Dies wird verkürzt als Operator $W$ geschrieben. So erhalten wir ein neues Bild $f_1 = W(f_0)$. Dieses Vorgehen führen wir iteriert aus bis wir von $f_n = W(f_{n-1})$ zu $f_{n-1}$ kaum mehr einen Unterschied feststellen. Die Iteration hat nun ihren Attraktor, das Bild, erreicht. @@ -157,12 +158,12 @@ Wir verwenden dafür den oben beschriebenen Algorithmus, welcher uns für jeden Mit diesen lässt sich das Bild im Anschluss wieder Rekonstruieren. Die Range-Blöcke wurden $4\times4$ gewählt und die Domain dementsprechend $8\times8$. Um etwas Zeit bei der Komprimierung zu ersparen, wurden nur disjunkte Domain-Blöcke gebraucht. -Als erstes Beispiel wählen wir das 360$\times$360px Bild von Rapperswil in Abbildung \ref{ifs:original}. -Das Startbild ist ein mittelgraues 360$\times$360px Bild, Abbildung \ref{ifs:bild0}. +Als erstes Beispiel wählen wir das 360$\times$360 Pixel Bild von Rapperswil in Abbildung \ref{ifs:original}. +Das Startbild ist ein mittelgraues 360$\times$360 Pixel Bild, Abbildung \ref{ifs:bild0}. Es kann jedoch ein beliebiges Startbild sein. Nun lassen wir das PIFS laufen. Wie wir in Abbildung \ref{ifs:rappirecoa} sehen, ist schon nach der ersten Iteration das Bild schon erkennbar. -Nach der fünften Iteration , Abbildung \ref{ifs:rappirecoc} gibt es fast keinen Unterschied mehr zur letzten Iteration, wir können die Rekonstruktion beenden. +Nach der fünften Iteration, Abbildung \ref{ifs:rappirecoc} gibt es fast keinen Unterschied mehr zur letzten Iteration, wir können die Rekonstruktion beenden. \begin{figure} \centering \includegraphics[width=0.4\textwidth]{papers/ifs/images/original} diff --git a/buch/papers/multiplikation/code/MM b/buch/papers/multiplikation/code/MM Binary files differindex f07985f..d52dda4 100755 --- a/buch/papers/multiplikation/code/MM +++ b/buch/papers/multiplikation/code/MM 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..47bd6ab 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,8 +217,9 @@ 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=',') @@ -232,10 +239,10 @@ def plot_c_res(ave, num): 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 = 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] @@ -255,7 +262,7 @@ def plot_c_res(ave, num): 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(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) @@ -275,22 +282,22 @@ def plot_c_res(ave, num): # test%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% if __name__ == '__main__': - plot_c_res(1, 4096) + # 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) + t_np = test_perfomance(n) # C = strassen(A, B) # C_test = A@B 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 Binary files differindex 547d794..304015a 100644 --- a/buch/papers/multiplikation/code/c_meas_4096.pdf +++ b/buch/papers/multiplikation/code/c_meas_4096.pdf diff --git a/buch/papers/multiplikation/code/meas/MM.txt b/buch/papers/multiplikation/code/meas/MM.txt index 1a0cd5d..13b6312 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,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..c3ec7ec 100644 --- a/buch/papers/multiplikation/code/meas/blas.txt +++ b/buch/papers/multiplikation/code/meas/blas.txt @@ -2,11 +2,11 @@ 0.000000,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..69ea472 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.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..6e6208a 100644 --- a/buch/papers/multiplikation/code/meas/winograd.txt +++ b/buch/papers/multiplikation/code/meas/winograd.txt @@ -2,10 +2,11 @@ 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 Binary files differindex fd0a108..3312420 100644 --- a/buch/papers/multiplikation/code/meas_1024.pdf +++ b/buch/papers/multiplikation/code/meas_1024.pdf 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 Binary files differindex ed1ec63..c54648f 100644 --- a/buch/papers/multiplikation/code/meas_128.pdf +++ b/buch/papers/multiplikation/code/meas_128.pdf 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 Binary files differindex 5f049dc..2eb177b 100644 --- a/buch/papers/multiplikation/code/meas_256.pdf +++ b/buch/papers/multiplikation/code/meas_256.pdf 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 Binary files differindex 94c3731..b926095 100644 --- a/buch/papers/multiplikation/code/meas_32.pdf +++ b/buch/papers/multiplikation/code/meas_32.pdf 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 Binary files differnew file mode 100644 index 0000000..e889d17 --- /dev/null +++ b/buch/papers/multiplikation/code/meas_4096.pdf 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 Binary files differindex 3a90949..92af29b 100644 --- a/buch/papers/multiplikation/code/meas_64.pdf +++ b/buch/papers/multiplikation/code/meas_64.pdf 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..2d0583d 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 \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}
\ No newline at end of file diff --git a/buch/papers/multiplikation/images/bigo.pdf b/buch/papers/multiplikation/images/bigo.pdf Binary files differindex dfa2ba4..c29a891 100644 --- a/buch/papers/multiplikation/images/bigo.pdf +++ b/buch/papers/multiplikation/images/bigo.pdf diff --git a/buch/papers/multiplikation/images/bigo.tex b/buch/papers/multiplikation/images/bigo.tex index e3293e4..a415ccb 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, + xmode=log, ymode=log, + xmin=1e-0, xmax=5e1, + ymin=10e-1, ymax=1e7, + grid=both, + major grid style={black!50}, xlabel = $n$ (Data Input), ylabel = {$t$ (time)}, legend pos=north east, very thick, - ymax = 500, yticklabels=\empty, xticklabels=\empty, scale only axis=true, width=12cm, height=6cm, ] \addplot [ - domain= 1:20, + domain= 1:50, samples=100, color=red, ] {1}; \addlegendentry{$\mathcal{O}(1)$} \addplot [ - domain= 1:20, + domain= 1:50, samples=100, color=green, ] {x}; \addlegendentry{$\mathcal{O}(n)$} \addplot [ - domain= 1:20, + domain= 1:50, samples=100, color=blue, ] {x^2}; -\addlegendentry{$\mathcal{O}(n^2)$} +\addlegendentry{$\mathcal{O}\left(n^2\right)$} \addplot [ - domain= 1:10, + domain= 1:50, samples=100, color=purple, ] {x^3}; -\addlegendentry{$\mathcal{O}(n^3)$} +\addlegendentry{$\mathcal{O}\left(n^3\right)$} \addplot [ - domain= 1:10, + domain= 1:50, 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:50, samples=100, color=orange, ] -{log2(x)}; +{log2(x)+1}; \addlegendentry{$\mathcal{O}(\log n)$} \addplot [ - domain= 1:20, + domain= 1:50, 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 Binary files differnew file mode 100644 index 0000000..304015a --- /dev/null +++ b/buch/papers/multiplikation/images/c_meas_4096.pdf diff --git a/buch/papers/multiplikation/images/meas_1024.pdf b/buch/papers/multiplikation/images/meas_1024.pdf Binary files differnew file mode 100644 index 0000000..70c7ec1 --- /dev/null +++ b/buch/papers/multiplikation/images/meas_1024.pdf diff --git a/buch/papers/multiplikation/images/strassen.pdf b/buch/papers/multiplikation/images/strassen.pdf Binary files differindex 9899dcb..a30fdaa 100644 --- a/buch/papers/multiplikation/images/strassen.pdf +++ b/buch/papers/multiplikation/images/strassen.pdf 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..6f1486c 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{Matrix Multiplication} \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 produklt \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} \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 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 Matrix Multiplication} \setlength{\lineskip}{7pt} \label{multiplikation:alg:devide_mm} \begin{algorithmic} @@ -105,15 +105,11 @@ 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 Algortihmen. +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. @@ -122,20 +118,20 @@ In diesem Fall hat der \textit{Divide and Conquer} Ansatz zu keiner Verbesserung \subsection{Strassen's Algorithmus} -Strassen's Algorithmus \cite{multiplikation:strassen_1969} beschreibt die Matrizenmultiplikation mit einer Vielzahl von Additionen, Subtraktionen und Multiplikationen. -Die Grundlegenden Terme +Strassen's Algorithmus \cite{multiplikation:strassen_1969} beschreibt die Matrizenmultiplikation mit einer Vielzahl von Additionen, Subtraktionen und Multiplikationen von Blockmatrizen. +Die 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 Matrix Multiplication} \label{multiplikation:alg:strassen} \setlength{\lineskip}{7pt} \begin{algorithmic} @@ -190,7 +186,11 @@ gebraucht. \EndFunction \end{algorithmic} \end{algorithm} -Strassens's Methode wird in der Abbildung \ref{multiplikation:fig:strassen} grafisch dargestellt. +Strassen's 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} @@ -202,17 +202,15 @@ Die Funktion wird sieben mal rekursiv aufgerufen. Dies f\"uhrt 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} -Ein weiterer Ansatz lieferte Shmuel Winograd im Jahre 1968 \cite{multiplikation:winograd_1968}. -Er zeigte einen neuen Algorithmus f\"ur das +Einen weiteren Ansatz lieferte Shmuel Winograd im Jahre 1968 \cite{multiplikation:winograd_1968}. +Er beschrieb einen neuen Algorithmus f\"ur das \begin{equation} \langle x,y \rangle = \sum_{i=1}^{n}x_i y_i \end{equation} @@ -236,6 +234,7 @@ Das Skalarprodukt ist nun geben mit 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. + 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 +242,10 @@ 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. +Was im Vergleich zu den $mpn$ Multiplikation der Standardmethode nur die H\"alfte ist. +Die Implementation kann Algorithmus \ref{multiplikation:alg:winograd} entnommen werden. -\begin{algorithm}\caption{Winograd Matrix Multiplication} +\begin{algorithm}\footnotesize\caption{Winograd Matrix Multiplication} \setlength{\lineskip}{7pt} \label{multiplikation:alg:winograd} \begin{algorithmic} @@ -297,13 +296,170 @@ Die Implementation kann im Algorithmus \ref{multiplikation:alg:winograd} entnomm \end{algorithmic} \end{algorithm} -\subsection{Weitere Algorithmen} +\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)$ karakteristik + \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)$ karakteristik + \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)$ karakteristik + \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)} + +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. + -\textcolor{red}{TODO: BLAS} -\section{Implementation} +\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 Strassen's Matrizenmultiplikation + \item Winograd's Matrizenmultiplikation + \item \texttt{BLAS} Matrizenmultiplikation in \texttt{C} + \item \texttt{Numpy} Matrizenmultiplikation in \texttt{Python} +\end{itemize} + +Der Code kann im dazugehörigen \textit{GitHub} 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/c_meas_4096} + \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_1024} + \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. +Einen optimierten 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..cd5aaaa 100755 --- a/buch/papers/multiplikation/problemstellung.tex +++ b/buch/papers/multiplikation/problemstellung.tex @@ -6,24 +6,24 @@ \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. +Das Ziel dieses Papers ist, verschiedenen Algorithmen der Matrizenmultiplikation vorzustellen. +Gezielt werden auf Algorithmen, welche das Problem schneller als der Standard Algorithmus L\"osen eingegangen. \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$. +$f(x) \in \mathcal{O}(g(x))$ besagt, dass die Funktion $f$ nicht wesentlich schneller w\"achst als $g$ wenn $x \rightarrow \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. \begin{figure} \center @@ -33,11 +33,13 @@ In der Abbildung \ref{multiplikation:fig:bigo} k\"onnen die Verschiedenen Laufze \end{figure} \subsubsection{Beispiel Algorithmen} + +Folgend einige Beispiele von Algorithmen welche zu einer bestimmten Zeitkomplexit\"atsklasse zugeteilt werden k\"onnen. \paragraph{Beschr\"ankter Algorithmus} -Ein Beispiel eines Beschr\"ankter Verhalten $\mathcal{O}(1)$, kann im Algorithmus \ref{multiplikation:alg:b1} entnommen werden. +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. -\begin{algorithm}\caption{} +\begin{algorithm}\footnotesize\caption{} \label{multiplikation:alg:b1} \setlength{\lineskip}{7pt} \begin{algorithmic} @@ -47,9 +49,10 @@ Ein Beispiel eines Beschr\"ankter Verhalten $\mathcal{O}(1)$, kann im Algorithmu \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)$. +Konstanten werden nicht beachtet, der Algorithmus \ref{multiplikation:alg:b2} f\"uhrt ebenso zu $\mathcal{O}(1)$ und nicht zu $\mathcal{O}(2)$. + -\begin{algorithm}\caption{} +\begin{algorithm}\footnotesize\caption{} \label{multiplikation:alg:b2} \setlength{\lineskip}{7pt} \begin{algorithmic} @@ -63,13 +66,14 @@ Wobei Konstanten nicht beachtet werden, der Algorithmus \ref{multiplikation:alg: \paragraph{Linearer Algorithmus} -Folgender Algorithmus \ref{multiplikation:alg:l1} hat ein lineares $\mathcal{O}(n)$ Verhalten. +Folgender Algorithmus \ref{multiplikation:alg:l1} hat ein lineares Verhalten. +Die \texttt{for}-Schleife wird $n$-mal durchlaufen und f\"uhrt deshalb zu $\mathcal{O}(n)$. -\begin{algorithm}\caption{} +\begin{algorithm}\footnotesize\caption{} \setlength{\lineskip}{7pt} \begin{algorithmic} \label{multiplikation:alg:l1} - \Function{L}{$\mathbf{A}, \mathbf{B}$,n} + \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] $ @@ -83,9 +87,11 @@ Folgender Algorithmus \ref{multiplikation:alg:l1} hat ein lineares $\mathcal{O}( \paragraph{Quadratischer Algorithmus} -Folgender Algorithmus \ref{multiplikation:alg:q1} hat ein quadratisches $\mathcal{O}(n^2)$ Verhalten. +Folgender 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)$. + -\begin{algorithm}[H]\caption{} +\begin{algorithm}[H]\footnotesize\caption{} \label{multiplikation:alg:q1} \setlength{\lineskip}{7pt} \begin{algorithmic} 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} +} diff --git a/buch/papers/munkres/teil1.tex b/buch/papers/munkres/teil1.tex index 363dc06..3bec61d 100644 --- a/buch/papers/munkres/teil1.tex +++ b/buch/papers/munkres/teil1.tex @@ -13,10 +13,10 @@ Um dieses Problem in einer einfachen, händischen Art und Weise zu lösen wurde \subsection{Zuordnungsproblem an einem konkreten Beispiel \label{munkres:subsection:bonorum}} -Man hat den Fall, wo ein Bauunternehmer einen Bauingenieur beauftragt, eine optimale Transportroute für die Umplatzierung seiner Kräne zu eruieren. Das heisst, die Transportstrecke für die Umplatzierung seine Kräne +Als Beispiel betrachten wir den Fall, wo ein Bauunternehmer einen Bauingenieur beauftragt, eine optimale Transportroute für die Umplatzierung seiner Kräne zu eruieren. Das heisst, die Transportstrecke für die Umplatzierung seine Kräne soll möglichst klein werden. Die Frage lautet, wie sind die Kräne umzusetzen, damit deren Transportstrecke minimal wird? Bei der normalen Optimierung dürfen normalerweise beliebige reelle Werte $\mathbb{R}$ angenommen werden. -Beim Beispiel mit den Kräne gibt es aber ein Problem. Bei der Suche nach der optimalen Lösung darf nur die Methode der ganzzahligen Optimierung gewählt werden. Materialien kann man aufteilen, jedoch Maschinen nicht. Die Bauarbeiter auf der neuen Baustelle benötigen einen ganzen Kran und nicht nur einen halben Kran. Es muss immer ein ganzer Kran von A nach B oder gar kein Kran verschoben werden. Also 1 oder 0. +Beim Beispiel mit den Kräne gibt es aber ein Problem. Bei der Suche nach der optimalen Lösung darf nur die Methode der ganzzahligen Optimierung gewählt werden. Materialien kann man aufteilen, jedoch Maschinen nicht. Die Bauarbeiter auf der neuen Baustelle benötigen einen ganzen Kran und nicht nur einen halben Kran. Es muss immer ein ganzer Kran (Anzahl 1) von A nach B oder gar kein Kran (Anzahl 0) verschoben werden. Für solche Optimierungsprobleme für reelle Variablen sind verschiedene Verfahren entwickelt worden, die im Allgemeinen auch sehr effizient sind. Das reelle Problem ist also in einer einfachen Art und Weise lösbar. Doch das Problem bleibt, wie in der Illustration oben ersichtlich. Es kann mit ganzzahligen Punkten kein Optimum erzielt werden. Das Ziel ist es an das Optimum so nah wie möglich heranzukommen und dies ist eine vergleichsweise träge und langsame Angelegenheit. \begin{figure} @@ -34,31 +34,39 @@ In einem Zuordnungsproblem sind alle Angebots- und Bedarfsmengen gleich 1 \begin{equation} a_{i}=b_{j}=1 \end{equation} -Das Ziel ist es die Gesamtkosten zu minimieren. Mit Hilfe einer $n\times n$ Matrix $\mathbb{A}$ $\mathbb{\in}$ $\mathbb{R}^{n,n}$ kann der Faktor Kosten mit in die Rechnung eingebracht werden. -In der Zelle dieser Matrix sind $a_{i,j}$ die Wege dargestellt, die entstehen, wenn man z.B. einem Kran $i$ den Einsatzort $j$ zuordnet. - -\begin{figure} -\centering -\includegraphics[width=5cm]{papers/munkres/figures/MatrixA.png} -\caption{Darstellung einer Matrix $A$} -\label{munkres:Vr2} -\end{figure} +Das Ziel ist es die Gesamtkosten zu minimieren. Mit Hilfe einer $n\times n$ Matrix +\[ +A += +\begin{pmatrix} +a_{11}&a_{12}&\dots &a_{1n}\\ +a_{21}&a_{22}&\dots &a_{2n}\\ +\vdots&\vdots&\ddots&\vdots\\ +a_{n1}&a_{n2}&\dots &a_{nn} +\end{pmatrix} +\] + +$A$ $\mathbb{\in}$ $\mathbb{R}^{n,n}$ kann der Faktor Kosten mit in die Rechnung eingebracht werden. +In der Zelle dieser Matrix sind $a_{i,j}$ Zahlen dargestellt, welche den Weg in z.B. Kilometer beschreiben. +Sie entstehen, wenn man z.B. einem Kran $i$ den Einsatzort $j$ zuordnet. +Die oben ersichtliche Matrix $A$ besitzt Matrix-Elemente. Die Elemente einer Matrix vom Typ $(n,n)$ mit Namen $A$ sind $a_{ij}$ wobei $i$ = 1,..., $n$ ist und $j$ = 1,...,$n$. $a_{ij}$ ist der Eintrag in der $i$-ten Zeile und $j$-ten Spalte der Matrix . Zum Beispiel ist a21 das Element der 2. Zeile und 1. Spalte. $i$ wird auch der Zeilenindex, $j$ der Spaltenindex genannt. \subsection{Alternative Darstellungen des Zuordnungsproblems \label{munkres:subsection:bonorum}} -\begin{equation} -Netzwerk -\end{equation} -\begin{equation} -Matrix -\end{equation} -\begin{equation} -Bitpartiter Graph -\end{equation} +\subsubsection{Netzwerk} +Ein (Fluss- oder Transport-) Netzwerk (engl. network) ist ein zusammenhängender Graph, bei dem jede Kante einen Fluss aufnehmen kann und jede Kante eine Kapazität für den Fluss hat. Die Menge des Flusses auf einer Kante kann die Kapazität der Kante nicht überschreiten. Ein Fluss muss die Einschränkung erfüllen, dass die Menge des Flusses in einen Knoten gleich der Menge des Flusses aus ihm heraus ist. Ein Fluss-Netzwerk (engl. flow network) ist ein Netzwerk, dessen Kanten zusätzlich Kosten pro Mengeneinheit des Flusses zugeordnet sind. Typischerweise will man einen Fluss durch die Kanten bestimmen, der den Einschränkungen des Netzwerks genügt und dessen Gesamtkosten minimal sind. Im Bild 21.2 dargestellt sind in den eckigen Klammern links die externen Flüsse $[1]$ für jeden Arbeiter und in den eckigen Klammern rechts eine $[-1]$ für jede Tätigkeit. Die Kosten sind entlang der Kanten als Zahlen in Klammern dargestellt. +\subsubsection{Matrix} +Im Bild 21.3 ist eine typische $4\times 4$ Matrix dargestellt. Die Zeilen A1 bis A4 betreffen z.B. vier bestehende Maschinenlager eines Unternehmers. In den Spalten B1 bis B4 sind vier neue Baustellenorte zugewiesen. Die Zahlen in der Matrix bedeuten z.B. die Distanz in Kilometer von dem jeweiligen Lager zur jeweiligen Baustelle. +\subsubsection{Bitpartiter Graph} Ein bipartiter Graph ist ein mathematisches Modell für Beziehungen -zwischen den Elementen zweier Mengen. -Es eignet sich sehr gut zur Untersuchung von Zuordnungsproblemen. +zwischen den Elementen zweier Mengen. Es eignet sich sehr gut zur Untersuchung von Zuordnungsproblemen. Zwischen zwei Gruppen von Objekten wird hierbei eine eindeutige Zuordnung hergestellt. Der Graph ist in Abbildung 21.4 ersichtlich. +\begin{itemize} +\item 3 = Anzahl der Knoten aus Menge A. +\item 3 = Anzahl der Knoten aus Menge B. +\end{itemize} + + \begin{figure} \centering \includegraphics[width=5cm]{papers/munkres/figures/Netzwerkdarstellung} diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex index 0d2c86e..964444c 100644 --- a/buch/papers/munkres/teil3.tex +++ b/buch/papers/munkres/teil3.tex @@ -45,45 +45,44 @@ Die ungarische Methode kann in einem einfachen händischen Beispiel erläutert w \begin{enumerate} \item Pro Zeile eruiert man die kleinste Zahl. Diese kleinste Zahl wird bei -allen anderen Ziffern in der jeweiligen Zeile subtrahiert. Mit dieser Subtraktion zieht man die unvermeidbaren Kosten ab. +allen anderen Ziffern in der jeweiligen Zeile subtrahiert. Mit dieser Subtraktion zieht man die unvermeidbaren Kosten ab, die man hat, um eine Baustelle zu erreichen. -\item Auch in diesem Schritt werden die unvermeidbaren Kosten abgezogen. Man zieht die kleinste Zahl in jeder Spalte von allen Zahlen in der Spalte ab. +\item Auch in diesem Schritt werden die unvermeidbaren Weg-Kosten abgezogen. Man zieht die kleinste Zahl in jeder Spalte von allen Zahlen in der Spalte ab. \item Bei den nachfolgenden Schritten bleiben dann nur noch die Kosten übrig, die man hat, wenn man eine andere Zuordnung wählt. Hierbei sollen möglichst viele Nullen markiert werden, welche freistehend sind. (Freistehend bedeutet, sowohl in der jeweiligen Zeile und Spalte nur eine markierte Null zu haben) -\item Weiter werden die jeweiligen Zeilen eruiert, bei welchen keine markierte Null vorhanden sind. Diese kennzeichnet man. +\item Weiter werden die jeweiligen Zeilen eruiert, bei welchen keine markierte Null vorhanden sind. Diese kennzeichnet man mit einer blauen Fläche. -\item In der vorherigen Zeile die 0 eruieren und die Spalte ebenfalls -kennzeichnen (*2) +\item In der vorherigen, mit blauer Fläche markierten Zeile die 0 eruieren und dann die dazugehörige Spalte ebenfalls +blau markieren. -\item Im der selben Spalte die Markierte Null eruieren und die dazugehörige -Zeile kennzeichnen (*3) +\item Im der selben Spalte die markierte Null eruieren und die dazugehörige +Zeile ebenfalls blau kennzeichnen. -\item Alle Zeilen durchstreichen, welche KEINE Kennzeichnungen (*) haben +\item Alle Zeilen mit einem gelben Balken durchstreichen, welche KEINE blauen Markierungen haben. -\item Alle Spalten durchstreichen, welche EINE Kennzeichnung besitzt! (hier, *2) +\item Alle Spalten durchstreichen, welche eine Blaue Markierung besitzt! -\item Kleinste Ziffer auswählen, welche nicht schon durchgestrichen sind. -(Im Beispiel ist es die Zahl 1. (Egal welche 1) +\item In den übrigen Zahlen soll nun die kleinste Ziffer ausgewählt werden, welche nicht schon durchgestrichen sind. +(Im Beispiel ist es die Zahl 1 in rot markiert. (Bei diesem Schritt ist es egal, welche 1 man wählt) \item Die eruierte kleinste Ziffer, wird von den nicht durchgestrichenen Ziffern -subtrahiert. Danach muss die Matrix wieder komplettiert werden. (inkl. Unterstreichen) +subtrahiert. Danach muss die Matrix wieder komplettiert werden. (inkl. Unterstreichen der Nullen) -\item Jeweilige Zahlen eruieren, welche vorgängig doppelt durchgestrichen wurden. +\item Jeweilige Zahlen eruieren, welche vorgängig doppelt mit einer gelben Fläche durchgestrichen wurden. -\item Kleinste eruierte Ziffer von vorhin auf die zwei markierten Ziffern addieren. +\item Kleinste eruierte Ziffer aus Schritt 9, soll nun auf die zwei in rot markierten Ziffern aus Schritt 11 dazu addiert werden. -\item Es sollen wiederum von neuem möglichst viele Nullen markiert werden, -welche freistehend sind. In diesem Schritt werden nur die markierten Nullen betrachtet. +\item In diesem Schritt sollen wiederum von neuem möglichst viele Nullen markiert werden, +welche freistehend sind. Es werden nur die markierten Nullen betrachtet. -\item Aus allen markierten Nullen in eine eins umwandeln. +\item Alle markierten Nullen werden jetzt in eine 1 umgewandelt. -\item Die restlichen Ziffern, durch eine Null ersetzen. +\item Die restlichen Ziffern in der Matrix, exklusiv die einsen, sollen jetzt ignoriert und durch eine Null ersetzt werden. -\item Zu guter letzt soll überall wo eine 1 steht, in der Ausgangsmatrix die -dazugehörige Ziffer ausgewählt werden. Nach Einsetzen und Eruieren der Zahlen ergeben sich nach Summieren der Zahlen der minimalste Transportweg. Im erwähnten Beispiel sind es total 13 Kilometer. +\item Zu guter Letzt werden überall wo eine 1 steht, die Zahlen aus der Ausgangsmatrix eingefügt. Nach Einsetzen der Zahlen können die in rot markierten Zahlen aufsummiert werden. Es ergibt der minimalste Transportweg. Im erwähnten Beispiel sind es total 13 Kilometer. \end{enumerate} \begin{figure} @@ -108,4 +107,4 @@ dazugehörige Ziffer ausgewählt werden. Nach Einsetzen und Eruieren der Zahlen \includegraphics[width=3cm]{papers/munkres/figures/Ungarische_Methode_Beispiel_Zuw.png} \caption{Händisches Beispiel des Munkres Algorithmus, Zuweisung der Kräne } \label{munkres:Vr2} -\end{figure} Somit konnte danke der Ungarischen Methode sowohl der minimalste Transportweg als auch die optimalste Zuweisung der Kräne auf die neuen Standorte ermittelt werden.
\ No newline at end of file +\end{figure} Wie in Abbildung 21.6 ersichtlich, kann somit dank der Ungarischen Methode sowohl der minimalste Transportweg als auch die optimalste Zuweisung der Kräne auf die neuen Standorte ermittelt werden.
\ No newline at end of file diff --git a/buch/papers/punktgruppen/crystals.tex b/buch/papers/punktgruppen/crystals.tex index 42008e1..45761f8 100644 --- a/buch/papers/punktgruppen/crystals.tex +++ b/buch/papers/punktgruppen/crystals.tex @@ -18,7 +18,7 @@ Glücklicherweise ist das Innere eines Kristalles relativ einfach definiert. Ein zweidimensionales Beispiel eines solchen Muster ist Abbildung \ref{fig:punktgruppen:lattice}. Für die Überschaubarkeit haben wir ein simples Motiv eines einzelnen grauen Punktes dargestellt und betrachten dies nur in zwei Dimensionen. Die eingezeichneten Vektoren \(\vec{a}_1\) und \(\vec{a}_2\) sind die kleinstmöglichen Schritte im Raum bis sich das Kristallgitter wiederholt. -Wird ein beliebiger grauer Gitterpunkt in \ref{fig:punktgruppen:lattice} gewählt und um eine ganzzahlige Linearkombination von \(\vec{a}_1\) und \(\vec{a}_2\) verschoben, endet er zwangsweise auf einem Gitterpunkt, wenn nicht wieder am selben Ort. +Wird ein beliebiger grauer Gitterpunkt in Abbildung \ref{fig:punktgruppen:lattice} gewählt und um eine ganzzahlige Linearkombination von \(\vec{a}_1\) und \(\vec{a}_2\) verschoben, endet er zwangsweise auf einem Gitterpunkt, wenn nicht wieder am selben Ort. Im dreidimensionalen Raum können alle Gitterpunkte mit derselben Idee und einem zusätzlichen Vektor \(\vec{c}\) also \[ \vec{r} = n_1 \vec{a}_1 + n_2 \vec{a}_2 + n_3 \vec{a}_3 = \sum_i n_i \vec{a}_i @@ -39,7 +39,7 @@ können wir auch sagen, dass alle Verschiebungen um eine Linearkombination der Vektoren $\vec{a}_1$ , $\vec{a}_2$ und $\vec{a}_3$ erlaubt sind. Dabei sollte erwähnt werden, dass eine Translationssymmetrie nur in unendlich grossen Kristallgittern besteht. -\subsection{Limitierte Kristallsymmetrien} \label{txt:punktgruppen:Translationssymmetrie} +\subsection{Einschränkungen durch Kristallsymmetrien} \label{sec:punktgruppen:Translationssymmetrie} Die Translationssymmetrie ist wohl keine grosse Überraschung, wenn man die Abbildung \ref{fig:punktgruppen:lattice} betrachtet. Was nicht direkt ersichtlich ist, ist dass bei beliebigen Grundvektoren nicht beliebige Symmetrien erstellt werden können. Dies weil die Translationssymmetrie eines Kristalles weitere Symmetrien deutlich einschränkt. @@ -53,7 +53,7 @@ Dabei sollte erwähnt werden, dass eine Translationssymmetrie nur in unendlich g \label{fig:punktgruppen:rot-geometry} \end{figure} -\begin{satz} +\begin{satz} \label{thm:punktgruppen:crystal-restriction} Die Rotationssymmetrien eines Kristalls sind auf 2-fach, 3-fach, 4-fach und 6-fach beschränkt. Mit anderen Worten: Es sind nur Drehwinkel von 0\(^{\circ}\), @@ -87,7 +87,7 @@ Dabei sollte erwähnt werden, dass eine Translationssymmetrie nur in unendlich g Wir beginnen, indem wir die Länge der Verschiebung \(|\vec{Q}| = Q\) setzen und \(|\vec{Q}'| = Q'\). Aus Abbildung \ref{fig:punktgruppen:rot-geometry} ist ersichtlich, dass \(Q' = Q + 2x\). Da \(\vec{Q}\) eine Translation um ein Grundvektor ist , muss \(\vec{Q}'\) ein ganzes Vielfaches von \(\vec{Q}\) sein. - Demnach auch die Länge + Demnach ist auch die Länge \[ Q' = nQ = Q + 2x . \] @@ -95,12 +95,12 @@ Dabei sollte erwähnt werden, dass eine Translationssymmetrie nur in unendlich g \[ nQ = Q + 2Q\sin(\alpha - \pi/2) . \] - Wir können durch \(Q\) dividieren um unabhängig von der Läge des Grundvektors zu werden, was auch Sinn macht, + Wir können durch \(Q\), dividieren um unabhängig von der Läge des Grundvektors zu werden, was auch Sinn macht, da eine Skalierung eines Kristalles seine Symmetrieeigenschaften nicht tangiert. - Zusätzlich können wir den Sinusterm vereinfachen. + Zusätzlich können wir den Sinusterm vereinfachen. Somit wird \[ - n = 1 - 2\cos\alpha \quad\iff\quad - \alpha = \cos^{-1}\left(\frac{1-n}{2}\right) + n = 1 - 2\cos\alpha \quad\text{oder}\quad + \alpha = \cos^{-1}\left(\frac{1-n}{2}\right). \] Dies schränkt die möglichen Rotationssymmetrien auf \( @@ -144,10 +144,10 @@ Jede der 32 Kristallklassen auf der Abbildung \ref{fig:punktgruppen:kristallklas Er hat Untergruppen gebildet, welche als Grossbuchstaben in Abbildung \ref{fig:punktgruppen:kristallklassen} zu sehen sind. \begin{itemize} \item In Kristallen ist nur die Drehgruppe \(C\), Diedergruppe \(D\), Drehspiegelgruppe \(S\), Tetraedergruppe \(T\) und die Oktaedergruppe \(O\) zu finden. - Es gäbe auch die Ikosaedergruppe \(I\) und die Kugelgruppe \(K\), diese sind aber nicht kompatibel mit der Translationssymmetrie eines Kristalles und daher in der Kristallographie nicht relevant. - \item Dank Abschintt \ref{txt:punktgruppen:Translationssymmetrie} wissen wir, wieso in Abbildung \ref{fig:punktgruppen:kristallklassen} auf \(C\) nur ganz bestimmte Subskripte folgen. + Es gäbe auch die Ikosaedergruppe \(I\) und die Kugelgruppe \(K\), diese sind aber nach Satz \ref{thm:punktgruppen:crystal-restriction} nicht kompatibel mit der Translationssymmetrie eines Kristalles und daher in der Kristallographie nicht relevant. + \item Dank Abschintt \ref{sec:punktgruppen:Translationssymmetrie} wissen wir, wieso in Abbildung \ref{fig:punktgruppen:kristallklassen} auf \(C\) nur ganz bestimmte Subskripte folgen. Ist im Subskript eine Zahl \(n\) zu finden, steht dies für eine \(n\)-fache Symmetrie. - Daher darf \(C_5\) auf der Abbildung \ref{fig:punktgruppen:kristallklassen} nicht vorkommen, da \(360^\circ/5 = 72^\circ\) was nach Abschnitt \ref{txt:punktgruppen:Translationssymmetrie} keine mögliche Rotationssymmetrie eines Kristalles ist. + Daher darf \(C_5\) auf der Abbildung \ref{fig:punktgruppen:kristallklassen} nicht vorkommen, da \(360^\circ/5 = 72^\circ\) was nach Satz \ref{thm:punktgruppen:crystal-restriction} keine mögliche Rotationssymmetrie eines Kristalles ist. \item Sind im Subskript Buchstaben, definieren diese weitere Symmetrieeigenschaften der Klasse. Für die folgenden Betrachtungen müssen wir uns Abbildung \ref{fig:punktgruppen:kristallklassen} genauer ansehen. Dabei ist mit horizontal flach auf dem Papier gemeint. diff --git a/buch/papers/punktgruppen/intro.tex b/buch/papers/punktgruppen/intro.tex index 1293234..0a0cc86 100644 --- a/buch/papers/punktgruppen/intro.tex +++ b/buch/papers/punktgruppen/intro.tex @@ -1,26 +1,16 @@ \section{Einleitung} + Es gibt viele Möglichkeiten sich in Kristallen zu verlieren. -Auch wenn man nur die mathematischen Betrachtungsweisen berücksichtigt, -hat man noch viel zu viele Optionen sich mit Kristallen zu beschäftigen. +Auch wenn man nur die mathematischen Betrachtungsweisen berücksichtigt, hat man noch viel zu viele Optionen sich mit Kristallen zu beschäftigen. In diesem Kapitel wird daher der Fokus ``nur'' auf die Symmetrie gelegt. -Zu Beginn werden wir zeigen was eine Symmetrie ausmacht und -dass sie noch weit mehr in sich verbirgt als nur schön auszusehen. -Die vorgestellten Symmetrien sind äusserst gut geeignet, -um die Grundeigenschaften eines Kristalles zu beschreiben. -Mit etwas kniffligen geometrischen Überlegungen kann man zeigen, -was in der Welt der Kristallographie alles möglich ist oder nicht. -Einschränkungen in Kristallsymmetrien sind durchaus willkommen, -da dank ihnen sich die möglichen Kristallgitter in Grenzen halten -und sich kategorisieren lassen. -Kategorien sind nicht nur für einen besseren Überblick nützlich, -sondern kann man aus ihnen auch auf Physikalische Eigenschaften schliessen. +Zu Beginn werden wir zeigen, was eine Symmetrie ausmacht und dass sie noch weit mehr in sich verbirgt als nur schön auszusehen. +Die vorgestellten Symmetrien sind äusserst gut geeignet, um die Grundeigenschaften eines Kristalles zu beschreiben. +Mit etwas kniffligen geometrischen Überlegungen kann man zeigen, was in der Welt der Kristallographie alles möglich ist oder nicht. +Diese erlauben alle möglichen Kristalle nach ihren Symmetrien in erstaunlich wenige Klassen zu kategorisieren. +Kategorien sind nicht nur für einen besseren Überblick nützlich, sondern kann man aus ihnen auch auf physikalische Eigenschaften schliessen. Als spannendes Beispiel: Die Piezoelektrizität. -Piezoelektrizität ist kein weit verbreiteter Begriff, -jedoch beschreibt er ein Effekt, ohne welchen diverse Altagsgegenständen nicht besonders nützlich wären. +Piezoelektrizität beschreibt einen Effekt, ohne welchen diverse Altagsgegenständen nicht besonders nützlich wären. Wie zum Beispiel sorgt er in den allermeisten Feuerzeugen für die Zündung. -Hiermit ist hoffentlich ein Funken Interesse geweckt -um sich mit dem scheinbar trivialen Thema der Symmetrie auseinander zu setzten. - - +Hiermit ist hoffentlich ein Funken Interesse geweckt um sich mit dem scheinbar trivialen Thema der Symmetrie auseinander zu setzten. %% vim:linebreak breakindent showbreak=.. spell spelllang=de: diff --git a/buch/papers/punktgruppen/piezo.tex b/buch/papers/punktgruppen/piezo.tex index 6ed7ee9..334e4e7 100644 --- a/buch/papers/punktgruppen/piezo.tex +++ b/buch/papers/punktgruppen/piezo.tex @@ -1,5 +1,4 @@ \section{Piezoelektrizität} -%% TODO: improve this paragraph Die Piezoelektrizität ist die spannende Eigenschaft, dass gewisse Kristalle eine elektrische Spannung erzeugen, wenn mechanischer Druck auf sie ausgeübt wird. \begin{figure} @@ -10,13 +9,13 @@ Die Piezoelektrizität ist die spannende Eigenschaft, dass gewisse Kristalle ein \end{figure} \subsection{Polarisierung} + Piezoelektrizität basiert darauf, dass zwischen den Oberflächen des Kristalles ein Ladungsungleichgewicht entsteht (siehe Abbildung\ref{fig:punktgruppen:basicPiezo}). -Dieses Ungleichgewicht resultiert, -weil durch den mechanischen Druck auf der einen Oberfläche des Kristalles positive Ionen näher an die Oberfläche gelangen, -wärend auf der gegenüberliegenden Seite dasselbe mit negativen Ionen passiert. -Es besitzt jedoch nicht jeder Kristall eine atomare Struktur welche sich unter Druck genau so verformt. +Dieses Ungleichgewicht resultiert, weil durch den mechanischen Druck auf der einen Oberfläche des Kristalles positive Ionen näher an die Oberfläche gelangen, wärend auf der gegenüberliegenden Seite dasselbe mit negativen Ionen passiert. +Es besitzt jedoch nicht jeder Kristall eine atomare Struktur, welche sich unter Druck genau so verformt. Der Aufbau und somit auch die Symmetrie des Kristalles sind daher relevant für die Entstehung dieses Effektes. + \begin{figure} \centering \begin{tabular}{c |c} @@ -35,46 +34,43 @@ Der Aufbau und somit auch die Symmetrie des Kristalles sind daher relevant für \end{figure} \subsection{Atomarer Aufbau} + Die Polarisation entsteht an der Oberfläche eines Kristalles, die Erklärung dazu finden wir jedoch im atomaren Aufbau. Wir wollen dazu die verschiedenen Kristallstrukturen auf Abbildung \ref{fig:punktgruppen:atomPiezo} diskutieren. -In Abbildung \ref{fig:punktgruppen:atomPiezo} gilt für alle Strukturen, dass rote Kreise positive Ionen und blaue negative Ionen repräsentieren. -Struktur \subref{fig:punktgruppen:atoms-piezo} zeigt ein piezoelektrisches Material in Ruhe. -Struktur \subref{fig:punktgruppen:atoms-piezo-fv} ist dasselbe Kristallgitter, jedoch wird es senkrecht belastet. +In Abbildung \ref{fig:punktgruppen:atomPiezo} gilt für alle Strukturen, dass rote Kreise positive Ionen und blaue negative Ionen repräsentieren. +Struktur \subref{fig:punktgruppen:atoms-piezo} zeigt ein piezoelektrisches Material in Ruhe. +Struktur \subref{fig:punktgruppen:atoms-piezo-fv} ist dasselbe Kristallgitter, jedoch wird es senkrecht belastet. Eingezeichnet ist auch das elektrische Feld, welches entsteht, weil die Ladungsträger ganz links und rechts weiter auseinander gedrückt werden. -Als Hilfe zur Vorstellung kann man \subref{fig:punktgruppen:atoms-piezo-fv} zwischen zwei leitende Platten setzen, so wird ersichtlich, -dass mit wachsendem Druck eine negative Ladung an die rechte Platte gedrückt wird, während sich die positiven Ionen weiter entfernen. -\par +Als Hilfe zur Vorstellung kann man \subref{fig:punktgruppen:atoms-piezo-fv} zwischen zwei leitende Platten setzen, so wird ersichtlich, dass mit wachsendem Druck eine negative Ladung an die rechte Platte gedrückt wird, während sich die positiven Ionen weiter entfernen. + + Die Struktur \subref{fig:punktgruppen:atoms-grid} ist nicht piezoelektrisch. Dies wird ersichtlich, wenn man \subref{fig:punktgruppen:atoms-grid} unter Druck setzt und sich die Struktur zu \subref{fig:punktgruppen:atoms-grid-f} verformt. -Setzt man \subref{fig:punktgruppen:atoms-grid-f} gedanklich auch zwischen zwei leitende Platten, -scheint es als würden rechts mehr positive Ionen in die Platte gedrückt werden und links umgekehrt. +Setzt man \subref{fig:punktgruppen:atoms-grid-f} gedanklich auch zwischen zwei leitende Platten, scheint es, als würden rechts mehr positive Ionen in die Platte gedrückt werden und links umgekehrt. Dies ist aber nicht mehr der Fall, wenn sich die Struktur nach oben und unten periodisch wiederholt. -\par -Struktur \subref{fig:punktgruppen:atoms-piezo-fh} zeigt \subref{fig:punktgruppen:atoms-piezo} in unter horizontaler Belastung. -Was zwischen \subref{fig:punktgruppen:atoms-piezo-fv} und \subref{fig:punktgruppen:atoms-piezo-fh} zu beobachten ist, -ist, dass die entstandene Ladungsdifferenz orthogonal zu der angelegten Kraft entsteht, -im Gegensatz zu \subref{fig:punktgruppen:atoms-piezo-fh}. -Daraus kann man schliessen, dass \subref{fig:punktgruppen:atoms-piezo} keine Rotationssymmetrie von \(90^\circ\) besitzen kann, -weil die Eigenschaften der Struktur sich bei einer \(90^\circ\) Drehung ändern. -Das Fehlen dieser Rotationssymmetrie bestätigt sich auch wenn \subref{fig:punktgruppen:atoms-piezo} als Hexagon betrachtet wird. + + +Struktur \subref{fig:punktgruppen:atoms-piezo-fh} zeigt \subref{fig:punktgruppen:atoms-piezo} in unter horizontaler Belastung. +Was zwischen \subref{fig:punktgruppen:atoms-piezo-fv} und \subref{fig:punktgruppen:atoms-piezo-fh} zu beobachten ist, dass die entstandene Ladungsdifferenz orthogonal zu der angelegten Kraft entsteht, im Gegensatz zu \subref{fig:punktgruppen:atoms-piezo-fh}. +Daraus kann man schliessen, dass \subref{fig:punktgruppen:atoms-piezo} keine Rotationssymmetrie von \(90^\circ\) besitzen kann, weil die Eigenschaften der Struktur sich bei einer \(90^\circ\) Drehung ändern. +Das Fehlen dieser Rotationssymmetrie bestätigt sich auch wenn \subref{fig:punktgruppen:atoms-piezo} als Hexagon betrachtet wird. + \subsection{Punktsymmetrie} + Piezoelektrische Kristalle können nicht punktsymmetrisch sein. Kristallgitter, bei welchen eine Punktspiegelung eine symmetrische Operation ist, können keine piezoelektrische Kristalle bilden. -Auf Abbildung \ref{fig:punktgruppen:atomPiezo} ist bewusst \subref{fig:punktgruppen:atoms-piezo} ein nicht punktsymmetrischer Kristall -mit einem punktsymmetrischen \subref{fig:punktgruppen:atoms-grid} verglichen worden. -Als vereinfachte Erklärung kann man sich wieder das Bild eines Kristalles wie \subref{fig:punktgruppen:atoms-piezo} vor Augen führen, -welcher unter Druck auf der einen Seite negative und der anderen Seite positive Ionen an seine Oberfläche verdrängt. -Spiegelt man nun den Kristall um den Gitterpunkt in der Mitte des Kristalles, so würden die negativen Ionen auf den positiven auf der anderen Seite landen, -was der Definition einer Symmetrie deutlich widerspricht. +Auf Abbildung \ref{fig:punktgruppen:atomPiezo} ist bewusst \subref{fig:punktgruppen:atoms-piezo} ein nicht punktsymmetrischer Kristall mit einem punktsymmetrischen \subref{fig:punktgruppen:atoms-grid} verglichen worden. +Als vereinfachte Erklärung kann man sich wieder das Bild eines Kristalles wie \subref{fig:punktgruppen:atoms-piezo} vor Augen führen, welcher unter Druck auf der einen Seite negative und der anderen Seite positive Ionen an seine Oberfläche verdrängt. +Spiegelt man nun den Kristall um den Gitterpunkt in der Mitte des Kristalles, so würden die negativen Ionen auf den positiven auf der anderen Seite landen, was der Definition einer Symmetrie deutlich widerspricht. + \subsection{Vom Kristall zum Feuer} + Piezoelektrizität hat durchaus Nutzen im Alltag. -Feuerzeuge welche nicht auf dem Prinzip beruhen einen Zündstein abzuschleifen, -sonder ohne Verschleiss auf Knopfdruck einen Zündfunken erzeugen, basieren auf dem Prinzip der Piezoelektrizität. +Feuerzeuge welche nicht auf dem Prinzip beruhen einen Zündstein abzuschleifen, sondern ohne Verschleiss auf Knopfdruck einen Zündfunken erzeugen, basieren auf dem Prinzip der Piezoelektrizität. Drückt der Nutzende auf den Zündknopf, spannt sich eine Feder bis zu einer konfigurierten Spannung. -Wird vom Nutzenden fester zugedrückt entspannt sich die Feder schlagartig und beschleunigt mit der gespeicherten Energie ein Hammer, -welcher auf das Piezoelement aufschlägt. +Drückt der Nutzende stärker zu, entspannt sich die Feder schlagartig und beschleunigt mit der gespeicherten Energie ein Hammer, welcher auf das Piezoelement aufschlägt. Der augenblicklich hohe Druck sorgt an den Piezokontakten für eine eben so kurze aber hohe elektrische Spannung. Die Spannung reicht aus, um eine Funkenstrecke zu überwinden und so eine entflammbares Gas zu entzünden. Sollte der Leser eines Tages in die Situation geraten, in welcher er zwei verschiedene Kristalle vor sich hat und ein piezoelektrisches Feuerzeug bauen musst, wobei bekannt ist, dass der eine eine Punktsymmetrie aufweist, empfiehlt es sich, sich am anderen zu versuchen. diff --git a/buch/papers/punktgruppen/references.bib b/buch/papers/punktgruppen/references.bib index 05c803f..7928b22 100644 --- a/buch/papers/punktgruppen/references.bib +++ b/buch/papers/punktgruppen/references.bib @@ -26,7 +26,7 @@ @book{punktgruppen:lang-elt2, title = {Elektrotechnik 2}, - author = {Prof. Hans-Dieter Lang Ph.D}, + author = {Hans-Dieter Lang Ph.D}, publisher = {Fachhochschule Ostschweiz Rapperswil}, year = {2020}, month = {2}, @@ -45,7 +45,7 @@ @online{punktgruppen:restriction, title = {Structure of Materials: Allowed Rotational Symmetry in Crystals}, - author = {Prof. Silvija Gradecak-Garaj{,} Massachusetts Institute of Technology (MIT)}, + author = {Silvija Gradecak-Garaj{,} Massachusetts Institute of Technology (MIT)}, year = {2020}, month = {4}, day = {9}, diff --git a/buch/papers/punktgruppen/symmetry.tex b/buch/papers/punktgruppen/symmetry.tex index 2067663..51620a4 100644 --- a/buch/papers/punktgruppen/symmetry.tex +++ b/buch/papers/punktgruppen/symmetry.tex @@ -35,7 +35,7 @@ Fasst man die möglichen Symmetrien zusammen, entsteht eine Symmetriegruppe. Eine Gruppe benötigt ausserdem auch zwingend ein neutrales Element, welches wir mit \(\mathds{1}\) bezeichnen. Die Anwendung der neutralen Operation ist gleichbedeutend damit, alles unverändert zu lassen. -Weiterhin muss in einer Gruppe für jede Operation \(g\) auch eine inverse Operation \(g^{-1}\) vorkommen, die intuitiv rückgängig macht, was \(g\) getan hat. % intuitiv weglassen oder anstelle sinnbildlich +Weiterhin muss in einer Gruppe für jede Operation \(g\) auch eine inverse Operation \(g^{-1}\) vorkommen, die rückgängig macht, was \(g\) getan hat. Somit ist \(\mathds{1}\) auch äquivalent dazu, eine Operation und dann ihre Inverse anzuwenden. Die Definition der Symmetriegruppe ist mit der Kompositionsoperation gegeben, sie wird aber auch oft als Multiplikation geschrieben. Das liegt daran, dass in manchen Fällen die Zusammensetzung algebraisch durch eine Multiplikation berechnet wird. @@ -52,7 +52,7 @@ durch Verwendung von Potenzen \(r^n = r\circ r \circ \cdots r\circ r\) für eine Das bedeutet, dass \(G\) die Elemente \(a, aa, aaa, \ldots\) sowie \(a^{-1}, a^{-1}a^{-1}, \ldots\) und ein neutrales Element \(\mathds{1} = aa^{-1}\) enthält. \end{beispiel} \begin{beispiel} - Als anschaulicheres Beispiel, können wir eine zyklische Untergruppe des \(n\)-Gon formalisieren. + Als anschaulicheres Beispiel können wir eine zyklische Untergruppe des \(n\)-Gon formalisieren. Wir bezeichnen mit \(r\) eine Drehung im Gegenuhrzeigersinn von \(360^\circ/n\) um einen Punkt. Diese Definition reicht aus, um die gesamte Symmetriegruppe \[ @@ -69,7 +69,7 @@ komplexere Strukturen aufbauen. %@Naoki Are you ok with my grammar fixes I'm not 101% shore how to use the word Erzeugendensystem? \begin{definition}[Erzeugendensystem] - Jede disktrete Gruppe kann durch eines oder mehrere ihrer Elemente generiert werden. + Jede diskrete Gruppe kann durch eines oder mehrere ihrer Elemente generiert werden. Wir lassen \(g_1, g_2, \ldots, g_n\) erzeugenden Elemente einer Symmetriegruppe sein. Da es mehrere Erzeuger gibt, müssen auch die sogenannten Definitionsgleichungen gegeben werden, die die Multiplikationstabelle vollständig definieren. Die Gleichungen sind ebenfalls in den Klammern angegeben. @@ -87,7 +87,7 @@ komplexere Strukturen aufbauen. &= \left\{ \mathds{1}, r, \ldots, r^{n-1}, \sigma, \sigma r, \ldots, \sigma r^{n-1} \right\}. - \end{align*} + \end{align*} \qedhere \end{beispiel} Die Symmetrieoperationen, die wir bis jetzt besprochen haben, haben immer mindestens einen Punkt gehabt, der wieder auf sich selbst abgebildet wird. @@ -110,7 +110,7 @@ Um es formaler zu beschreiben, werden wir einige Begriffe einführen. Man sagt, dass der Homomorphismus \(f\) \(G\) in \(H\) transformiert. \end{definition} \begin{beispiel} - Die Rotationssymmetrie des Kreises \(C_\infty\), mit einem unendlichen Kontinuum von Werten \(\alpha \in \mathbb{R}\), entspricht perfekt dem komplexen Einheitskreis. + Die Rotationssymmetrie des Kreises \(C_\infty\), mit einem unendlichen Kontinuum von Werten \(\alpha \in \mathbb{R}\), entspricht genau dem komplexen Einheitskreis. Der Homomorphismus \(\phi: C_\infty \to \mathbb{C}\) ist durch die Eulersche Formel \(\phi(r) = e^{i\alpha}\) gegeben. \end{beispiel} diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex index 813b28a..c58e40c 100644 --- a/buch/papers/verkehr/section1.tex +++ b/buch/papers/verkehr/section1.tex @@ -54,13 +54,13 @@ Der Floyd-Warshall-Algorithmus sucht kürzeste Wege innerhalb eines Graphen. Er \subsection{Anwendung Floyd-Warshall-Algorithmus} %THEORIE... -In einem ersten Schritt wird eine Gewichtsmatrix $W$ mit den Matrixeinträgen $W[i, j]$ erstellt. +In einem ersten Schritt wird eine Gewichtsmatrix $W$ mit den Matrixeinträgen $W(i, j)$ erstellt. Der Algorithmus berechnet danach in einer Hauptschleife alle Knoten $k$ von 1 bis $n$. Dabei versucht er in jeder Iteration alle Wege von $i$ nach $j$ durch die Wege $(i, k)$ und $(k, j)$ zu verbessern. Falls dieser mögliche Umweg zu einer Verbesserung führt, wird der entsprechende Eintrag aktualisiert. Die aktuelle Gewichtung der Pfade wird mit -\begin{equation}d[i, j]=\min[d[i,j], d[i,k] + d[k,i]]\end{equation} +\begin{equation}d(i, j)=\min\{d(i,j), d(i,k) + d(k,i)\}\end{equation} ermittelt. |