From a4817013b542cd6aa1a0cd955806c82ac337dca6 Mon Sep 17 00:00:00 2001 From: Nunigan Date: Wed, 28 Jul 2021 22:27:27 +0200 Subject: added corrections from prof mueller --- buch/papers/multiplikation/einlteung.tex | 20 +++--- buch/papers/multiplikation/images/bigo.pdf | Bin 24288 -> 26821 bytes buch/papers/multiplikation/images/bigo.tex | 36 ++++++----- buch/papers/multiplikation/images/strassen.pdf | Bin 15850 -> 19970 bytes buch/papers/multiplikation/images/strassen.tex | 14 ++--- buch/papers/multiplikation/loesungsmethoden.tex | 80 ++++++++++++------------ buch/papers/multiplikation/problemstellung.tex | 27 ++++---- buch/papers/multiplikation/references.bib | 20 ++++++ 8 files changed, 113 insertions(+), 84 deletions(-) diff --git a/buch/papers/multiplikation/einlteung.tex b/buch/papers/multiplikation/einlteung.tex index bc4bfcf..ea71d91 100755 --- a/buch/papers/multiplikation/einlteung.tex +++ b/buch/papers/multiplikation/einlteung.tex @@ -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 index dfa2ba4..a2599fa 100644 Binary files a/buch/papers/multiplikation/images/bigo.pdf and b/buch/papers/multiplikation/images/bigo.pdf differ diff --git a/buch/papers/multiplikation/images/bigo.tex b/buch/papers/multiplikation/images/bigo.tex index e3293e4..71826f5 100644 --- a/buch/papers/multiplikation/images/bigo.tex +++ b/buch/papers/multiplikation/images/bigo.tex @@ -39,67 +39,73 @@ \begin{document} \begin{tikzpicture} + \begin{axis}[ - axis lines = left, + xmode=log, + ymode=log, + log ticks with fixed point, xlabel = $n$ (Data Input), ylabel = {$t$ (time)}, legend pos=north east, very thick, - ymax = 500, + grid=minor, + ymax = 100000, + ymin = 0.5, + xmin = 1, 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/strassen.pdf b/buch/papers/multiplikation/images/strassen.pdf index 9899dcb..a30fdaa 100644 Binary files a/buch/papers/multiplikation/images/strassen.pdf and b/buch/papers/multiplikation/images/strassen.pdf differ diff --git a/buch/papers/multiplikation/images/strassen.tex b/buch/papers/multiplikation/images/strassen.tex index 797772b..5cf39b4 100644 --- a/buch/papers/multiplikation/images/strassen.tex +++ b/buch/papers/multiplikation/images/strassen.tex @@ -81,13 +81,13 @@ \node at (-3,-10) {$C_{12}=$} ; \node at (-3,-5) {$C_{11}=$} ; - \node at (5,-2) {I}; - \node at (10,-2) {II}; - \node at (15,-2) {III}; - \node at (20,-2) {IV}; - \node at (25,-2) {V}; - \node at (30,-2) {VI}; - \node at (35,-2) {VII}; + \node at (5,-2) {P}; + \node at (10,-2) {Q}; + \node at (15,-2) {R}; + \node at (20,-2) {S}; + \node at (25,-2) {T}; + \node at (30,-2) {U}; + \node at (35,-2) {V}; } diff --git a/buch/papers/multiplikation/loesungsmethoden.tex b/buch/papers/multiplikation/loesungsmethoden.tex index 83be814..8bdbf2c 100755 --- a/buch/papers/multiplikation/loesungsmethoden.tex +++ b/buch/papers/multiplikation/loesungsmethoden.tex @@ -4,16 +4,16 @@ % (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. \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} \label{multiplikation:alg:smm} @@ -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} @@ -64,11 +66,9 @@ Die Matrizen $\mathbf{A}$ und $\mathbf{B}$ werden in jeweils vier Blockmatrizen \mathbf{C}_{11} & \mathbf{C}_{12}\\ \mathbf{C}_{21} & \mathbf{C}_{22} \end{bmatrix} -\end{equation} -aufgeteilt. -Die Berechnung +\end{equation}, \begin{equation} -\mathbf{C}_{ij} = \sum_{k=1}^n \mathbf{A}_{ik} \mathbf{B}_{kj} +\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. @@ -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 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,7 +140,7 @@ 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. +der Matrix $\mathbf{C}$ gebraucht. \begin{algorithm}\caption{Strassen Matrix Multiplication} \label{multiplikation:alg:strassen} \setlength{\lineskip}{7pt} @@ -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,14 @@ 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. \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 +233,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,8 +241,8 @@ 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} \setlength{\lineskip}{7pt} diff --git a/buch/papers/multiplikation/problemstellung.tex b/buch/papers/multiplikation/problemstellung.tex index b20a791..fed6a9f 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,9 +33,11 @@ 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\"atsklassen geh\"oren. \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{} \label{multiplikation:alg:b1} @@ -47,7 +49,7 @@ 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{} \label{multiplikation:alg:b2} @@ -63,13 +65,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 durchgef\"hrt und f\"uhrt deshalb zu $\mathcal{O}(n)$. \begin{algorithm}\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,7 +86,9 @@ 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 durchgef\"hrt und f\"uhrt deshalb zu $\mathcal{O}\left(n^2\right)$. + \begin{algorithm}[H]\caption{} \label{multiplikation:alg:q1} diff --git a/buch/papers/multiplikation/references.bib b/buch/papers/multiplikation/references.bib index 9d76e8e..63cb976 100755 --- a/buch/papers/multiplikation/references.bib +++ b/buch/papers/multiplikation/references.bib @@ -63,3 +63,23 @@ 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} +} + -- cgit v1.2.1 From 31b66acba16f525d41c42094601ade8afb3fd549 Mon Sep 17 00:00:00 2001 From: Nunigan Date: Sat, 31 Jul 2021 21:36:30 +0200 Subject: updare --- buch/papers/multiplikation/images/bigo.pdf | Bin 26821 -> 27173 bytes buch/papers/multiplikation/images/bigo.tex | 12 +++++------- buch/papers/multiplikation/loesungsmethoden.tex | 8 ++++---- buch/papers/multiplikation/problemstellung.tex | 6 +++--- 4 files changed, 12 insertions(+), 14 deletions(-) diff --git a/buch/papers/multiplikation/images/bigo.pdf b/buch/papers/multiplikation/images/bigo.pdf index a2599fa..c29a891 100644 Binary files a/buch/papers/multiplikation/images/bigo.pdf and b/buch/papers/multiplikation/images/bigo.pdf differ diff --git a/buch/papers/multiplikation/images/bigo.tex b/buch/papers/multiplikation/images/bigo.tex index 71826f5..a415ccb 100644 --- a/buch/papers/multiplikation/images/bigo.tex +++ b/buch/papers/multiplikation/images/bigo.tex @@ -41,17 +41,15 @@ \begin{tikzpicture} \begin{axis}[ - xmode=log, - ymode=log, - log ticks with fixed point, + 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, - grid=minor, - ymax = 100000, - ymin = 0.5, - xmin = 1, yticklabels=\empty, xticklabels=\empty, scale only axis=true, diff --git a/buch/papers/multiplikation/loesungsmethoden.tex b/buch/papers/multiplikation/loesungsmethoden.tex index 8bdbf2c..7ee0b6e 100755 --- a/buch/papers/multiplikation/loesungsmethoden.tex +++ b/buch/papers/multiplikation/loesungsmethoden.tex @@ -65,13 +65,13 @@ Das Matrizen produklt \begin{bmatrix} \mathbf{C}_{11} & \mathbf{C}_{12}\\ \mathbf{C}_{21} & \mathbf{C}_{22} -\end{bmatrix} -\end{equation}, +\end{bmatrix}, +\end{equation} \begin{equation} -\mathbf{C}_{ij} = \sum_{k=1}^n \mathbf{A}_{ik} \mathbf{B}_{kj}. +\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. diff --git a/buch/papers/multiplikation/problemstellung.tex b/buch/papers/multiplikation/problemstellung.tex index fed6a9f..2688f27 100755 --- a/buch/papers/multiplikation/problemstellung.tex +++ b/buch/papers/multiplikation/problemstellung.tex @@ -34,7 +34,7 @@ In der Abbildung \ref{multiplikation:fig:bigo} k\"onnen die verschiedenen Laufze \subsubsection{Beispiel Algorithmen} -Folgend einige Beispiele von Algorithmen welche zu einer bestimmten Zeitkomplexit\"atsklassen geh\"oren. +Folgend einige Beispiele von Algorithmen welche zu einer bestimmten Zeitkomplexit\"atsklasse zugeteilt werden kann. \paragraph{Beschr\"ankter Algorithmus} Ein Beispiel eines Beschr\"ankter Verhalten $\mathcal{O}(1)$, kann im Algorithmus \ref{multiplikation:alg:b1} entnommen werden. Da $a$ und $b$ Skalare sind, hat keine Gr\"osse $n$ einen einfluss auf die Laufzeit. @@ -66,7 +66,7 @@ Konstanten werden nicht beachtet, der Algorithmus \ref{multiplikation:alg:b2} f\ \paragraph{Linearer Algorithmus} Folgender Algorithmus \ref{multiplikation:alg:l1} hat ein lineares Verhalten. -Die \texttt{for}-Schleife wird $n$-mal durchgef\"hrt und f\"uhrt deshalb zu $\mathcal{O}(n)$. +Die \texttt{for}-Schleife wird $n$-mal durchlaufen und f\"uhrt deshalb zu $\mathcal{O}(n)$. \begin{algorithm}\caption{} \setlength{\lineskip}{7pt} @@ -87,7 +87,7 @@ Die \texttt{for}-Schleife wird $n$-mal durchgef\"hrt und f\"uhrt deshalb zu $\ma \paragraph{Quadratischer Algorithmus} Folgender Algorithmus \ref{multiplikation:alg:q1} hat ein quadratisches Verhalten. -Die beiden \texttt{for}-Schleifen werden jeweils $n$-mal durchgef\"hrt und f\"uhrt deshalb zu $\mathcal{O}\left(n^2\right)$. +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{} -- cgit v1.2.1 From 28efadd162ae3d48c04276da8e971155921d5812 Mon Sep 17 00:00:00 2001 From: Nunigan Date: Sun, 1 Aug 2021 22:50:04 +0200 Subject: update --- buch/papers/multiplikation/code/MM.py | 23 +++++----- buch/papers/multiplikation/code/meas_1024.pdf | Bin 17660 -> 17653 bytes buch/papers/multiplikation/code/meas_1024.txt | 10 ++--- buch/papers/multiplikation/code/meas_128.pdf | Bin 17961 -> 18120 bytes buch/papers/multiplikation/code/meas_128.txt | 10 ++--- buch/papers/multiplikation/code/meas_256.pdf | Bin 18067 -> 19428 bytes buch/papers/multiplikation/code/meas_256.txt | 10 ++--- buch/papers/multiplikation/code/meas_32.pdf | Bin 17078 -> 17964 bytes buch/papers/multiplikation/code/meas_32.txt | 10 ++--- buch/papers/multiplikation/code/meas_64.pdf | Bin 17678 -> 17747 bytes buch/papers/multiplikation/code/meas_64.txt | 10 ++--- buch/papers/multiplikation/loesungsmethoden.tex | 53 +++++++++++++++++++++++- buch/papers/multiplikation/main.tex | 22 ++++++++++ buch/papers/multiplikation/references.bib | 17 ++++++++ 14 files changed, 127 insertions(+), 38 deletions(-) diff --git a/buch/papers/multiplikation/code/MM.py b/buch/papers/multiplikation/code/MM.py index 626b82d..352771f 100644 --- a/buch/papers/multiplikation/code/MM.py +++ b/buch/papers/multiplikation/code/MM.py @@ -174,10 +174,11 @@ def test_perfomance(n): 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) @@ -198,7 +199,7 @@ 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") @@ -275,22 +276,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)) + n = np.logspace(1,8,8,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/meas_1024.pdf b/buch/papers/multiplikation/code/meas_1024.pdf index fd0a108..7b7a133 100644 Binary files a/buch/papers/multiplikation/code/meas_1024.pdf and b/buch/papers/multiplikation/code/meas_1024.pdf differ diff --git a/buch/papers/multiplikation/code/meas_1024.txt b/buch/papers/multiplikation/code/meas_1024.txt index c5ce619..ab507a2 100644 --- a/buch/papers/multiplikation/code/meas_1024.txt +++ b/buch/papers/multiplikation/code/meas_1024.txt @@ -1,6 +1,6 @@ 2.000000000000000000e+00 4.000000000000000000e+00 8.000000000000000000e+00 1.600000000000000000e+01 3.200000000000000000e+01 6.400000000000000000e+01 1.280000000000000000e+02 2.560000000000000000e+02 5.120000000000000000e+02 1.024000000000000000e+03 -1.502037048339843750e-05 6.628036499023437500e-05 4.780292510986328125e-04 2.713203430175781250e-03 2.115225791931152344e-02 1.758832931518554688e-01 1.338865518569946289e+00 1.009106445312500000e+01 8.192077994346618652e+01 7.835870332717895508e+02 -6.675720214843750000e-06 7.200241088867187500e-05 5.540847778320312500e-04 3.144979476928710938e-03 2.545046806335449219e-02 2.083067893981933594e-01 1.659256219863891602e+00 1.319160294532775879e+01 1.046767003536224365e+02 9.679818902015686035e+02 -1.668930053710937500e-05 1.628398895263671875e-04 7.648468017578125000e-04 4.426956176757812500e-03 2.922415733337402344e-02 1.800994873046875000e-01 1.286747694015502930e+00 9.412034273147583008e+00 6.263725924491882324e+01 4.427414393424987793e+02 -2.408027648925781250e-05 8.463859558105468750e-05 4.761219024658203125e-04 2.339839935302734375e-03 1.682758331298828125e-02 1.299476623535156250e-01 1.048770904541015625e+00 8.114667415618896484e+00 6.373566389083862305e+01 6.489995403289794922e+02 -1.573562622070312500e-05 7.152557373046875000e-06 7.152557373046875000e-06 2.074241638183593750e-05 5.388259887695312500e-05 6.365776062011718750e-05 3.257751464843750000e-03 1.396179199218750000e-03 3.274917602539062500e-03 2.186250686645507812e-02 +1.859664916992187500e-05 8.296966552734375000e-05 5.471706390380859375e-04 3.053665161132812500e-03 2.407431602478027344e-02 1.868948936462402344e-01 1.563691616058349609e+00 1.100623321533203125e+01 8.547679090499877930e+01 7.507572824954986572e+02 +8.106231689453125000e-06 9.012222290039062500e-05 7.290840148925781250e-04 4.970788955688476562e-03 2.718997001647949219e-02 2.652802467346191406e-01 1.777865171432495117e+00 1.327002429962158203e+01 1.053971357345581055e+02 8.473208103179931641e+02 +2.098083496093750000e-05 1.742839813232421875e-04 9.438991546630859375e-04 4.754066467285156250e-03 4.852557182312011719e-02 2.204136848449707031e-01 1.447179555892944336e+00 9.938656568527221680e+00 6.396102952957153320e+01 4.614939928054809570e+02 +2.789497375488281250e-05 1.049041748046875000e-04 5.528926849365234375e-04 4.555702209472656250e-03 1.871442794799804688e-02 1.530685424804687500e-01 1.194762229919433594e+00 8.298985958099365234e+00 6.836994743347167969e+01 5.373736469745635986e+02 +1.835823059082031250e-05 7.867813110351562500e-06 1.001358032226562500e-05 5.412101745605468750e-05 4.267692565917968750e-05 1.184940338134765625e-04 2.441406250000000000e-04 6.957054138183593750e-04 2.217054367065429688e-03 1.880884170532226562e-02 diff --git a/buch/papers/multiplikation/code/meas_128.pdf b/buch/papers/multiplikation/code/meas_128.pdf index ed1ec63..c54648f 100644 Binary files a/buch/papers/multiplikation/code/meas_128.pdf and b/buch/papers/multiplikation/code/meas_128.pdf differ diff --git a/buch/papers/multiplikation/code/meas_128.txt b/buch/papers/multiplikation/code/meas_128.txt index 976bbdf..f3a5beb 100644 --- a/buch/papers/multiplikation/code/meas_128.txt +++ b/buch/papers/multiplikation/code/meas_128.txt @@ -1,6 +1,6 @@ 2.000000000000000000e+00 4.000000000000000000e+00 8.000000000000000000e+00 1.600000000000000000e+01 3.200000000000000000e+01 6.400000000000000000e+01 1.280000000000000000e+02 -1.978874206542968750e-05 1.134872436523437500e-04 4.298686981201171875e-04 2.815246582031250000e-03 2.616596221923828125e-02 1.767718791961669922e-01 1.293319463729858398e+00 -6.675720214843750000e-06 1.251697540283203125e-04 4.818439483642578125e-04 3.490447998046875000e-03 2.465796470642089844e-02 2.014584541320800781e-01 1.630620479583740234e+00 -2.408027648925781250e-05 2.126693725585937500e-04 1.172780990600585938e-03 4.364490509033203125e-03 3.148293495178222656e-02 2.010228633880615234e-01 1.429297924041748047e+00 -2.932548522949218750e-05 1.466274261474609375e-04 4.270076751708984375e-04 2.837419509887695312e-03 1.723575592041015625e-02 1.308519840240478516e-01 1.015527009963989258e+00 -3.337860107421875000e-05 1.096725463867187500e-05 9.536743164062500000e-06 3.600120544433593750e-05 2.837181091308593750e-05 5.912780761718750000e-05 1.981019973754882812e-03 +1.239776611328125000e-05 5.507469177246093750e-05 3.888607025146484375e-04 2.762079238891601562e-03 2.097773551940917969e-02 1.672370433807373047e-01 1.410297393798828125e+00 +5.483627319335937500e-06 5.888938903808593750e-05 3.871917724609375000e-04 3.364324569702148438e-03 2.481031417846679688e-02 2.047052383422851562e-01 1.712310314178466797e+00 +1.358985900878906250e-05 1.189708709716796875e-04 6.430149078369140625e-04 5.586385726928710938e-03 3.101944923400878906e-02 1.874091625213623047e-01 1.327976465225219727e+00 +1.978874206542968750e-05 7.224082946777343750e-05 4.618167877197265625e-04 3.294944763183593750e-03 1.755571365356445312e-02 1.360688209533691406e-01 1.028253555297851562e+00 +1.215934753417968750e-05 5.722045898437500000e-06 2.074241638183593750e-05 4.339218139648437500e-05 2.813339233398437500e-05 5.292892456054687500e-05 1.921653747558593750e-04 diff --git a/buch/papers/multiplikation/code/meas_256.pdf b/buch/papers/multiplikation/code/meas_256.pdf index 5f049dc..4ca7102 100644 Binary files a/buch/papers/multiplikation/code/meas_256.pdf and b/buch/papers/multiplikation/code/meas_256.pdf differ diff --git a/buch/papers/multiplikation/code/meas_256.txt b/buch/papers/multiplikation/code/meas_256.txt index 15035c6..2ca4447 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.096725463867187500e-05 5.531311035156250000e-05 3.712177276611328125e-04 2.662897109985351562e-03 2.111244201660156250e-02 1.660463809967041016e-01 1.280746459960937500e+00 1.149287748336791992e+01 +5.483627319335937500e-06 5.745887756347656250e-05 4.055500030517578125e-04 3.203868865966796875e-03 2.503871917724609375e-02 2.148163318634033203e-01 1.655935287475585938e+00 1.472915720939636230e+01 +1.335144042968750000e-05 1.153945922851562500e-04 6.134510040283203125e-04 3.850460052490234375e-03 2.817606925964355469e-02 1.827111244201660156e-01 1.277473211288452148e+00 9.337273359298706055e+00 +1.907348632812500000e-05 9.274482727050781250e-05 3.526210784912109375e-04 2.403974533081054688e-03 1.725149154663085938e-02 1.314754486083984375e-01 1.121860027313232422e+00 8.884316682815551758e+00 +3.147125244140625000e-05 6.675720214843750000e-06 4.768371582031250000e-06 7.867813110351562500e-06 2.574920654296875000e-05 5.888938903808593750e-05 2.071857452392578125e-04 6.518363952636718750e-04 diff --git a/buch/papers/multiplikation/code/meas_32.pdf b/buch/papers/multiplikation/code/meas_32.pdf index 94c3731..b926095 100644 Binary files a/buch/papers/multiplikation/code/meas_32.pdf and b/buch/papers/multiplikation/code/meas_32.pdf differ diff --git a/buch/papers/multiplikation/code/meas_32.txt b/buch/papers/multiplikation/code/meas_32.txt index afdb6d5..0fdc18d 100644 --- a/buch/papers/multiplikation/code/meas_32.txt +++ b/buch/papers/multiplikation/code/meas_32.txt @@ -1,6 +1,6 @@ 2.000000000000000000e+00 4.000000000000000000e+00 8.000000000000000000e+00 1.600000000000000000e+01 3.200000000000000000e+01 -1.215934753417968750e-05 5.459785461425781250e-05 3.700256347656250000e-04 3.249406814575195312e-03 1.996850967407226562e-02 -4.529953002929687500e-06 5.650520324707031250e-05 4.577636718750000000e-04 4.029273986816406250e-03 2.444481849670410156e-02 -1.311302185058593750e-05 1.165866851806640625e-04 6.275177001953125000e-04 4.323244094848632812e-03 2.624726295471191406e-02 -1.835823059082031250e-05 6.890296936035156250e-05 3.914833068847656250e-04 2.423048019409179688e-03 1.761770248413085938e-02 -1.263618469238281250e-05 5.006790161132812500e-06 5.960464477539062500e-06 1.144409179687500000e-05 3.600120544433593750e-05 +1.239776611328125000e-05 5.507469177246093750e-05 3.802776336669921875e-04 2.795457839965820312e-03 2.073740959167480469e-02 +5.006790161132812500e-06 5.841255187988281250e-05 3.988742828369140625e-04 3.505229949951171875e-03 2.511668205261230469e-02 +1.335144042968750000e-05 1.149177551269531250e-04 6.387233734130859375e-04 4.088878631591796875e-03 2.969408035278320312e-02 +1.955032348632812500e-05 8.058547973632812500e-05 3.998279571533203125e-04 2.514839172363281250e-03 1.842117309570312500e-02 +1.215934753417968750e-05 8.583068847656250000e-06 6.675720214843750000e-06 2.694129943847656250e-05 2.789497375488281250e-05 diff --git a/buch/papers/multiplikation/code/meas_64.pdf b/buch/papers/multiplikation/code/meas_64.pdf index 3a90949..92af29b 100644 Binary files a/buch/papers/multiplikation/code/meas_64.pdf and b/buch/papers/multiplikation/code/meas_64.pdf differ diff --git a/buch/papers/multiplikation/code/meas_64.txt b/buch/papers/multiplikation/code/meas_64.txt index ae6ff9b..b4fc7a1 100644 --- a/buch/papers/multiplikation/code/meas_64.txt +++ b/buch/papers/multiplikation/code/meas_64.txt @@ -1,6 +1,6 @@ 2.000000000000000000e+00 4.000000000000000000e+00 8.000000000000000000e+00 1.600000000000000000e+01 3.200000000000000000e+01 6.400000000000000000e+01 -1.645088195800781250e-05 7.295608520507812500e-05 3.807544708251953125e-04 2.672195434570312500e-03 2.010774612426757812e-02 1.662156581878662109e-01 -7.390975952148437500e-06 7.843971252441406250e-05 4.265308380126953125e-04 3.107070922851562500e-03 2.457642555236816406e-02 2.122807502746582031e-01 -1.931190490722656250e-05 1.568794250488281250e-04 7.593631744384765625e-04 3.937005996704101562e-03 3.596329689025878906e-02 2.131938934326171875e-01 -2.622604370117187500e-05 9.226799011230468750e-05 3.504753112792968750e-04 2.469539642333984375e-03 1.652932167053222656e-02 1.281068325042724609e-01 -1.788139343261718750e-05 7.152557373046875000e-06 6.914138793945312500e-06 1.120567321777343750e-05 2.884864807128906250e-05 6.914138793945312500e-05 +2.145767211914062500e-05 6.175041198730468750e-05 4.422664642333984375e-04 3.235816955566406250e-03 2.289748191833496094e-02 1.855163574218750000e-01 +1.025199890136718750e-05 6.341934204101562500e-05 5.202293395996093750e-04 3.566026687622070312e-03 3.026723861694335938e-02 2.312932014465332031e-01 +2.384185791015625000e-05 1.807212829589843750e-04 6.821155548095703125e-04 4.796504974365234375e-03 2.968001365661621094e-02 2.291278839111328125e-01 +3.504753112792968750e-05 1.106262207031250000e-04 4.322528839111328125e-04 2.696514129638671875e-03 2.188420295715332031e-02 1.477701663970947266e-01 +3.218650817871093750e-05 1.144409179687500000e-05 7.390975952148437500e-06 4.625320434570312500e-05 3.814697265625000000e-05 5.435943603515625000e-05 diff --git a/buch/papers/multiplikation/loesungsmethoden.tex b/buch/papers/multiplikation/loesungsmethoden.tex index 7ee0b6e..0f6aa6b 100755 --- a/buch/papers/multiplikation/loesungsmethoden.tex +++ b/buch/papers/multiplikation/loesungsmethoden.tex @@ -295,9 +295,58 @@ Die Implementation kann Algorithmus \ref{multiplikation:alg:winograd} entnommen \end{algorithmic} \end{algorithm} -\subsection{Weitere Algorithmen} +\subsection{Basic Linear Algebra Subprograms (BLAS)} + +die gebr\"uchlichen Methode f\"ur die Anwendung einer optimierten Matrizenmultiplikation ist die Verwendung einer Subrutine 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 ausgek\"ugelter Verwedung der Speicher Architektur zur erheblichen Leistungoprimierung f\"uhren. + + +\subsubsection{General Matrix Multiplication (GEMM)} + +Die \textit{Double-GEMM} ist in \cite{multiplikation:DGEMM} 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 Implementaion 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} \rhead{Implementation} 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/references.bib b/buch/papers/multiplikation/references.bib index 63cb976..8815386 100755 --- a/buch/papers/multiplikation/references.bib +++ b/buch/papers/multiplikation/references.bib @@ -83,3 +83,20 @@ 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} +} -- cgit v1.2.1 From 11264adfdeba52738aa6ee7a96958936a20d4984 Mon Sep 17 00:00:00 2001 From: Nunigan Date: Mon, 2 Aug 2021 08:14:39 +0200 Subject: update --- buch/papers/multiplikation/loesungsmethoden.tex | 24 +++++++++++++++++++++--- 1 file changed, 21 insertions(+), 3 deletions(-) diff --git a/buch/papers/multiplikation/loesungsmethoden.tex b/buch/papers/multiplikation/loesungsmethoden.tex index 7ee0b6e..8e3369d 100755 --- a/buch/papers/multiplikation/loesungsmethoden.tex +++ b/buch/papers/multiplikation/loesungsmethoden.tex @@ -131,7 +131,7 @@ Die grundlegenden Terme \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 Bl\"ocke +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}} \\ @@ -187,10 +187,10 @@ der Matrix $\mathbf{C}$ gebraucht. \end{algorithmic} \end{algorithm} 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}$ . +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. +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} @@ -303,5 +303,23 @@ Die Implementation kann Algorithmus \ref{multiplikation:alg:winograd} entnommen \rhead{Implementation} \textcolor{red}{TODO: messresultate} +Folgende Algorithmen wurden jweiles 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{CBLAS} Matrizenmultiplikation in \texttt{C} + \item \texttt{Numpy} Matrizenmultiplikation in \texttt{Python} +\end{itemize} + \section{Fazit} \rhead{Fazit} + +Wie man in \textcolor{red}{hyperlink Messresultate} gesehen haben, sind die geziegten 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 keleine Mikrocontroller ohne Floatingpoint Recheneinhieten oder auch an \textit{Field Programmable Gate Arrays (FPGA's)}. +Sobland sehr grosse Matrizen multipliziert werden müssen und eine Addition in weniger Taktzyklen als eine Multiplikation durcheführt werden kann, können die gezeigten Algorithmen von Vorteil sein. -- cgit v1.2.1 From f96b0b2b66fe215a9e471eec44c58f4de11c7c0b Mon Sep 17 00:00:00 2001 From: Nunigan Date: Mon, 2 Aug 2021 22:49:09 +0200 Subject: update --- buch/papers/multiplikation/code/MM | Bin 26848 -> 26848 bytes buch/papers/multiplikation/code/MM.c | 2 +- buch/papers/multiplikation/code/MM.py | 23 ++--- buch/papers/multiplikation/code/c_matrix.h | 114 +++++++++++----------- buch/papers/multiplikation/code/c_meas_4096.pdf | Bin 15865 -> 17400 bytes buch/papers/multiplikation/code/meas/MM.txt | 20 ++-- buch/papers/multiplikation/code/meas/MM_dc.txt | 24 ++--- buch/papers/multiplikation/code/meas/blas.txt | 16 +-- buch/papers/multiplikation/code/meas/strassen.txt | 18 ++-- buch/papers/multiplikation/code/meas/winograd.txt | 15 +-- buch/papers/multiplikation/code/meas_1024.pdf | Bin 17653 -> 18813 bytes buch/papers/multiplikation/code/meas_256.pdf | Bin 19428 -> 17715 bytes buch/papers/multiplikation/code/meas_256.txt | 10 +- buch/papers/multiplikation/images/c_meas_4096.pdf | Bin 0 -> 15865 bytes buch/papers/multiplikation/images/meas_1024.pdf | Bin 0 -> 18813 bytes buch/papers/multiplikation/loesungsmethoden.tex | 16 +++ 16 files changed, 138 insertions(+), 120 deletions(-) create mode 100644 buch/papers/multiplikation/images/c_meas_4096.pdf create mode 100644 buch/papers/multiplikation/images/meas_1024.pdf diff --git a/buch/papers/multiplikation/code/MM b/buch/papers/multiplikation/code/MM index f07985f..d52dda4 100755 Binary files a/buch/papers/multiplikation/code/MM and b/buch/papers/multiplikation/code/MM differ diff --git a/buch/papers/multiplikation/code/MM.c b/buch/papers/multiplikation/code/MM.c index 04c4dab..a897d4f 100755 --- a/buch/papers/multiplikation/code/MM.c +++ b/buch/papers/multiplikation/code/MM.c @@ -31,7 +31,7 @@ int main() { run_algo(strassen, "strassen",0); run_algo(MM, "MM", 0); - // run_algo(winograd, "winograd", 0); + run_algo(winograd, "winograd", 0); run_algo_cblas(0); return 0; diff --git a/buch/papers/multiplikation/code/MM.py b/buch/papers/multiplikation/code/MM.py index 352771f..ee6f598 100644 --- a/buch/papers/multiplikation/code/MM.py +++ b/buch/papers/multiplikation/code/MM.py @@ -174,7 +174,7 @@ def test_perfomance(n): 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.xscale('log', base=2) plt.legend() plt.xlabel("n") plt.ylabel("time (s)") @@ -203,6 +203,7 @@ def plot(num): 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() @@ -213,7 +214,7 @@ def plot(num): 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=',') @@ -233,10 +234,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] @@ -256,7 +257,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) @@ -276,11 +277,11 @@ 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,8,8,base=2,dtype=(np.int)) + # plot(1024) + # n = np.logspace(1,10,10,base=2,dtype=(np.int)) # n = np.arange(1,50,2) # A = np.random.randint(-10, 6, (5,3)) # B = np.random.randint(-10, 6, (3,5)) @@ -291,7 +292,7 @@ if __name__ == '__main__': # print(C_test) # print(np.equal(C, C_test)) - t_np = test_perfomance(n) + # t_np = test_perfomance(n) # C = strassen(A, B) # C_test = A@B diff --git a/buch/papers/multiplikation/code/c_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 const int A0[][2] = { - {-15,68}, - {49,86} + {75,47}, + {-41,-24} }; const int B0[][2] = { - {33,73}, - {38,-76} + {-53,-95}, + {-93,30} }; const double dB0[][2] = { - {33,73}, - {38,-76} + {-53,-95}, + {-93,30} }; const double dA0[][2] = { - {-15,68}, - {49,86} + {75,47}, + {-41,-24} }; const int A1[][4] = { - {75,-38,-32,-65}, - {37,74,-31,29}, - {15,-62,-20,-20}, - {-31,-35,-89,47} + {47,11,-66,8}, + {36,98,39,82}, + {-32,12,40,-79}, + {61,-20,-85,-98} }; const int B1[][4] = { - {71,90,78,-98}, - {4,63,12,-47}, - {11,-44,75,-69}, - {95,-15,64,23} + {37,75,-53,9}, + {37,-33,-67,38}, + {70,39,-93,43}, + {43,41,23,-4} }; const double dB1[][4] = { - {71,90,78,-98}, - {4,63,12,-47}, - {11,-44,75,-69}, - {95,-15,64,23} + {37,75,-53,9}, + {37,-33,-67,38}, + {70,39,-93,43}, + {43,41,23,-4} }; const double dA1[][4] = { - {75,-38,-32,-65}, - {37,74,-31,29}, - {15,-62,-20,-20}, - {-31,-35,-89,47} + {47,11,-66,8}, + {36,98,39,82}, + {-32,12,40,-79}, + {61,-20,-85,-98} }; const int A2[][8] = { - {80,42,3,-16,6,55,87,16}, - {-99,-14,21,-1,-94,-56,91,10}, - {-47,-55,-59,62,12,-53,87,-65}, - {-60,94,-67,23,-62,33,-63,-72}, - {12,-75,16,21,22,-37,1,16}, - {-100,-99,82,-66,2,64,-13,44}, - {59,-100,-90,8,36,-24,18,88}, - {73,-58,75,-100,-19,-29,85,-19} + {-54,-87,87,69,52,-21,-86,55}, + {19,-75,-61,-50,-55,-23,66,-92}, + {-73,-67,-36,19,84,-11,24,46}, + {-98,62,-76,57,-100,6,-23,-51}, + {62,46,1,-64,42,-9,85,-12}, + {35,-59,-17,-47,78,86,-50,74}, + {-15,45,33,-59,-9,-81,49,96}, + {-57,22,-43,7,-30,-45,-5,13} }; const int B2[][8] = { - {-61,88,69,49,-53,47,73,45}, - {16,14,-88,-11,-67,-73,-20,43}, - {-60,-63,26,32,-29,18,-44,-69}, - {1,21,21,38,7,-100,-61,-76}, - {-90,95,-99,88,49,-80,27,-36}, - {24,-12,-47,-7,29,15,52,37}, - {-98,-76,29,76,-41,-75,97,79}, - {62,-90,-35,-14,-30,-42,-95,52} + {-71,-82,-80,-78,83,-97,48,-24}, + {15,75,15,-60,-63,-53,1,-50}, + {-84,63,67,-2,78,93,-13,95}, + {61,-26,-88,56,56,27,26,1}, + {2,54,21,36,9,-41,53,53}, + {85,-11,42,-51,-6,3,27,97}, + {10,-2,90,-76,-75,0,8,-37}, + {10,-64,47,-69,66,-50,89,-66} }; const double dB2[][8] = { - {-61,88,69,49,-53,47,73,45}, - {16,14,-88,-11,-67,-73,-20,43}, - {-60,-63,26,32,-29,18,-44,-69}, - {1,21,21,38,7,-100,-61,-76}, - {-90,95,-99,88,49,-80,27,-36}, - {24,-12,-47,-7,29,15,52,37}, - {-98,-76,29,76,-41,-75,97,79}, - {62,-90,-35,-14,-30,-42,-95,52} + {-71,-82,-80,-78,83,-97,48,-24}, + {15,75,15,-60,-63,-53,1,-50}, + {-84,63,67,-2,78,93,-13,95}, + {61,-26,-88,56,56,27,26,1}, + {2,54,21,36,9,-41,53,53}, + {85,-11,42,-51,-6,3,27,97}, + {10,-2,90,-76,-75,0,8,-37}, + {10,-64,47,-69,66,-50,89,-66} }; const double dA2[][8] = { - {80,42,3,-16,6,55,87,16}, - {-99,-14,21,-1,-94,-56,91,10}, - {-47,-55,-59,62,12,-53,87,-65}, - {-60,94,-67,23,-62,33,-63,-72}, - {12,-75,16,21,22,-37,1,16}, - {-100,-99,82,-66,2,64,-13,44}, - {59,-100,-90,8,36,-24,18,88}, - {73,-58,75,-100,-19,-29,85,-19} + {-54,-87,87,69,52,-21,-86,55}, + {19,-75,-61,-50,-55,-23,66,-92}, + {-73,-67,-36,19,84,-11,24,46}, + {-98,62,-76,57,-100,6,-23,-51}, + {62,46,1,-64,42,-9,85,-12}, + {35,-59,-17,-47,78,86,-50,74}, + {-15,45,33,-59,-9,-81,49,96}, + {-57,22,-43,7,-30,-45,-5,13} }; const int *Ap[3] = {(int*) A0,(int*) A1,(int*) A2}; const int *Bp[3] = {(int*) B0,(int*) B1,(int*) B2}; diff --git a/buch/papers/multiplikation/code/c_meas_4096.pdf b/buch/papers/multiplikation/code/c_meas_4096.pdf index 547d794..304015a 100644 Binary files a/buch/papers/multiplikation/code/c_meas_4096.pdf and b/buch/papers/multiplikation/code/c_meas_4096.pdf differ 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 index 7b7a133..70c7ec1 100644 Binary files a/buch/papers/multiplikation/code/meas_1024.pdf and b/buch/papers/multiplikation/code/meas_1024.pdf differ diff --git a/buch/papers/multiplikation/code/meas_256.pdf b/buch/papers/multiplikation/code/meas_256.pdf index 4ca7102..2eb177b 100644 Binary files a/buch/papers/multiplikation/code/meas_256.pdf and b/buch/papers/multiplikation/code/meas_256.pdf differ diff --git a/buch/papers/multiplikation/code/meas_256.txt b/buch/papers/multiplikation/code/meas_256.txt index 2ca4447..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.096725463867187500e-05 5.531311035156250000e-05 3.712177276611328125e-04 2.662897109985351562e-03 2.111244201660156250e-02 1.660463809967041016e-01 1.280746459960937500e+00 1.149287748336791992e+01 -5.483627319335937500e-06 5.745887756347656250e-05 4.055500030517578125e-04 3.203868865966796875e-03 2.503871917724609375e-02 2.148163318634033203e-01 1.655935287475585938e+00 1.472915720939636230e+01 -1.335144042968750000e-05 1.153945922851562500e-04 6.134510040283203125e-04 3.850460052490234375e-03 2.817606925964355469e-02 1.827111244201660156e-01 1.277473211288452148e+00 9.337273359298706055e+00 -1.907348632812500000e-05 9.274482727050781250e-05 3.526210784912109375e-04 2.403974533081054688e-03 1.725149154663085938e-02 1.314754486083984375e-01 1.121860027313232422e+00 8.884316682815551758e+00 -3.147125244140625000e-05 6.675720214843750000e-06 4.768371582031250000e-06 7.867813110351562500e-06 2.574920654296875000e-05 5.888938903808593750e-05 2.071857452392578125e-04 6.518363952636718750e-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/images/c_meas_4096.pdf b/buch/papers/multiplikation/images/c_meas_4096.pdf new file mode 100644 index 0000000..547d794 Binary files /dev/null and b/buch/papers/multiplikation/images/c_meas_4096.pdf differ diff --git a/buch/papers/multiplikation/images/meas_1024.pdf b/buch/papers/multiplikation/images/meas_1024.pdf new file mode 100644 index 0000000..70c7ec1 Binary files /dev/null and b/buch/papers/multiplikation/images/meas_1024.pdf differ diff --git a/buch/papers/multiplikation/loesungsmethoden.tex b/buch/papers/multiplikation/loesungsmethoden.tex index b25462a..8a95dd5 100755 --- a/buch/papers/multiplikation/loesungsmethoden.tex +++ b/buch/papers/multiplikation/loesungsmethoden.tex @@ -362,6 +362,22 @@ Folgende Algorithmen wurden jweiles in \texttt{C} und \texttt{Python} implementi \item \texttt{Numpy} Matrizenmultiplikation in \texttt{Python} \end{itemize} + +\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:c_meas_4096} +\end{figure} + \section{Fazit} \rhead{Fazit} -- cgit v1.2.1 From 6c9796cdf6fccfca8935f769781d94bfc4017dda Mon Sep 17 00:00:00 2001 From: Alain Date: Tue, 3 Aug 2021 17:08:02 +0200 Subject: corrections --- .../ifs/images/farnnotweight-eps-converted-to.pdf | Bin 0 -> 6124632 bytes buch/papers/ifs/teil1.tex | 6 ++--- buch/papers/ifs/teil2.tex | 30 ++++++++++----------- buch/papers/ifs/teil3.tex | 15 ++++++----- 4 files changed, 26 insertions(+), 25 deletions(-) create mode 100644 buch/papers/ifs/images/farnnotweight-eps-converted-to.pdf diff --git a/buch/papers/ifs/images/farnnotweight-eps-converted-to.pdf b/buch/papers/ifs/images/farnnotweight-eps-converted-to.pdf new file mode 100644 index 0000000..ee73d4d Binary files /dev/null and b/buch/papers/ifs/images/farnnotweight-eps-converted-to.pdf differ diff --git a/buch/papers/ifs/teil1.tex b/buch/papers/ifs/teil1.tex index 7ce546a..6c03f3b 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,7 +100,7 @@ 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. +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 diff --git a/buch/papers/ifs/teil2.tex b/buch/papers/ifs/teil2.tex index 49c1cf3..c468b73 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. diff --git a/buch/papers/ifs/teil3.tex b/buch/papers/ifs/teil3.tex index 1d39c6f..01a3ee2 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. @@ -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} -- cgit v1.2.1 From b15f2fc72a17bc489fe287bacc3d4d4a2450ece1 Mon Sep 17 00:00:00 2001 From: LordMcFungus Date: Tue, 3 Aug 2021 17:13:53 +0200 Subject: Update teil1.tex --- buch/papers/ifs/teil1.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/buch/papers/ifs/teil1.tex b/buch/papers/ifs/teil1.tex index 6c03f3b..caba120 100644 --- a/buch/papers/ifs/teil1.tex +++ b/buch/papers/ifs/teil1.tex @@ -101,7 +101,7 @@ Ihre Ähnlichkeits-Dimension ist somit 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. +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} -- cgit v1.2.1 From e5da5157fb61cdb006f3f50a2b3bd3b922644f1f Mon Sep 17 00:00:00 2001 From: Nunigan Date: Tue, 3 Aug 2021 22:08:02 +0200 Subject: update --- buch/papers/multiplikation/code/MM.py | 53 +++++++++------- buch/papers/multiplikation/code/meas_1024.pdf | Bin 18813 -> 18813 bytes buch/papers/multiplikation/code/meas_4096.pdf | Bin 0 -> 12952 bytes buch/papers/multiplikation/code/meas_4096.txt | 0 buch/papers/multiplikation/images/c_meas_4096.pdf | Bin 15865 -> 17400 bytes buch/papers/multiplikation/loesungsmethoden.tex | 73 +++++++++++++++++++++- 6 files changed, 101 insertions(+), 25 deletions(-) create mode 100644 buch/papers/multiplikation/code/meas_4096.pdf create mode 100644 buch/papers/multiplikation/code/meas_4096.txt diff --git a/buch/papers/multiplikation/code/MM.py b/buch/papers/multiplikation/code/MM.py index ee6f598..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,10 +173,10 @@ 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() @@ -182,10 +186,10 @@ def test_perfomance(n): 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): @@ -213,6 +217,7 @@ 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=',') blas = np.loadtxt("meas/blas.txt", delimiter=',') @@ -277,11 +282,11 @@ def plot_c_res(ave, num): # test%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% if __name__ == '__main__': - plot_c_res(1, 4096) + # plot_c_res(1, 4096) - # plot(1024) - # 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, 6, (5,3)) # B = np.random.randint(-10, 6, (3,5)) @@ -292,7 +297,7 @@ if __name__ == '__main__': # print(C_test) # print(np.equal(C, C_test)) - # t_np = test_perfomance(n) + t_np = test_perfomance(n) # C = strassen(A, B) # C_test = A@B diff --git a/buch/papers/multiplikation/code/meas_1024.pdf b/buch/papers/multiplikation/code/meas_1024.pdf index 70c7ec1..3312420 100644 Binary files a/buch/papers/multiplikation/code/meas_1024.pdf and b/buch/papers/multiplikation/code/meas_1024.pdf differ diff --git a/buch/papers/multiplikation/code/meas_4096.pdf b/buch/papers/multiplikation/code/meas_4096.pdf new file mode 100644 index 0000000..e889d17 Binary files /dev/null and b/buch/papers/multiplikation/code/meas_4096.pdf differ diff --git a/buch/papers/multiplikation/code/meas_4096.txt b/buch/papers/multiplikation/code/meas_4096.txt new file mode 100644 index 0000000..e69de29 diff --git a/buch/papers/multiplikation/images/c_meas_4096.pdf b/buch/papers/multiplikation/images/c_meas_4096.pdf index 547d794..304015a 100644 Binary files a/buch/papers/multiplikation/images/c_meas_4096.pdf and b/buch/papers/multiplikation/images/c_meas_4096.pdf differ diff --git a/buch/papers/multiplikation/loesungsmethoden.tex b/buch/papers/multiplikation/loesungsmethoden.tex index 8a95dd5..780cbf3 100755 --- a/buch/papers/multiplikation/loesungsmethoden.tex +++ b/buch/papers/multiplikation/loesungsmethoden.tex @@ -358,10 +358,81 @@ Folgende Algorithmen wurden jweiles in \texttt{C} und \texttt{Python} implementi \item \textit{Devide and Conquer} Matrizenmultiplikation \item Strassen's Matrizenmultiplikation \item Winograd's Matrizenmultiplikation - \item \texttt{CBLAS} Matrizenmultiplikation in \texttt{C} + \item \texttt{BLAS} Matrizenmultiplikation in \texttt{C} \item \texttt{Numpy} Matrizenmultiplikation in \texttt{Python} \end{itemize} +Der Code kann im dazugeh\"orgien \textit{GitHub} Repository gefunden werden. + +\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 -- cgit v1.2.1 From 24a24cb7f6cb0a85bc136bbdb11ad52b7d7917f0 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20K=C3=BChne?= Date: Wed, 4 Aug 2021 10:27:27 +0200 Subject: neue version --- buch/papers/munkres/teil1.tex | 29 ++++++++++++++++++++++------- buch/papers/munkres/teil3.tex | 4 ++-- 2 files changed, 24 insertions(+), 9 deletions(-) diff --git a/buch/papers/munkres/teil1.tex b/buch/papers/munkres/teil1.tex index 363dc06..07489e3 100644 --- a/buch/papers/munkres/teil1.tex +++ b/buch/papers/munkres/teil1.tex @@ -35,30 +35,45 @@ In einem Zuordnungsproblem sind alle Angebots- und Bedarfsmengen gleich 1 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. +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. \begin{figure} -\centering -\includegraphics[width=5cm]{papers/munkres/figures/MatrixA.png} +\[ +A += +\begin{pmatrix} +a_{11}&a_{12}&\dots &a_{1m}\\ +a_{21}&a_{22}&\dots &a_{2m}\\ +\vdots&\vdots&\ddots&\vdots\\ +a_{n1}&a_{n2}&\dots &a_{nm} +\end{pmatrix} +\] \caption{Darstellung einer Matrix $A$} -\label{munkres:Vr2} \end{figure} - +Eine Matrix, wie hier in Abbildung 21.2 ersichtlich, ist ein rechteckiges Schema, dessen Elemente üblicherweise Zahlen, aber auch andere mathematische Elemente wie Variablen oder Funktionen sein können. Sie besteht aus $n$ Zeilen und $m$ Spalten. D.h. die Elemente einer Matrix vom Typ $(n,m)$ mit Namen $A$ sind $a_{ij}$ wobei $i$ = 1,..., $m$ 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} +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.3 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. \begin{equation} Matrix \end{equation} +Im Bild 21.4 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. \begin{equation} Bitpartiter Graph \end{equation} 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. +\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..d2e8174 100644 --- a/buch/papers/munkres/teil3.tex +++ b/buch/papers/munkres/teil3.tex @@ -45,9 +45,9 @@ 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 -- cgit v1.2.1 From 960fdcf227a9de8bf5919c56b88e05a0abd0ec0a Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Wed, 4 Aug 2021 13:51:52 +0200 Subject: Klammern vereinheitlicht --- buch/papers/verkehr/section1.tex | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex index 6ac86ad..075649e 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. -- cgit v1.2.1 From 420405209148acf4bf074369f516d5e73c2b13b1 Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Wed, 4 Aug 2021 13:56:09 +0200 Subject: =?UTF-8?q?Zeilenumbr=C3=BCche?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- buch/papers/verkehr/section1.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex index 6ac86ad..813b28a 100644 --- a/buch/papers/verkehr/section1.tex +++ b/buch/papers/verkehr/section1.tex @@ -68,7 +68,7 @@ ermittelt. \section{PageRank-Algorithmus} Der PageRank-Algorithmus wurde von den Gründern von Google, Larry Page und Sergey Brin im Jahr 1996 entwickelt und zum Patent angemeldet. Zwei Jahre später gründeten sie ihr Unternehmen Google Inc. Beim PageRank-Algorithmus handelt es sich nicht um einen Suchalgorithmus, stattdessen werden Knoten aufgrund der Vernetzung des vorliegenden Graphen bewertet. -Verwendet wird er beispielsweise um die Verlinkungsstruktur verschiedener Websites des World Wide Web anhand ihrer Struktur zu bewerten und relevante Suchergebnisse zu ermittteln. Der PageRank wird umso höher, je mehr hochwertige Links auf eine Webseite verweisen und je höher die Gewichtung einer Webseite ist, desto grösser ist der Effekt.\\ +Verwendet wird er beispielsweise um die Verlinkungsstruktur verschiedener Websites des World Wide Web anhand ihrer Struktur zu bewerten und relevante Suchergebnisse zu ermittteln. Der PageRank wird umso höher, je mehr hochwertige Links auf eine Webseite verweisen und je höher die Gewichtung einer Webseite ist, desto grösser ist der Effekt. Dabei handelt es sich um einen iterativen Prozess. Ausgegangen wird von der Adjazenz-Matrix $A$, für welche folgendes gilt: \begin{equation} -- cgit v1.2.1 From 062f9b9a2984a3e8cec05adaf5cc9cf83da131e0 Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Wed, 4 Aug 2021 13:59:52 +0200 Subject: =?UTF-8?q?Formel=20mit=20"cases"=20einger=C3=BCckt?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- buch/papers/verkehr/section1.tex | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex index 6ac86ad..4991950 100644 --- a/buch/papers/verkehr/section1.tex +++ b/buch/papers/verkehr/section1.tex @@ -72,10 +72,10 @@ Verwendet wird er beispielsweise um die Verlinkungsstruktur verschiedener Websit Dabei handelt es sich um einen iterativen Prozess. Ausgegangen wird von der Adjazenz-Matrix $A$, für welche folgendes gilt: \begin{equation} -A_{i,j}=\left\{ \begin{matrix} -1 & \text{Kante von $j$ nach $i$} \\ 0 & \text{keine Kante von $j$ nach $i$} -\end{matrix} - \right. +A_{i,j} = \begin{cases} +1&\quad\text{Kante von $j$ nach $i$}\\ +0&\quad\text{keine Kante von $j$ nach $i$} +\end{cases} \label{verkehr:Adja} \end{equation} -- cgit v1.2.1 From 87779c4a725f04e31ba27e88dbfd8f639d51bed8 Mon Sep 17 00:00:00 2001 From: Pascal Schmid <81317360+paschost@users.noreply.github.com> Date: Wed, 4 Aug 2021 14:24:55 +0200 Subject: Anpassung Formel - Korrektur Formel-Syntax - Integration in Satz --- buch/papers/verkehr/section1.tex | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex index 6ac86ad..6c5817d 100644 --- a/buch/papers/verkehr/section1.tex +++ b/buch/papers/verkehr/section1.tex @@ -86,8 +86,8 @@ Grundsätzlich setzt sich der PageRank Algorithmus mit der Fragestellung auseina Für ungerichtete Graphen mit $n$ Knoten gilt \begin{equation}A_{i,j}=A_{j,i}\end{equation} und weiter \begin{equation}A_{i,i}=0\quad\forall i\in \left\{1\dots n\right\}\end{equation} Beim PageRank-Algorithmus wird eine abgewandelte Form der Adjazenz-Matrix verwendet. -Dabei werden die Matrix-Einträge spaltenweise durch die jeweilige Spaltensumme geteilt: -\( P_{i,j}=\frac{A_{i,j}}{\sum_{i=1}^{n}A_{i,j}} \) +Dabei werden die Matrix-Einträge spaltenweise durch die jeweilige Spaltensumme geteilt, so entsteht die Link-Matrix +\[ P_{i,j}=\frac{A_{i,j}}{\sum_{k=1}^{n}A_{k,j}} \] Anschliessend multipliziert man diese Matrix $P$ mit einem Spaltenvektor $\Vec{r_0}$ mit $n$ Einträgen, für welchen gilt: \( \Vec{r_0}(i) = \frac{1}{n} \quad\forall i\in \left\{1\dots n\right\} \) Dieser Vektor stellt ein neutrales Ranking dar. Alle Knoten werden gleich gewichtet. -- cgit v1.2.1 From 1663dd03e22b2ee65a8050f5eb5433c7580028b5 Mon Sep 17 00:00:00 2001 From: Nunigan Date: Wed, 4 Aug 2021 16:14:15 +0200 Subject: update multiplikation --- buch/papers/multiplikation/einlteung.tex | 2 +- buch/papers/multiplikation/loesungsmethoden.tex | 50 +++++++++++++------------ buch/papers/multiplikation/problemstellung.tex | 11 +++--- 3 files changed, 34 insertions(+), 29 deletions(-) diff --git a/buch/papers/multiplikation/einlteung.tex b/buch/papers/multiplikation/einlteung.tex index ea71d91..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 diff --git a/buch/papers/multiplikation/loesungsmethoden.tex b/buch/papers/multiplikation/loesungsmethoden.tex index 780cbf3..6f1486c 100755 --- a/buch/papers/multiplikation/loesungsmethoden.tex +++ b/buch/papers/multiplikation/loesungsmethoden.tex @@ -7,7 +7,7 @@ \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} @@ -15,7 +15,7 @@ Die Standardmethode kann im Algorithmus \ref{multiplikation:alg:smm} entnommen w Hierf\"ur wurde die Gleichung \eqref{multiplikation:eq:MM} direkt implementiert. Die \texttt{for i} Schleife iteriert \"uber alle Zeilen der $\mathbf{A}$ Matrix, die \texttt{for j} Schleife iteriert \"uber alle Spalten der $\mathbf{B}$ Matrix und die \texttt{for k} Schleife iteriert \"uber alle Eintr\"age dieser Zeilen bzw. Spalten. -\begin{algorithm}\caption{Matrix Multiplication} +\begin{algorithm}\footnotesize\caption{Matrix Multiplication} \label{multiplikation:alg:smm} \setlength{\lineskip}{7pt} \begin{algorithmic}[1] @@ -76,7 +76,7 @@ ist identisch zu der Gleichung \eqref{multiplikation:eq:MM}, f\"ur die Multiplik Der Algorithmus \ref{multiplikation:alg:devide_mm} zeigt den \textit{Divide and Conquer} Ansatz, Der Grundstruktur dieser Methode besteht aus dem rekursiven Aufruf der Funktion mit den erzeugten Blockmatrizen. Der rekursive Aufruf wird bis zu der Gr\"osse der Matrizen von $N = 2 \times 2$ durchgef\"uhrt. -\begin{algorithm}\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} @@ -106,7 +106,7 @@ Der rekursive Aufruf wird bis zu der Gr\"osse der Matrizen von $N = 2 \times 2$ \end{algorithm} Die Laufzeit dieser rekursiven Funktion kann mit dem \textit{Master Theorem} \cite{multiplikation:master_theorem} berechnet werden. Das \textit{Master Theorem} bestimmt die Zeitkomplexit\"at von rekursiven Algortihmen. -Ohne auf dieses vertieft einzugehen, bestimmt die Anzahl rekursiver Aufrufe der Funktion die Laufzeit. +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) = 8 \cdot \mathcal{T}\left (\frac{n}{2}\right ) + n^2 = \mathcal{O}(n^{\log_2 8}) = \mathcal{O}\left (n^{3} \right ) @@ -141,7 +141,7 @@ aus $\mathbf{A}$ und $\mathbf{B}$, werden f\"ur die Berechnung der Bl\"ocke \end{split} \end{equation} der Matrix $\mathbf{C}$ gebraucht. -\begin{algorithm}\caption{Strassen Matrix Multiplication} +\begin{algorithm}\footnotesize\caption{Strassen Matrix Multiplication} \label{multiplikation:alg:strassen} \setlength{\lineskip}{7pt} \begin{algorithmic} @@ -205,6 +205,7 @@ Dies f\"uhrt zu einer Laufzeit von 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 Standardmethode. +Man beachte, dass die Anzahl von Additionen und Subtraktionen gr\"osser und die Anzahl der Multiplikationen kleiner wurde. \subsection{Winograd's Algorithmus} @@ -244,7 +245,7 @@ Wenn $m,p,n$ gross werden, dominiert der Term $\frac{mpn}{2}$ und es werden $\fr 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,7 +298,7 @@ Die Implementation kann Algorithmus \ref{multiplikation:alg:winograd} entnommen \subsection{Basic Linear Algebra Subprograms (BLAS)} -die gebr\"uchlichen Methode f\"ur die Anwendung einer optimierten Matrizenmultiplikation ist die Verwendung einer Subrutine aus den \textit{Basic Linear Algebra Subprograms (BLAS)} \cite{multiplikation: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. @@ -320,12 +321,12 @@ Die meisten Numerischen Bibliotheken von High-Level Skriptsprachen wie \texttt{M \end{itemize} \end{itemize} -Die \textit{BLAS} sind auf die modernen Computer Prozessoren optimiert und k\"onnen dank einer ausgek\"ugelter Verwedung der Speicher Architektur zur erheblichen Leistungoprimierung f\"uhren. +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} ist in \cite{multiplikation:DGEMM} definiert als: +Die \textit{Double-GEMM} \cite{multiplikation:DGEMM} ist definiert als: \textit{DGEMM performs one of the matrix-matrix operations} $$ @@ -339,20 +340,19 @@ $$ an m by k matrix, op( B ) a k by n matrix and C an m by n matrix. } -Die Implementaion 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. +%Die Implementation von $\alpha\mathbf{A}\mathbf{B} + \beta \mathbf{C} = \mathbf{C}$, wobei $\alpha = 1.0$ und $\beta = 0.0$ in der \texttt{C}-Version von \textit{BLAS}, ist als +%\begin{lstlisting}[style=multiplikationC] +%cblas_dgemm(CblasRowMajor, CblasNoTrans, CblasNoTrans, +% m, n, k, 1, A, m , B, k, 0, C, m); +%\end{lstlisting} +%definiert. -\section{Implementation} +\section{Implementation}\label{multiplikation:section:Implementation} \rhead{Implementation} -\textcolor{red}{TODO: messresultate} -Folgende Algorithmen wurden jweiles in \texttt{C} und \texttt{Python} implementiert. +Folgende Algorithmen wurden jeweils in \texttt{C} und \texttt{Python} implementiert. \begin{itemize} \item Standard Matrizenmultiplikation \item \textit{Devide and Conquer} Matrizenmultiplikation @@ -362,7 +362,11 @@ Folgende Algorithmen wurden jweiles in \texttt{C} und \texttt{Python} implementi \item \texttt{Numpy} Matrizenmultiplikation in \texttt{Python} \end{itemize} -Der Code kann im dazugeh\"orgien \textit{GitHub} Repository gefunden werden. +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} @@ -446,16 +450,16 @@ Der Code kann im dazugeh\"orgien \textit{GitHub} Repository gefunden werden. \center \includegraphics[width=\linewidth]{papers/multiplikation/images/meas_1024} \caption{Messresultate mit der Programmiersprache \texttt{Python}} - \label{multiplikation:fig:c_meas_4096} + \label{multiplikation:fig:python} \end{figure} \section{Fazit} \rhead{Fazit} -Wie man in \textcolor{red}{hyperlink Messresultate} gesehen haben, sind die geziegten Algorithmen, trotz den theoretisch geringeren Zeitkomplexitäten, den Implementationen der numerischen Bibliotheken klar unterlegen. +Wie man im Abschnitt\ref{multiplikation:section:Implementation} sehen kann, sind die gezeigten Algorithmen, trotz den theoretisch geringeren Zeitkomplexitäten, den Implementationen der numerischen Bibliotheken klar unterlegen. 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 keleine Mikrocontroller ohne Floatingpoint Recheneinhieten oder auch an \textit{Field Programmable Gate Arrays (FPGA's)}. -Sobland sehr grosse Matrizen multipliziert werden müssen und eine Addition in weniger Taktzyklen als eine Multiplikation durcheführt werden kann, können die gezeigten Algorithmen von Vorteil sein. +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/problemstellung.tex b/buch/papers/multiplikation/problemstellung.tex index 2688f27..cd5aaaa 100755 --- a/buch/papers/multiplikation/problemstellung.tex +++ b/buch/papers/multiplikation/problemstellung.tex @@ -34,12 +34,12 @@ In der Abbildung \ref{multiplikation:fig:bigo} k\"onnen die verschiedenen Laufze \subsubsection{Beispiel Algorithmen} -Folgend einige Beispiele von Algorithmen welche zu einer bestimmten Zeitkomplexit\"atsklasse zugeteilt werden kann. +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. 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} @@ -51,7 +51,8 @@ Ein Beispiel eines Beschr\"ankter Verhalten $\mathcal{O}(1)$, kann im Algorithmu 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} @@ -68,7 +69,7 @@ Konstanten werden nicht beachtet, der Algorithmus \ref{multiplikation:alg:b2} f\ 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} @@ -90,7 +91,7 @@ Folgender Algorithmus \ref{multiplikation:alg:q1} hat ein quadratisches Verhalte 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} -- cgit v1.2.1 From 100898f1bdf1f00e3f8ba8ddb68703bcbed1e77e Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Wed, 4 Aug 2021 20:24:32 +0200 Subject: add new image stuff --- buch/papers/clifford/3d/Makefile | 13 +++ buch/papers/clifford/3d/common.inc | 206 +++++++++++++++++++++++++++++++++++++ buch/papers/clifford/3d/dq.pov | 25 +++++ 3 files changed, 244 insertions(+) create mode 100644 buch/papers/clifford/3d/Makefile create mode 100644 buch/papers/clifford/3d/common.inc create mode 100644 buch/papers/clifford/3d/dq.pov diff --git a/buch/papers/clifford/3d/Makefile b/buch/papers/clifford/3d/Makefile new file mode 100644 index 0000000..e6a9be3 --- /dev/null +++ b/buch/papers/clifford/3d/Makefile @@ -0,0 +1,13 @@ +# +# Makefile +# +# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +# +all: dq.jpg + +dq.png: dq.pov common.inc + povray +A0.1 +W1920 +H1080 -Odq.png dq.pov + +dq.jpg: dq.png + convert dq.png -density 300 -units PixelsPerInch dq.jpg + diff --git a/buch/papers/clifford/3d/common.inc b/buch/papers/clifford/3d/common.inc new file mode 100644 index 0000000..4bc2e7d --- /dev/null +++ b/buch/papers/clifford/3d/common.inc @@ -0,0 +1,206 @@ +// +// 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.04; + +camera { + location <40, 10, 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 to with thickness with +// color +// +#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) + +mesh { + #declare N = 100; + #declare phi = 0; + #declare phimax = 1.8 * pi; + #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) + +#declare e1 = vnormalize(fromdirection); +#declare e2 = -vnormalize(vcross(axis, fromdirection)); +#declare e3 = vnormalize(axis); + +#declare r1 = 0.4 * r; +#declare r2 = r; + +circlearrow0(e1, e2, e3, r1, r2) + +box { + center - r * (e1 + e2) - 0.021 * e3, center + r * (e1 + e2) + 0.021 * e3 + pigment { + color rgb<0.6,0.6,1> + } +} + +cone { + center + 0.02101 * e3, r, center + 2 * r * e3, 0 + pigment { + color rgbt<0.6,0.6,1,0.8> + } +} + +cylinder { + center, center + 2 * r * e3, 0.04*0.2 + pigment { + color rgb<1.0,0.6,0.6> + } +} + +#end + diff --git a/buch/papers/clifford/3d/dq.pov b/buch/papers/clifford/3d/dq.pov new file mode 100644 index 0000000..92b702a --- /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, 0.022) +circlearrow(<1,0,0>, <0,1,0>, <1, 0, 2>, sqrt(2)/2, 0.022) +circlearrow(<0,0,1>, <1,0,0>, <0, sqrt(2), 2>, 0.5, 0.022) + +#declare l = 2.8; +#declare h = 0.0001; +union { + box { <-l,-l,-h>, } + box { <-l,-h,-l>, } + box { <-h,-l,-l>, <-h,l,l> } + pigment { + color rgbt<0.6,0.6,0.6,0.0> + } +} -- cgit v1.2.1 From f06e1476cec724c47306967946f9dcb6d8be971e Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20K=C3=BChne?= Date: Thu, 5 Aug 2021 10:59:29 +0200 Subject: neue version --- buch/papers/munkres/teil1.tex | 43 ++++++++++++++++++------------------------- buch/papers/munkres/teil3.tex | 37 ++++++++++++++++++------------------- 2 files changed, 36 insertions(+), 44 deletions(-) diff --git a/buch/papers/munkres/teil1.tex b/buch/papers/munkres/teil1.tex index 07489e3..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,40 +34,33 @@ 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}$ Zahlen dargestellt, welche den Weg in z.B. Kilometer beschreiben. -Sie entstehen, wenn man z.B. einem Kran $i$ den Einsatzort $j$ zuordnet. - -\begin{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_{1m}\\ -a_{21}&a_{22}&\dots &a_{2m}\\ +a_{11}&a_{12}&\dots &a_{1n}\\ +a_{21}&a_{22}&\dots &a_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ -a_{n1}&a_{n2}&\dots &a_{nm} +a_{n1}&a_{n2}&\dots &a_{nn} \end{pmatrix} \] -\caption{Darstellung einer Matrix $A$} -\end{figure} -Eine Matrix, wie hier in Abbildung 21.2 ersichtlich, ist ein rechteckiges Schema, dessen Elemente üblicherweise Zahlen, aber auch andere mathematische Elemente wie Variablen oder Funktionen sein können. Sie besteht aus $n$ Zeilen und $m$ Spalten. D.h. die Elemente einer Matrix vom Typ $(n,m)$ mit Namen $A$ sind $a_{ij}$ wobei $i$ = 1,..., $m$ 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. + +$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} -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.3 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. -\begin{equation} -Matrix -\end{equation} -Im Bild 21.4 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. -\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 zwei Gruppen von Objekten wird hierbei eine eindeutige Zuordnung hergestellt. +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. diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex index d2e8174..964444c 100644 --- a/buch/papers/munkres/teil3.tex +++ b/buch/papers/munkres/teil3.tex @@ -53,37 +53,36 @@ allen anderen Ziffern in der jeweiligen Zeile subtrahiert. Mit dieser Subtraktio (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 -- cgit v1.2.1 From a8138ae8cf5b0bda133b5c5fb077021ac3d59761 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Thu, 5 Aug 2021 12:59:37 +0200 Subject: add images for clifford article --- buch/papers/clifford/3d/Makefile | 23 ++++++- buch/papers/clifford/3d/common.inc | 59 +++++++++++++++--- buch/papers/clifford/3d/dq.pov | 6 +- buch/papers/clifford/3d/drehung.pov | 120 ++++++++++++++++++++++++++++++++++++ buch/papers/clifford/3d/q23.pov | 12 ++++ buch/papers/clifford/3d/q31.pov | 12 ++++ 6 files changed, 217 insertions(+), 15 deletions(-) create mode 100644 buch/papers/clifford/3d/drehung.pov create mode 100644 buch/papers/clifford/3d/q23.pov create mode 100644 buch/papers/clifford/3d/q31.pov diff --git a/buch/papers/clifford/3d/Makefile b/buch/papers/clifford/3d/Makefile index e6a9be3..70dffe3 100644 --- a/buch/papers/clifford/3d/Makefile +++ b/buch/papers/clifford/3d/Makefile @@ -3,11 +3,28 @@ # # (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule # -all: dq.jpg +all: dq.jpg q23.jpg q31.jpg drehung.jpg -dq.png: dq.pov common.inc - povray +A0.1 +W1920 +H1080 -Odq.png dq.pov +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 index 4bc2e7d..54aa7fe 100644 --- a/buch/papers/clifford/3d/common.inc +++ b/buch/papers/clifford/3d/common.inc @@ -11,10 +11,11 @@ global_settings { } #declare imagescale = 0.14; -#declare r = 0.04; +#declare r = 0.02; +#declare thick = 0.040; camera { - location <40, 10, 15> + location <40, 12, 15> look_at <0, 0, 0> right 16/9 * x * imagescale up y * imagescale @@ -70,12 +71,12 @@ 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) +#macro circlearrow0(e1, e2, e3, r1, r2, h, winkel) mesh { #declare N = 100; #declare phi = 0; - #declare phimax = 1.8 * pi; + #declare phimax = winkel - pi / 12; #declare phistep = (phimax - phi) / N; #while (phi < phimax - phistep/2) triangle { @@ -170,7 +171,7 @@ mesh { #end -#macro circlearrow(fromdirection, axis, center, r, h) +#macro circlearrow(fromdirection, axis, center, r, h, winkel, anzahl) #declare e1 = vnormalize(fromdirection); #declare e2 = -vnormalize(vcross(axis, fromdirection)); @@ -179,27 +180,67 @@ mesh { #declare r1 = 0.4 * r; #declare r2 = r; -circlearrow0(e1, e2, e3, r1, r2) +#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 } -box { - center - r * (e1 + e2) - 0.021 * e3, center + r * (e1 + e2) + 0.021 * e3 pigment { color rgb<0.6,0.6,1> } + finish { + specular 0.96 + metallic + } } +#if (vlength(axis) > 0.1) cone { - center + 0.02101 * e3, r, center + 2 * r * e3, 0 + 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 index 92b702a..8002129 100644 --- a/buch/papers/clifford/3d/dq.pov +++ b/buch/papers/clifford/3d/dq.pov @@ -9,9 +9,9 @@ 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, 0.022) -circlearrow(<1,0,0>, <0,1,0>, <1, 0, 2>, sqrt(2)/2, 0.022) -circlearrow(<0,0,1>, <1,0,0>, <0, sqrt(2), 2>, 0.5, 0.022) +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; 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>, } + //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) -- cgit v1.2.1 From 2bab34711e7654ec4b4bb69e324df57ccc4e4665 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Thu, 5 Aug 2021 13:12:55 +0200 Subject: Changes to IFS image problem --- buch/papers/ifs/images/Makefile | 9 +++++ buch/papers/ifs/images/chaosspiel.tex | 37 +++++++++++++++++++++ .../ifs/images/farnnotweight-eps-converted-to.pdf | Bin 166218 -> 6074235 bytes .../ifs/images/farnrightwight-eps-converted-to.pdf | Bin 59191 -> 6450743 bytes buch/papers/ifs/teil2.tex | 13 ++++---- buch/papers/ifs/teil3.tex | 2 +- 6 files changed, 54 insertions(+), 7 deletions(-) create mode 100644 buch/papers/ifs/images/Makefile create mode 100644 buch/papers/ifs/images/chaosspiel.tex 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 index 35bff32..f5e4093 100644 Binary files a/buch/papers/ifs/images/farnnotweight-eps-converted-to.pdf and b/buch/papers/ifs/images/farnnotweight-eps-converted-to.pdf differ diff --git a/buch/papers/ifs/images/farnrightwight-eps-converted-to.pdf b/buch/papers/ifs/images/farnrightwight-eps-converted-to.pdf index 3652e8f..fa69d77 100644 Binary files a/buch/papers/ifs/images/farnrightwight-eps-converted-to.pdf and b/buch/papers/ifs/images/farnrightwight-eps-converted-to.pdf differ diff --git a/buch/papers/ifs/teil2.tex b/buch/papers/ifs/teil2.tex index c468b73..d0110ed 100644 --- a/buch/papers/ifs/teil2.tex +++ b/buch/papers/ifs/teil2.tex @@ -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 01a3ee2..cebb664 100644 --- a/buch/papers/ifs/teil3.tex +++ b/buch/papers/ifs/teil3.tex @@ -137,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. -- cgit v1.2.1 From def3198eb5a2462d296aea81d14b6b982a722b8e Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Thu, 5 Aug 2021 18:48:54 +0200 Subject: bild 1 --- buch/papers/clifford/3d/Makefile | 8 +++--- buch/papers/clifford/3d/dq.pdf | Bin 0 -> 156467 bytes buch/papers/clifford/3d/dq.pov | 11 ++++++--- buch/papers/clifford/3d/dq.tex | 51 +++++++++++++++++++++++++++++++++++++++ 4 files changed, 64 insertions(+), 6 deletions(-) create mode 100644 buch/papers/clifford/3d/dq.pdf create mode 100644 buch/papers/clifford/3d/dq.tex diff --git a/buch/papers/clifford/3d/Makefile b/buch/papers/clifford/3d/Makefile index 70dffe3..87acb6d 100644 --- a/buch/papers/clifford/3d/Makefile +++ b/buch/papers/clifford/3d/Makefile @@ -3,15 +3,17 @@ # # (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule # -all: dq.jpg q23.jpg q31.jpg drehung.jpg +all: dq.jpg q23.jpg q31.jpg drehung.jpg dq.pdf 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 +dq.jpg: dq.png Makefile + convert -extract 1600x1400+1500+60 dq.png -density 300 -units PixelsPerInch dq.jpg +dq.pdf: dq.jpg dq.tex + pdflatex dq.tex q23.png: q23.pov common.inc povray +A0.1 $(size) -Oq23.png q23.pov diff --git a/buch/papers/clifford/3d/dq.pdf b/buch/papers/clifford/3d/dq.pdf new file mode 100644 index 0000000..1bcaf2c Binary files /dev/null and b/buch/papers/clifford/3d/dq.pdf differ diff --git a/buch/papers/clifford/3d/dq.pov b/buch/papers/clifford/3d/dq.pov index 8002129..762eee2 100644 --- a/buch/papers/clifford/3d/dq.pov +++ b/buch/papers/clifford/3d/dq.pov @@ -9,9 +9,14 @@ 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 drehwinkel = 0.95 * 2*pi/3 * 3; +#declare drehwinkel23 = drehwinkel; +#declare drehwinkel12 = drehwinkel / sqrt(2); +#declare drehwinkel13 = drehwinkel / 2; + +circlearrow(<1,0,0>, <0,0,1>, <1, sqrt(2), 0>, 1, thick, drehwinkel23, 1) +circlearrow(<1,0,0>, <0,1,0>, <1, 0, 2>, sqrt(2)/2, thick, drehwinkel12, 1) +circlearrow(<0,0,1>, <1,0,0>, <0, sqrt(2), 2>, 0.5, thick, drehwinkel13, 1) #declare l = 2.8; #declare h = 0.0001; diff --git a/buch/papers/clifford/3d/dq.tex b/buch/papers/clifford/3d/dq.tex new file mode 100644 index 0000000..6b28452 --- /dev/null +++ b/buch/papers/clifford/3d/dq.tex @@ -0,0 +1,51 @@ +% +% dq.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{times} +\usepackage{amsmath} +\usepackage{txfonts} +\usepackage[utf8]{inputenc} +\usepackage{graphics} +\usetikzlibrary{arrows,intersections,math} +\usepackage{ifthen} +\begin{document} + +\definecolor{darkred}{rgb}{0.7,0,0} + +\newboolean{showgrid} +\setboolean{showgrid}{false} +\def\breite{6} +\def\hoehe{6} + +\begin{tikzpicture}[>=latex,thick] + +% Povray Bild +\node at (0,0) {\includegraphics[width=12cm]{dq.jpg}}; + +% Gitter +\ifthenelse{\boolean{showgrid}}{ +\draw[step=0.1,line width=0.1pt] (-\breite,-\hoehe) grid (\breite, \hoehe); +\draw[step=0.5,line width=0.4pt] (-\breite,-\hoehe) grid (\breite, \hoehe); +\draw (-\breite,-\hoehe) grid (\breite, \hoehe); +\fill (0,0) circle[radius=0.05]; +}{} + +\node at (-2.8,-2.7) {$O$}; +\node at (4.7,-3.4) {$a_1$}; +\node at (-2.6,5.2) {$a_2$}; +\fill[color=white,opacity=0.7] ({-5.7-0.25},{-4.8-0.15}) rectangle ({-5.7+0.25},{-4.8+0.2}); +\node at (-5.7,-4.8) {$a_3$}; + +\node[color=blue] at (-3.6,0.8) {$y\mathbf{e}_{23}$}; +\node[color=blue] at (2.1,0.9) {$x\mathbf{e}_{12}$}; +\node[color=blue] at (1.3,-3.7) {$z\mathbf{e}_{13}$}; + +\node[color=darkred] at (1.3,0.4) {$\vec{q}$}; + +\end{tikzpicture} + +\end{document} + -- cgit v1.2.1 From 001c12e5156f2e3b656bd42608768af5c3db4171 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Thu, 5 Aug 2021 19:14:44 +0200 Subject: Zwei Drehungen --- buch/papers/clifford/3d/Makefile | 16 +++++---- buch/papers/clifford/3d/dq.pdf | Bin 156467 -> 156467 bytes buch/papers/clifford/3d/qq.pdf | Bin 0 -> 170922 bytes buch/papers/clifford/3d/qq.tex | 68 +++++++++++++++++++++++++++++++++++++++ 4 files changed, 78 insertions(+), 6 deletions(-) create mode 100644 buch/papers/clifford/3d/qq.pdf create mode 100644 buch/papers/clifford/3d/qq.tex diff --git a/buch/papers/clifford/3d/Makefile b/buch/papers/clifford/3d/Makefile index 87acb6d..823ad54 100644 --- a/buch/papers/clifford/3d/Makefile +++ b/buch/papers/clifford/3d/Makefile @@ -3,9 +3,8 @@ # # (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule # -all: dq.jpg q23.jpg q31.jpg drehung.jpg dq.pdf +all: dq.jpg q23.jpg q31.jpg drehung.jpg dq.pdf qq.pdf -size="+W1920 +H1080" size="+W3840 +H2160" dq.png: dq.pov common.inc @@ -15,15 +14,20 @@ dq.jpg: dq.png Makefile dq.pdf: dq.jpg dq.tex pdflatex dq.tex +extract="1200x1200+1450+350" + 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 +q23.jpg: q23.png Makefile + convert -extract $(extract) 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 +q31.jpg: q31.png Makefile + convert -extract $(extract) q31.png -density 300 -units PixelsPerInch q31.jpg + +qq.pdf: qq.tex q31.jpg q23.jpg + pdflatex qq.tex drehung.png: drehung.pov common.inc povray +A0.1 $(size) -Odrehung.png drehung.pov diff --git a/buch/papers/clifford/3d/dq.pdf b/buch/papers/clifford/3d/dq.pdf index 1bcaf2c..59a1498 100644 Binary files a/buch/papers/clifford/3d/dq.pdf and b/buch/papers/clifford/3d/dq.pdf differ diff --git a/buch/papers/clifford/3d/qq.pdf b/buch/papers/clifford/3d/qq.pdf new file mode 100644 index 0000000..07a871c Binary files /dev/null and b/buch/papers/clifford/3d/qq.pdf differ diff --git a/buch/papers/clifford/3d/qq.tex b/buch/papers/clifford/3d/qq.tex new file mode 100644 index 0000000..c2ac1bc --- /dev/null +++ b/buch/papers/clifford/3d/qq.tex @@ -0,0 +1,68 @@ +% +% qq.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{times} +\usepackage{amsmath} +\usepackage{txfonts} +\usepackage[utf8]{inputenc} +\usepackage{graphics} +\usetikzlibrary{arrows,intersections,math} +\usepackage{ifthen} +\begin{document} + +\definecolor{darkred}{rgb}{0.7,0,0} + +\newboolean{showgrid} +\setboolean{showgrid}{false} +\def\breite{4} +\def\hoehe{4} + +\begin{tikzpicture}[>=latex,thick] + +% Povray Bild +\begin{scope}[xshift=-3.3cm] +\node at (0,0) {\includegraphics[width=6.3cm]{q23.jpg}}; +% Gitter +\ifthenelse{\boolean{showgrid}}{ +\draw[step=0.1,line width=0.1pt] (-\breite,-\hoehe) grid (\breite, \hoehe); +\draw[step=0.5,line width=0.4pt] (-\breite,-\hoehe) grid (\breite, \hoehe); +\draw (-\breite,-\hoehe) grid (\breite, \hoehe); +\fill (0,0) circle[radius=0.05]; +}{} +\fill[color=white,opacity=0.5] ({-0.6-0.3},{-0.2-0.2}) rectangle ({-0.6+0.3},{-0.2+0.2}); +\node[color=darkred] at (-0.6,-0.2) {$q_{23}$}; +\node[color=blue] at (-0.4,2.7) {$\mathbf{v}$}; +\node[color=blue] at (0.7,0.4) {$\mathbf{v}''_{23}$}; +\node at (3.1,-1.4) {$a_1$}; +\node at (-2.7,-2.4) {$a_3$}; +\node at (-0.7,3.4) {$a_2$}; +\end{scope} + +\setboolean{showgrid}{false} + +\begin{scope}[xshift=3.3cm] +\node at (0,0) {\includegraphics[width=6.3cm]{q31.jpg}}; +% Gitter +\ifthenelse{\boolean{showgrid}}{ +\draw[step=0.1,line width=0.1pt] (-\breite,-\hoehe) grid (\breite, \hoehe); +\draw[step=0.5,line width=0.4pt] (-\breite,-\hoehe) grid (\breite, \hoehe); +\draw (-\breite,-\hoehe) grid (\breite, \hoehe); +\fill (0,0) circle[radius=0.05]; +}{} +\fill[color=white,opacity=0.5] ({-0.7-0.3},{-0.9-0.2}) rectangle ({-0.7+0.3},{-0.9+0.2}); +\node[color=darkred] at (-0.7,-0.9) {$q_{13}$}; +\node[color=blue] at (0.7,0.4) {$\mathbf{v}''_{23}$}; +\node[color=blue] at (2.7,-0.7) {$\mathbf{v}''$}; +\node at (3.1,-1.4) {$a_1$}; +\node at (-2.7,-2.4) {$a_3$}; +\node at (-0.7,3.4) {$a_2$}; +\end{scope} + + +\end{tikzpicture} + +\end{document} + -- cgit v1.2.1 From e5df99c1ee45a6897c4fe98b018088ef0289f7e5 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Thu, 5 Aug 2021 19:35:13 +0200 Subject: add images for clifford --- buch/papers/clifford/3d/Makefile | 8 ++++-- buch/papers/clifford/3d/dq.jpg | Bin 0 -> 135038 bytes buch/papers/clifford/3d/dq.pdf | Bin 156467 -> 156467 bytes buch/papers/clifford/3d/drehung.jpg | Bin 0 -> 203814 bytes buch/papers/clifford/3d/drehung.pdf | Bin 0 -> 224521 bytes buch/papers/clifford/3d/drehung.tex | 56 ++++++++++++++++++++++++++++++++++++ buch/papers/clifford/3d/q23.jpg | Bin 0 -> 77888 bytes buch/papers/clifford/3d/q31.jpg | Bin 0 -> 75576 bytes buch/papers/clifford/3d/qq.pdf | Bin 170922 -> 170756 bytes buch/papers/clifford/3d/qq.tex | 12 ++++---- 10 files changed, 67 insertions(+), 9 deletions(-) create mode 100644 buch/papers/clifford/3d/dq.jpg create mode 100644 buch/papers/clifford/3d/drehung.jpg create mode 100644 buch/papers/clifford/3d/drehung.pdf create mode 100644 buch/papers/clifford/3d/drehung.tex create mode 100644 buch/papers/clifford/3d/q23.jpg create mode 100644 buch/papers/clifford/3d/q31.jpg diff --git a/buch/papers/clifford/3d/Makefile b/buch/papers/clifford/3d/Makefile index 823ad54..147ca81 100644 --- a/buch/papers/clifford/3d/Makefile +++ b/buch/papers/clifford/3d/Makefile @@ -3,7 +3,7 @@ # # (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule # -all: dq.jpg q23.jpg q31.jpg drehung.jpg dq.pdf qq.pdf +all: dq.jpg q23.jpg q31.jpg drehung.jpg dq.pdf qq.pdf drehung.pdf size="+W3840 +H2160" @@ -31,6 +31,8 @@ qq.pdf: qq.tex q31.jpg q23.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 +drehung.jpg: drehung.png Makefile + convert -extract 1600x1450+1400+50 drehung.png -density 300 -units PixelsPerInch drehung.jpg +drehung.pdf: drehung.tex drehung.jpg + pdflatex drehung.tex diff --git a/buch/papers/clifford/3d/dq.jpg b/buch/papers/clifford/3d/dq.jpg new file mode 100644 index 0000000..bd44a65 Binary files /dev/null and b/buch/papers/clifford/3d/dq.jpg differ diff --git a/buch/papers/clifford/3d/dq.pdf b/buch/papers/clifford/3d/dq.pdf index 59a1498..71727d2 100644 Binary files a/buch/papers/clifford/3d/dq.pdf and b/buch/papers/clifford/3d/dq.pdf differ diff --git a/buch/papers/clifford/3d/drehung.jpg b/buch/papers/clifford/3d/drehung.jpg new file mode 100644 index 0000000..ad7cd47 Binary files /dev/null and b/buch/papers/clifford/3d/drehung.jpg differ diff --git a/buch/papers/clifford/3d/drehung.pdf b/buch/papers/clifford/3d/drehung.pdf new file mode 100644 index 0000000..de29085 Binary files /dev/null and b/buch/papers/clifford/3d/drehung.pdf differ diff --git a/buch/papers/clifford/3d/drehung.tex b/buch/papers/clifford/3d/drehung.tex new file mode 100644 index 0000000..2ed6789 --- /dev/null +++ b/buch/papers/clifford/3d/drehung.tex @@ -0,0 +1,56 @@ +% +% drehung.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{times} +\usepackage{amsmath} +\usepackage{txfonts} +\usepackage[utf8]{inputenc} +\usepackage{graphics} +\usetikzlibrary{arrows,intersections,math} +\usepackage{ifthen} +\begin{document} + +\definecolor{darkgreen}{rgb}{0,0.6,0} +\definecolor{darkred}{rgb}{0.6,0,0} + +\newboolean{showgrid} +\setboolean{showgrid}{false} +\def\breite{7} +\def\hoehe{6} + +\begin{tikzpicture}[>=latex,thick] + +% Povray Bild +\node at (0,0) {\includegraphics[width=13cm]{drehung.jpg}}; + +% Gitter +\ifthenelse{\boolean{showgrid}}{ +\draw[step=0.1,line width=0.1pt] (-\breite,-\hoehe) grid (\breite, \hoehe); +\draw[step=0.5,line width=0.4pt] (-\breite,-\hoehe) grid (\breite, \hoehe); +\draw (-\breite,-\hoehe) grid (\breite, \hoehe); +\fill (0,0) circle[radius=0.05]; +}{} + +\node at (6.1,-3.3) {$a_1$}; +\node at (-2.0,5.7) {$a_2$}; +\node at (-5.7,-4.9) {$a_3$}; + +\node[color=white] at (-1.9,4.4) {$\boldsymbol{v}$}; +\node[color=white] at (4.5,-2.7) {$\boldsymbol{v}''$}; + +\node[color=darkgreen] at (-3.3,4.4) {$\boldsymbol{v}_{\perp}$}; +\node[color=darkgreen] at (4.2,-4.3) {$\boldsymbol{v}''_{\perp}$}; + +\node[color=blue] at (-3.7,1.5) {$\boldsymbol{v}_{\|}$}; +\node[color=blue] at (1.9,-4.7) {$\boldsymbol{v}''_{\|}$}; + +\node[color=darkred] at (-1.6,-4.2) {$2\alpha=120^\circ$}; +\node[color=darkred] at (-4.9,-0.6) {$\boldsymbol{q}$}; + +\end{tikzpicture} + +\end{document} + diff --git a/buch/papers/clifford/3d/q23.jpg b/buch/papers/clifford/3d/q23.jpg new file mode 100644 index 0000000..50ca028 Binary files /dev/null and b/buch/papers/clifford/3d/q23.jpg differ diff --git a/buch/papers/clifford/3d/q31.jpg b/buch/papers/clifford/3d/q31.jpg new file mode 100644 index 0000000..10313fa Binary files /dev/null and b/buch/papers/clifford/3d/q31.jpg differ diff --git a/buch/papers/clifford/3d/qq.pdf b/buch/papers/clifford/3d/qq.pdf index 07a871c..4c55d57 100644 Binary files a/buch/papers/clifford/3d/qq.pdf and b/buch/papers/clifford/3d/qq.pdf differ diff --git a/buch/papers/clifford/3d/qq.tex b/buch/papers/clifford/3d/qq.tex index c2ac1bc..9baa8bb 100644 --- a/buch/papers/clifford/3d/qq.tex +++ b/buch/papers/clifford/3d/qq.tex @@ -33,9 +33,9 @@ \fill (0,0) circle[radius=0.05]; }{} \fill[color=white,opacity=0.5] ({-0.6-0.3},{-0.2-0.2}) rectangle ({-0.6+0.3},{-0.2+0.2}); -\node[color=darkred] at (-0.6,-0.2) {$q_{23}$}; -\node[color=blue] at (-0.4,2.7) {$\mathbf{v}$}; -\node[color=blue] at (0.7,0.4) {$\mathbf{v}''_{23}$}; +\node[color=darkred] at (-0.6,-0.2) {$\boldsymbol{q}_{23}$}; +\node[color=blue] at (-0.4,2.7) {$\boldsymbol{v}$}; +\node[color=blue] at (0.7,0.4) {$\boldsymbol{v}''_{23}$}; \node at (3.1,-1.4) {$a_1$}; \node at (-2.7,-2.4) {$a_3$}; \node at (-0.7,3.4) {$a_2$}; @@ -53,9 +53,9 @@ \fill (0,0) circle[radius=0.05]; }{} \fill[color=white,opacity=0.5] ({-0.7-0.3},{-0.9-0.2}) rectangle ({-0.7+0.3},{-0.9+0.2}); -\node[color=darkred] at (-0.7,-0.9) {$q_{13}$}; -\node[color=blue] at (0.7,0.4) {$\mathbf{v}''_{23}$}; -\node[color=blue] at (2.7,-0.7) {$\mathbf{v}''$}; +\node[color=darkred] at (-0.7,-0.9) {$\boldsymbol{q}_{13}$}; +\node[color=blue] at (0.7,0.4) {$\boldsymbol{v}''_{23}$}; +\node[color=blue] at (2.7,-0.7) {$\boldsymbol{v}''$}; \node at (3.1,-1.4) {$a_1$}; \node at (-2.7,-2.4) {$a_3$}; \node at (-0.7,3.4) {$a_2$}; -- cgit v1.2.1