Title: All Decks / ETH_Sem5_old / ICP

Q: Heviside-Lorentz
[...]
[...]
A: Kontinuitätsgleichung:; \(div \vec i = -\dede{\rho}{t}\)

Q: Heviside-Lorentz
B-Feldgleichungen (stationär)
[...]
[...]
A: \(div B = 0\); \(rot B = i/c\)

Q: Heviside-Lorentz
[...]
[...]
A: Umformung Stromdichte <-> Magnetisierung:; \(\vec i = c rot \vec M\)

Q: Heviside-Lorentz
Homogene Feldgleichungen:
[...]
[...]
A: \(div B = 0\); \(rot E + \frac 1 c \dede{B}{t} = 0\)

Q: Heviside-Lorentz
Inhomogene Feldgleichungen:
[...]
[...]
A: \(rotB - \frac 1 c \dede{E}{t} = \frac{i}{c}\); \(div E = \rho\)

Q: Identität:
 [...] \(=\) [...]
A: \(rot (rot( E)) \); \(\vec \nabla div(E) - \Delta E\)

Q: Heviside-Lorentz
Felder durch Potentiale:
[...]
[...]
A: \(B = rot A\); \(E = -\nabla \varphi- \frac 1 c \dede{A}{t}\)

Q: Heviside-Lorentz
Eichtransformationen des Feldes:
[...]
[...]
A: \(\varphi \to \varphi - \frac 1 c \dede{\chi}{t}\); \(A \to A + \nabla \chi\)

Q: Heviside-Lorentz
Inhomogene MGl [...] Eichung:
[...]
[...]
A: Lorenz; \(\square \varphi = \rho\); \(\square A = \frac i c\)

Weak vs strong scaling

Q: How does multiprocessing work in julia?
A: - The (+) stands for the reduction opperation of +
- Each loop starts a new worker (new cpu)

How does multithreading work in julia?

Q: What is congruential RNG?
A: It is best if we have p as a Mersenne prime (a prime number of the form \(2^n - 1\))

Q: What is lagged fibbonachi?
A: Additive RNG method of the type:

How to test RNG?
- Square test: The plot of consecutive numbers (xi, xi+1) should be distributed homogeneously. Any sign of clustering indicates non-randomness and correlation in the sequence {xi}.
- Cube test: Similar to the square test, but in three dimensions with tuples (xi, xi+1, xi+2), aiming for homogeneous distribution.
- Average value: The arithmetic mean of {xi} in [0, 1) should approach 1/2 as more numbers are included.
- Fluctuation of the mean value (χ2-test):  Distribution should behave like a Gaussian distribution around 1/2.
- Spectral analysis (= Fourier analysis): Fourier transform using Fast Fourier Transform (FFT) can reveal randomness in the frequency distribution.
- Correlation tests: Analyzing correlations like \(\abk{x_i x_{i+d} } - \abk{x_i^2}\)

Q: Why do we care about low discrepancy sequences? What are the errors in the associated MC sampling methods?
A: Low discrepancy are non-random, but more uniform than true random

Q: Explain \(D^*\) discrepancy, what is the formula?
A: Looking at all subboxes with a corner in the "lower-left" we find how many points are inside of this box as compared with how many would be uniform.
The largest such value is returned.
The first sum, looks at all points in the sequence. The product under the sum ensures that the point is in the subbox spanned by \(v\) along every axis.
The last product is just the volume of the hypercube spanned by \(v\)

How do we approximate an integral using MC methods?

Q: What are the integration error bounds for QMC methods?
A: With \(V\) the variation \(d\) the dimension \(N\) the number of samples \(c\) a dimension dependant constant

Q: Ways to create non-uniform random numbers
A: - Transformation Method
- Rejection sampling

