\documentclass[pdf]{prosper}

\usepackage{verbatim}
\usepackage[german]{babel}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{ae}
\usepackage{aecompl}
\usepackage{color}
\usepackage{graphicx}
\graphicspath{{./img/}}
\usepackage{hyperref}

\title{introduction to computational physics}
\subtitle{basic concepts and approaches}
\author{frank zirkelbach}
\email{frank.zirkelbach@physik.uni-augsburg.de}
\institution{experimantal physics {\footnotesize IV} - university of augsburg}

\begin{document}

\maketitle

\overlays{5}{
\begin{slide}{outline}
\begin{itemstep}
  \item motivation
  \item history of computing hardware/software
  \item warning
  \item computational techniques
  \item summary
\end{itemstep}
\end{slide}}

\overlays{3}{
\begin{slide}{motivation}
\FromSlide{1}{
  \begin{center}
  \begin{figure}[h]
  \includegraphics[width=8cm]{cp_appl_field.eps}
  \end{figure}
  \end{center}
}
\FromSlide{2}{
challenge:
\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{3}{
$\Rightarrow$ study and implementation of numerical algorithms
}
\end{slide}}

\overlays{5}{
\begin{slide}{history of computing hardware}
  \begin{minipage}[t]{10cm}
     \onlySlide*{1}{\begin{center} \includegraphics[height=3cm]{abacus.eps} \end{center}}
     \onlySlide*{2}{\begin{center} \includegraphics[height=3cm]{eniac.eps} \hspace{1cm} \includegraphics[height=3cm]{tube.eps} \end{center}}
     \onlySlide*{3}{\begin{center} \includegraphics[height=3cm]{z1.eps} \end{center}}
     \onlySlide*{4}{\begin{center} \includegraphics[height=3cm]{pdp1.eps} \hspace{1pt} \includegraphics[height=3cm]{transistor.eps} \end{center}}
     \onlySlide*{5}{\begin{center} \includegraphics[height=3cm]{pdp8.eps} \hspace{1cm} \includegraphics[height=3cm]{ic.eps} \end{center}}
     %\FromSlide{6}{\begin{center} \includegraphics[height=3cm]{} \end{center}}
  \end{minipage}
  \begin{minipage}[b]{10cm}
    \begin{itemstep}
      \item $3000 \, bc$: abacus - first calculating device
      \item $1945$: eniac - electrical digital computer
      \item $1938/41$: z1/3 - featuring memory and programmability
      \item $1960$: pdp-1 - transistor based computers
      \item $1964$: pdp-8 - integrated circuit computers
    \end{itemstep}
  \end{minipage}
\end{slide}}

\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]{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}}

\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}}

\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}}

\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}

\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 + (-mg) \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}}

\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}{euler's method: accuracy}
  \includegraphics[width=10cm]{euler.eps}
\end{slide}

\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 propability 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{4}{
\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 markov process: \\
          \begin{itemize}
            \item $P(A,t)$: probability of configuration $A$ at time $t$ 
            \item $W(A \rightarrow B)$: transition probability
            \[
            \begin{array}{l}
            P(A,t+1) = P(A,t) + \\
            \sum_B \Big( W(B \rightarrow A) P(B,t) - W(A \rightarrow B) P(A,t) \Big)
            \end{array}
            \]
          \end{itemize}
  \end{itemstep}
\end{slide}}

\overlays{5}{
\begin{slide}{metropolis algorithm}
  \begin{itemstep}
    \item detailed balance
    \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}
