\usepackage{aecompl}
\usepackage{color}
\usepackage{graphicx}
-\graphicspath{{./}}
+\graphicspath{{./img/}}
\usepackage{hyperref}
\title{introduction to computational physics}
\end{itemstep}
\end{slide}}
-\overlays{4}{
+\overlays{3}{
\begin{slide}{motivation}
\FromSlide{1}{
\begin{center}
}
\FromSlide{2}{
challenge:
-}
-\FromSlide{3}{
\begin{itemize}
\item precise mathematical theory
\item often: solving theory's equations ab-initio is not realistic
\item only a few models can be solved exactly
\end{itemize}}
-\FromSlide{4}{
+\FromSlide{3}{
$\Rightarrow$ study and implementation of numerical algorithms
}
\end{slide}}
\end{minipage}
\end{slide}}
-\overlays{5}{
+\overlays{6}{
\begin{slide}{history of computing hardware}
\begin{minipage}[t]{10cm}
\onlySlide*{1}{\begin{center} \includegraphics[height=3cm]{4004.eps} \end{center}}
\onlySlide*{2}{\begin{center} \includegraphics[height=3cm]{cray2.eps} \hspace{1pt} \includegraphics[height=3cm]{cray2_i.eps} \end{center}}
\onlySlide*{3}{\begin{center} \includegraphics[height=3cm]{apple2.eps} \includegraphics[height=3cm]{c64.eps} \end{center}}
- \onlySlide*{4}{\begin{center} \includegraphics[height=3cm]{mips.eps} \hspace{1pt} \includegraphics[height=3cm]{ppc.eps} \end{center}}
- \onlySlide*{5}{\begin{center} \includegraphics[height=3cm]{cluster1.eps} \hspace{1cm} \includegraphics[height=3cm]{cluster2.eps} \end{center}}
- %\FromSlide{6}{\begin{center} \includegraphics[height=3cm]{} \end{center}}
+ \onlySlide*{4}{\begin{center} \includegraphics[height=3cm]{intel1.eps} \includegraphics[height=3cm]{intel2.eps} \end{center}}
+ \onlySlide*{5}{\begin{center} \includegraphics[height=3cm]{mips.eps} \hspace{1pt} \includegraphics[height=3cm]{ppc.eps} \end{center}}
+ \onlySlide*{6}{\begin{center} \includegraphics[height=3cm]{cluster1.eps} \hspace{1cm} \includegraphics[height=3cm]{cluster2.eps} \end{center}}
\end{minipage}
\begin{minipage}[b]{10cm}
\begin{itemstep}
\item $1970$: intel 4004 - first single chip $\mu$-processor
\item $1977/85$: cray1/2 - vector supercomputer
\item $1977/82/85$: 6502/6510/m68k - first pc
+ \item $1978/82/85 $: 8086/80286/80386
\item $1985$: mips - first risc design
\item $1990/2000$: massive parallel computing
\end{itemstep}
\end{minipage}
\end{slide}}
-\begin{slide}{}
+\overlays{11}{
+\begin{slide}{history of computing software}
+ \begin{itemstep}
+ \item $1946$: plankalk"ul - high-level programming language
+ \item $1950$: assembler - translating instruction mnemonics
+ \item $1954$: fortran - {\scriptsize formula translation}
+ \item $1963$: basic - {\scriptsize beginner's all purpose symbolic instruction code}
+ \item $1964$: os/360 - batch processing operating system
+ \item $1969$: unix - multics port to pdp-8, pdp-11/20
+ \item $1972$: c programming language - thompson, ritchie
+ \item $1978/84/85$: apple os/atari, amiga os/mac os
+ \item $1981/85/92/95$: ms-dos/windows 1.0/3.x/95
+ \item $1983$: gnu project - unix-like free software development
+ \item $1991$: linux - open-source kernel
+ \end{itemstep}
+\end{slide}}
-\end{slide}
+\overlays{7}{
+\begin{slide}{warning - numerical errors}
+ \begin{itemstep}
+ \item machine accuracy $\epsilon_m$
+ \begin{itemize}
+ \item ieee 64-bit floating point format: $v = -1^s 2^{-e} m$ \\
+ \begin{tabular}{lll}
+ $s$: & signe & 1 bit \\
+ $m$: & mantissa & 52 bit \\
+ $e$: & exponent & 11 bit \\
+ \end{tabular}
+ \item $\epsilon_m$: smallest floating point with $1 + \epsilon_m \neq 1$ \\
+ $\epsilon_m \approx 2.22 \times 10^{-16}$ \hspace{2pt} (roundoff error)
+ \end{itemize}
+ \item truncation error $\epsilon_t$
+ \begin{itemize}
+ \item discrete approximation of continuous quantity
+ \item persists even on hypothetical perfect computer ($\epsilon_m = 0$)
+ \item machine independent, characteristic of used algorithm
+ \end{itemize}
+ \end{itemstep}
+\end{slide}}
-\begin{slide}{}
+\overlays{4}{
+\begin{slide}{warning - recursive functions}
+ \begin{itemstep}
+ \item avoid recursive functions!
+ \verbatiminput{fak1.c}
+ \item better:
+ \verbatiminput{fak2.c}
+ \end{itemstep}
+\end{slide}}
+\begin{slide}{computational techniques}
+ \begin{minipage}{5.5cm}
+ \begin{itemize}
+ \item rough discretization
+ \item solution of linear algebraic equations
+ \item interpolation and extrapolation
+ \item integration of functions
+ \item evaluation of (special) functions
+ \item monte carlo methods
+ \end{itemize}
+ \end{minipage}
+ \begin{minipage}{5.5cm}
+ \begin{itemize}
+ \item eigensystems
+ \item spectral applications
+ \item modeling of data
+ \item ordinary differential equations
+ \item two point boundary value problems
+ \item partial differential \\
+ equations
+ \end{itemize}
+ \end{minipage}
+\footnote{http://www.nr.com/}
\end{slide}
-\begin{slide}{}
+\overlays{3}{
+\begin{slide}{first steps: rough discretization}
+ \begin{itemstep}
+ \item example: homogenous field of force $\vec{F} = (0,-mg)$ \\
+ \begin{tabular}{ll}
+ equation of motion: & $\vec{F} = m \vec{a} = m \frac{d^2 \vec{r}}{dt^2}$ \\
+ initial condition: & $\vec{r}(t=0) = \vec{r_0} = (x_0,y_0)$ \\
+ & $\frac{d \vec{r}}{dt}|_{t=0} = (v_{x_0},v_{y_0})$ \\
+ \end{tabular}
+ \item algorithm using discretized time ($T = N \tau$):
+ \begin{tabular}{lll}
+ $x^1 = x_0;$ & $y^1 = y_0;$ & \\
+ $v^1_x = v_{x_0};$ & $v^1_y = v_{y_0};$ & \\
+ loop: & $x^2 = x^1 + \tau v^1_x;$ & $y^2 = y^1 + \tau v^1_y;$ \\
+ & $v^2_x = v^1_x;$ & $v^2_y = v^1_y - g \tau;$ \\
+ & $x^1 = x^2;$ & $y^1 = y^2$ \\
+ & $v^1_x = v^2_x;$ & $v^1_y = v^2_y;$ \\
+ \end{tabular}
+ \item euler's method for solving o.d.e.
+ \end{itemstep}
+\end{slide}}
-\end{slide}
+\overlays{10}{
+\begin{slide}{euler's method: error estimation}
+ \begin{itemstep}
+ \item truncation error $\epsilon_t$:
+ \begin{itemize}
+ \item $x_{t+\tau} = x(t) + v(t,x) \tau + O(\tau^2)$
+ \item period $T$: $O(\tau^{-1})$ steps $\Rightarrow \epsilon_t \sim O(\tau)$
+ \end{itemize}
+ \item machine accuracy:
+ \begin{itemize}
+ \item every floating point step: error of $O(\epsilon_m)$
+ \item $O(\tau^{-1})$ steps $\Rightarrow$ error of $O(\frac{\epsilon_m}{\tau})$
+ \end{itemize}
+ \item optimum:
+ \begin{itemize}
+ \item $\epsilon \sim \frac{\epsilon_m}{\tau} + \tau$
+ \item 64-bit: $\epsilon_m \sim 10^{-16} \Rightarrow \tau \sim 10^{-8}$
+ \item 32-bit: $\epsilon_m = 1.19 \times 10^{-7} \Rightarrow \tau \sim 3 \times 10^{-4}$
+ \end{itemize}
+ \end{itemstep}
+\end{slide}}
-\begin{slide}{computational techniques}
-techniques discussed in the talk:
-\begin{itemize}
- \item rough discretization
- \item solution of linear algebraic equations
- \item interpolation and extrapolation
- \item integration of functions
- %\item evaluation of (special) functions
- \item monte carlo methods
- \item eigensystems
- \item spectral applications
- %\item modeling of data
- %\item ordinary differential equations
- %\item two point boundary value problems
- %\item partial differential equations
-\end{itemize}
+\begin{slide}{euler's method: accuracy}
+ \includegraphics[width=10cm]{euler.eps}
\end{slide}
-\begin{slide}{computational techniques}
-techniques \textcolor{red}{not yet} discussed in the talk:\footnote{if time is available this will be completed. read more at http://www.nr.com}
-\begin{itemize}
- %\item rough discretization
- %\item solution of linear algebraic equations
- %\item interpolation and extrapolation
- %\item integration of functions
- \item evaluation of (special) functions
- %\item monte carlo methods
- %\item eigensystems
- %\item spectral applications
- \item modeling of data
- \item ordinary differential equations
- \item two point boundary value problems
- \item partial differential equations
-\end{itemize}
-\hspace{6cm}
+\overlays{9}{
+\begin{slide}{monte carlo methods}
+ \begin{itemstep}
+ \item algorithms for solving computational problems using random numbers
+ \item deterministic pseudo-random sequences
+ \item applications:
+ \begin{itemize}
+ \item monte carlo integration
+ \item metropolis algorithm
+ \item simulated annealing
+ \end{itemize}
+ \item advantages:
+ \begin{itemize}
+ \item more efficient than other methods
+ \item no need fo simplifying assumptions
+ \end{itemize}
+ \end{itemstep}
+\end{slide}}
+
+\overlays{5}{
+\begin{slide}{random number generator}
+linear congruential generator:
+ \begin{itemstep}
+ \item $I_{j+1} = ( a I_{j} + c ) \, mod \, m$ \\
+ $a$: multiplier, $c$: increment \\
+ $m$: modulus, $I_0$: seed
+ \item minimal standard by park and miller: \\
+ $a = 7^5 = 16807, \quad m = 2^{31} - 1 = 2147483647, \quad c = 0$
+ \item always seed the rng
+ \end{itemstep}
+\FromSlide{4}{
+$\Rightarrow$ sequence of integers $\in [0,m[$ \\
+}
+\vspace{2pt}
+\FromSlide{5}{
+division by modulus $\Rightarrow$ uniform deviates : \\
+\[
+ p(x)dx = \left\{
+ \begin{array}{ll}
+ dx & 0 \leq x < 1 \\
+ 0 & \textrm{sonst}
+ \end{array} \right.
+\]
+}
+\end{slide}}
+
+\overlays{8}{
+\begin{slide}{special deviates}
+ \begin{itemstep}
+ \item transformation method:
+ \begin{itemize}
+ \item arbitrary probability distribution $\rho(y)$
+ \item trafo: $p(x) dx = \rho(y) dy \Rightarrow x = \int_{- \infty}^y \rho(y) dy$
+ \item get inverse of $x(y) \Rightarrow y(x)$
+ \end{itemize}
+ \item rejection method: \\
+ \begin{minipage}{5cm}
+ \begin{itemize}
+ \item $p(x) \in [a,b]$ mit $p(x) \geq 0 \quad \forall x \in [a,b]$
+ \item uniformly distributed $x \in [a,b]$ und $y \in [0,p_m]$
+ \item if $y \leq p(x)$ use $x$, else reject $x$
+ \end{itemize}
+ \end{minipage}
+ \begin{minipage}{5cm}
+ \includegraphics[width=5cm]{rej_meth.eps} \\
+ \end{minipage}
+ \end{itemstep}
+\end{slide}}
+
+\overlays{5}{
+\begin{slide}{monte carlo integration}
+ basics:
+ \begin{itemstep}
+ \item $I = \int_{\Omega} f d \Omega$
+ \item instead of regular $x_i$, choose them at random
+ \item $I \approx \Omega <f> \pm \Omega \sqrt{\frac{<f^2> - <f>^2}{N}}$ \\
+ $<f> = \frac{1}{N} \sum_{i=1}^{N} f(\vec{x_i})$ \\[6pt]
+ $<f^2> = \frac{1}{N} \sum_{i=1}^{N} f^2(\vec{x_i})$
+ \end{itemstep}
+\FromSlide{4}{
+ example: gambling for $\pi$ \\
+}
+\FromSlide{5}{
+ \[
+ \begin{array}{l}
+ \pi = \int_{-1}^1 \int_{-1}^1 p(x,y) dx dy \approx \frac{4}{N} \sum_{i=1}^N p(x_i,y_i) \\[6pt]
+ \textrm{with } p(x,y) = \left\{
+ \begin{array}{ll}
+ 1 & x^2 + y^2 \leq 1 \\
+ 0 & \textrm{sonst}
+ \end{array} \right.
+ \end{array}
+ \]
+}
+\end{slide}}
+
+\overlays{5}{
+\begin{slide}{metropolis algorithm}
+ising model:
+ \begin{itemstep}
+ \item $d$-dimensional periodic lattice
+ \item two possible states for magnetic moment at site $i$: \\
+ $\mu_i = \mu S_i \qquad S_i = \pm 1 \quad \forall i$
+ \item nearest neighbors moments interact, \\
+ interaction strength $\frac{J_{ij}}{\mu^2}$
+ \end{itemstep}
+\FromSlide{4}{
+$\Rightarrow$ hamiltonian: $H = - \sum_{(i,j)} J_{ij} S_i S_j$ \\
+}
+\FromSlide{5}{
+partition function: \\
+\[
+Z = \sum_{i=1}^N e^{\frac{-E_i}{k_B T}} = Tr(e^{-\beta H})
+\]
+}
+\end{slide}}
+
+\overlays{2}{
+\begin{slide}{metropolis algorithm}
+ \begin{itemstep}
+ \item importance sampling: \\
+ $<A> = \sum_i p_i A_i \approx \frac{1}{N} \sum_{i=1}^N A_i$ , with \\[6pt]
+ $\qquad p_i = \frac{e^{- \beta E_i}}{Z}$
+ \item detailed balance \\[6pt]
+ sufficient condition for equilibrium: \\
+ \[
+ W(A \rightarrow B) p(A) = W(B \rightarrow A) p(B)
+ \]
+ $\Rightarrow \frac{W(A \rightarrow B)}{W(B \rightarrow A)} = \frac{p(B)}{p(A)} = e^{\frac{- \Delta E}{k_B T}}$ \\[6pt]
+ with $\Delta E = E(B) - E(A)$
+ \end{itemstep}
+\end{slide}}
+
+\overlays{5}{
+\begin{slide}{metropolis algorithm}
+ \begin{itemstep}
+ \item choose $W$: \\
+ \[
+ W(A \rightarrow B) = \left\{
+ \begin{array}{ll}
+ e^{- \beta \Delta E} & : \Delta E > 0 \\
+ 1 & : \Delta E < 0
+ \end{array} \right.
+ \]
+ \item algorithm:
+ \begin{itemize}
+ \item visit every lattice site
+ \item calculate $\Delta E$ for spin flip
+ \item flip spin if $r \leq e^{\frac{-\Delta E}{k_B T}}$
+ \end{itemize}
+ \end{itemstep}
+\end{slide}}
+
+\begin{slide}{summary}
+ \begin{itemize}
+ \item importance of computational physics
+ \item things to keep in mind when doing computational physics
+ \item euler's method for solving o.d.e.
+ \item introduction to monte carlo methods
+ \end{itemize}
\end{slide}
\end{document}
projects / lectures / latex.git / blobdiff