Q: How does the transformation method work?
A: \(p_u \) is a uniform distribution and \(p_{nu}\) is the desired distribution.
\(x\) is the probabilty to receive a number in \([0,x]\) under the uniform distribution.
It is also the probability to receive a number in \([0,x']\) under the non-uniform distribution.
If we find \(x'\) in relation to \(x\) we can calculate a random number, which by satisfying the cdf, also satisfies the true distribution.
Ex:
 \(p_{exp}(z) = e^{-kz}\)
We ensure \(p_e\) is properly normalized:
 \(\int_0^\infty p_e dz = 1\)
\(x = \int_0^{x'} p_e dz = 1-e^{-kx'}\)
Inverting to \(x'\)
\(x' = -{1\over k} \log(1-x)\)

Q: What is rejection sampling?
A: We sample random points in 2d and keep them if they are "under" the curve

Formal definition of cellular automata?

Q: How do we get the 1D cellular automaton rule from the number?
A: Because we only consider "3-tile-neigbourhoods" we can describe any local situation using a number between 1 and 8.
Each bit in the rule-number is the result of situation 1-8 we read the bits from right to left.
(odd numbers transform \(000\) to \(1\))

Q: What are 1D automaton classes?
A: - Class 1: All patterns are quickly stable and homogenous
- Class 2: All patterns quickly stable or oscillating
- Class 3: All patterns are quickly random
- Class 4: All patterns have complex interactions

Q: What are some interesting CA?
A: - GOL: 0,1,4-8 death 3 birth
- Traffic: 10111000
- Langton Ant: White->Gray + 90 turn left. Gray->White 90 turn right
- HPP Gas: 2 Steps - Propagation, Collision

Q: Explain the order in a phase transition.
A: First-order: Order parameter jumps at critical point
Second-order: Order parameter varies continiously at critical point
Examples:
- Boiling
- Percolation

Q: What are relevant parameters in percolation?
A: - Percolation strength \(P(p)\) fraction of sites part of the spanning cluster. It is the order parameter.
- Critical exponent \(\beta\): power dependence of the order parameter close to criticality
- Wrapping probability: Probability to have a percolating system
- Cluster size distribution:

Q: What is the Burning Algorithm?
A: BFS to find the shortest percolating path

Q: What is the Hoshen-Kopelman Algorithm?
A: Union find to find number and size of clusters
The clever part is that we scan from top left to right, which allows us to only look at the left and the top. If we find two different clusters we merge one into the other using union find (add the total mass as negative, to mark it as a subcluster)

Q: What is the fractal dimension?
A: Where \(V^*\) is the smallest volume of spheres of size \(\varepsilon\) needed to cover the entire thing.
Essentially we calculate the log-ratio of the volume to the side-length of the system

Q: What are the sandbox and box-counting methods?
A: Sandbox:
Look at increasingly larger regions of the fractal, plot log(box-size) vs log(covering) and take the slope.
Box-counting:
We count the number of empty boxes when partitioning our fractal into \(\epsilon\) sized boxes. and plot log(boxes) vs (\(1/\epsilon)\) and take the slope

Q: What are the errors involved in numerical integration?
A: 1-D:
local error: \(\mathcal{O}(\Delta x^3)\)
global error: \(\mathcal{O} (N\Delta x^3) = \mathcal{O} (\Delta x^2)\)
N-D:
global error: \(\mathcal{O}(N^{-2/d})\) with \(N= \#intervals \space per \space dim ^d\)

Q: Error in MC Integration:
A: \(\mathcal{O}(N^{-1/2})\)

Q: How to speed up MC methods?
A: - Control Variates
- Importance Sampling
- Quasi MC
- Markov Chain MC
- MLMC

Q: What is Control Variates?
A: We write our integral as
\(\int f(x) dx = \int(f-g)dx + \int g dx\)
Where \(\int g dx\) is easy to calculate and \(f-g\) is flatter than \(f\)
This means that \(var(g) < 2*cov(f,g)\), meaning \(f,g\) are positiveley correlated

Q: How does importance sampling work?
A: We sample our function non-uniformly:
\(I_{MC} = {1 \over N} \sum_i^N {f(x_i) \over g(x_i)}\)
where \(x_i\) is distributed according to \(g\)
Note that \(g\) needs to be a PDF (especially it needs to \(\int\) to \(1\))

Q: What is Markov Chain MC?
A: We sample our points according to transfer probabilities, this allows us (assuming ergodicity) to sample only relevant regions.
We want \(W\) to have the following properties:
- Normalization: \(\sum_Y W(X\to Y) = 1\)
- Homogeneity: \(\sum_Y p(Y) W(Y \to X) = p(X)\)
- Ergodicity: \(W(X\to Y) > 0 \forall X,Y\)
A good condition (but not the most strict) is the detailed balance condition
\(p_{st}(Y)W(Y \to X) = p_{st}(X)W(X \to Y)\)

What is the master equation?

Q: What is the \(M(RT)^2\)/ Metropolis Hastings algorithm?
A: A choice of \(W\) for MCMC such that:
\(T\) uniform
\(A_M(X\to Y) = min[1,{p_{st}(Y)\over p_{st}(X)}]\)
This is especially useful if we don't know \(p_{st}\) normalized (like in boltzman distributed systems)
We need to give the algorithm enough time to find the distribution, which is called the burn in phase
The algorithm goes as follows:

What are the canonical equations?

Q: What is Liouville's theorem, and why is it useful?
A: It's useful because we can now consider the system statistically

What is the hamiltonian in the ising model?

Explain MCMC on the ising model

Q: What ist the formula/ trick used in MLMC?
A: The trick is this telescopic sum allows us to decompose the estimation on the fine level \(\mathbb{E}(P_L)\) using courser levels. By weighting the levels according to their cost/variance we can get fine estimation with the cost of course calculation.

What are the cost/ variance of one level in MLMC?

Variance and cost in MLMC

Q: List of error sources:
A: - Errors in given input data
- Rounding errors during the computation
- Truncation Errors
- Simplifications in the Mathematical Model
- Human & Machine Errors

Error propagation for addition, multiplication and general functions

Statistical estimation of error after a function

State the Navier-Stokes-Equation

Q: Fluid continuity equation:
A: \[\partial_t \rho  + \nabla (\rho \vec v) = 0\]

Navier-Stokes for incompressible fluids:

State the linear advection equation:

For linear advection state all the discretisation schemes:

Q: State the courant numbers and orders of accuracy for linear advection discretisations:
A: - FTBS: \(c = v {\Delta t \over \Delta x}\) 1. order s & t
- FTCS: \(c = v {\Delta t \over 2\Delta x}\)2. order s \ 1. order t
- BTCS: \(c = v {\Delta t \over 2\Delta x}\) 2. order s \ 1. order t
- CTCS: \(c = v {\Delta t \over \Delta x}\) 2. order s&t

Generally, we distinguish between  unconditionally stable schemes which are stable for any time step size and  conditionally stable  schemes which are only stable for sufficiently small time steps. Otherwise we call the scheme  unconditionally unstable. The relation between consistency, stability and convergence is summarized in the Lax Equivalence Theorem which states that a consistent finite difference scheme is convergent if and only if it is stable.

Q: Define consistency, how do we normaly prove it?
A: Consitent means that for \(\Delta x,t \to 0\) all errors due to finite diference approximations vanish.
We normaly just show 1. order accuracy, which implies consistency

Q: How to test for stability?
A: - CFL: Stability implies that the analytical domain of dependence is included in the numerical one. (attention, not the other way around)
- Neumann Stability Analysis: Check if fourier coefficients blow up
- Conserved Quantities
- Higher Moments
- Dispersion

Q: State the shallow water equations:
A: \(\partial_t \vec w = -g \nabla\eta\)
\(\partial_t \eta = - H_0 \nabla \cdot\vec w\)

Draw the image of different integration schemes

Q: Error for Euler method, and reasons
A: \(\eta\) is the smallest number we can add and makes a diffence, we round off \(1 \over \Delta t\)times per unit interval.
Euler has truncation errors of \(\mathcal{O}(\Delta t^2)\) which we do \(\mathcal{\Delta t^{-1}}\) times

Q: Write down centered, forward and backwards difference approximation, including their order
A: From
we get:

Q: How do we get the shallow water equations?
A: Using the incompressible Navier-Stokes we decompose the heigth of water as:
\(H(x,y,t ) = H_0 + H'(x,y,t)\)
We assume \(H'<<\) and \(\eta = 0\) (no viscosity), but we introduce a graviational force.
\[(\partial_t + \vec v \cdot \nabla) \vec v = -\frac{1}{\rho} \nabla p + \vec g\]
\[\nabla \cdot \vec v = 0\]

Q: For shallow water, what is the difference between A and C?
Why would we choose one over the other?
A: A is stable for \(c\le 2\)
C is stable for \(c \leq 1\), but the dispersion is better

Q: What form do the initial value problems for time integration take?
A: Which results in the problem to be solved:

Q: Write down the Butcher tableau for RK4.
What is the meaning of this?
A: The left side is the time offset for \(k_i\)
The bottom is the weigth of \(k_i\) in the final result
The middle is the space offset (in fractions of \(k_j\))

Write down RK4

Q: How to check for energy conservation of an approximated Hamiltonian?
A: We need to check that the Hamiltonian has \(det(H) = 1\)

Q: What does symplectic mean? How do we enforce it?
A: A transformation which conserves phase space. We can modify elements of the hamiltonian such that \(det(A) = 1\)

State Lorentz force law in SI-Units

State the Maxwell Equations in SI-Units

What is the poisson equation in SI-units?

What is the Faraday law in SI-Units?

Q: State the curl-curl equation, what does it describe?
A: \(\varepsilon\dede{^2 E}{t^2} + \nabla\times(\nabla \times \frac{E}{\mu}) = 0\)
It describes a propagating electromagnetic wave

Q: Draw a Yee Lattice in 1D, which are the involved spatial directions?
A: \(E_x\) and \(H_y\) and the position in \(z\)

Q: How to implement ABC in 1D Maxwell solvers? When does this work, and why?
A: \(E^n_{j=0} = E^{n-2}_{j=1}\)
This only works for \(c\Delta t\over h \\ = 0.5\)
By translating the field by half a period we will get perfect absorbing boundry conditions

Draw a 3D Yee cell

Q: What is the Liouville equation, what does it describe?
A: It describes the movement of particle distributions under external force

Q: Write down the non relativistic Vlasov-Possion equation.
What do the terms mean?
A: First Line: Liouville Equation with potential as an "external" force
Second Line: Poisson equation
Third line: Translation between density (in real space) to distribution (in state space)

Q: Write down the Vlasov-Maxwell equations.
What do the terms mean?
A: 1) Liouville equation under Lorentz force
2) Homogenious Maxwell Equations
3) Inhomogenious Maxwelll Equations
4) Translation between realspace density/current and statespace density/ current

Q: How to solve N-Body problems?
A: - Particle in Cell: Follow particles, solve field on grid
- P3M (Particle-Particle Particle-Mesh): Separate forces to long and short range
- Fast Multipole: Collect "far away objects" to center of mass and higher multipoles
- Tree Methods: Subdivide space and calculate on apropriate levels

Q: What is the Boris algorithm? How does it work?
A: The Boris Algorithm solves the particle part of the Vlasov-Maxwell-Equations and "pushes" them using Lorentz force.
It works by redefining the velocities as follows:
This canceles the electric field and allows to solve for a pure rotation

Q: What is the PIC method? How does it work?
A: Particle In Cell method is often used to solve plasma physics problems.
It works the following way:
- Integrate the equations of Motion (Push)
- Interpolate charge and current to mesh (Scatter)
- Compute field at mesh (Force Field Calculation)
- Interpolate field to particles (Gather)