Photos of Sichuan Province, China (May 2014)

In May I had the chance to visit Chengdu, Chongqing, Emei Shan and a few other places in Sichuan Province, China. I travelled with Fritz Kretzschmar a good week long before attending a conference, which was quite a success for him.

Chengdu and Chongqing made a big impression on me. Chengdu for its beauty and calmness, its beautiful and plenty parks and the tea house culture. Maybe I am prejudiced but I did not expect this from a big Chinese city.

My prejudices were met when we arrived to Chongqing. This is a place, where I definitely could not live. Everything is packed with sky scrapers, cars and people. It’s noisy and very stressful – at least for me. You will have no problems identifying which photos are from Chongqing…

 Photo Gallery

Python Implementations and Comparison of InsertionSort, SelectionSort, MergeSort and QuickSort

Python3 implementations with timing.

#!/usr/bin/env python

from collections import deque
import random
import time

### INSERTION SORT ###
def InsertionSort ( unsorted ):
    sorted = [ unsorted[0] ]
    for i in range(1, len(unsorted)):
        j = 0
        while j < len(sorted) and sorted[j] < unsorted[i]:
            j += 1
        sorted.insert(j, unsorted[i])
        # print ( ''.join(sorted) )
    return sorted

### SELECTION SORT ###
# based on creating a new sorted list by extracting elements from the unsorted list
def SelectionSort1 ( unsorted ):
    sorted = []
    for j in range( len(unsorted) ):
        smallest = max(unsorted)
        for i in range( len(unsorted) ):
            if unsorted[i] <= smallest:
                smallest = unsorted[i]
                position = i
        sorted.append(smallest)
        del unsorted[position]
    return sorted

# based on swapping elements
def SelectionSort2 ( array ):
    for i in range( len(array) ):
        smallest = i
        for j in range( i+1, len(array) ):
            if array[j] < array[smallest]:
                smallest = j
        array[i], array[smallest] = array[smallest], array[i]
    return array

### MERGESORT ###
def Merge ( array, lo, md, hi ):
    queue1 = deque(array[lo:md+1])
    queue2 = deque(array[md+1:hi+1])

    pos = lo
    while len(queue1) and len(queue2):
        if queue1[0] < queue2[0]:
            array[pos] = queue1.popleft()
        else:
            array[pos] = queue2.popleft()
        pos += 1

    while len(queue1):
        array[pos] = queue1.popleft()
        pos += 1
    while len(queue2):
        array[pos] = queue2.popleft()
        pos += 1

def MergeSort ( array, lo, hi ):
    if hi > lo:
        md = int ((hi+lo)/2)
        MergeSort ( array,lo,md )
        MergeSort ( array,md+1,hi )
        Merge ( array, lo, md, hi )

### QUICKSORT ###
def Partition ( array, lo, hi ):
    # print ( ''.join(array[lo:hi+1]) )
    pivot = array[hi]

    pivotPosition = lo
    for i in range ( lo, hi ):
        if array[i] < pivot:
            array[pivotPosition], array[i] = array[i], array[pivotPosition]
            pivotPosition += 1

    array[pivotPosition], array[hi] = array[hi], array[pivotPosition]
    # print ( ''.join(array[lo:hi+1]) )
    return pivotPosition

def QuickSort ( array, lo, hi ):
    # avoid problems for almost sorted data
    if lo == 0 and hi == len(array) - 1:
        random.shuffle ( array )
    if hi > lo:
        pivotPosition = Partition ( array, lo, hi )
        QuickSort ( array, lo, pivotPosition-1 )
        QuickSort ( array, pivotPosition+1, hi )

### MAIN ###
if __name__ == "__main__":
    # unsorted = [ 'T', 'H', 'I', 'S', 'L', 'I', 'S', 'T', 'I', 'S', 'U', 'N', 'S', 'O', 'R', 'T', 'E', 'D' ]
    # print ( ''.join(unsorted) )
    N = 20000

    unsorted = [int(random.random() * N) for i in range(N)]
    start = time.time()
    sorted = InsertionSort( unsorted )
    print ( "InsertionSort:  " + str( time.time() - start ) )
    # print ( ''.join(sorted) )

    unsorted = [int(random.random() * N) for i in range(N)]
    start = time.time()
    sorted = SelectionSort1( unsorted )
    print ( "SelectionSort1: " + str( time.time() - start ) )
    # print ( ''.join(sorted) )

    unsorted = [int(random.random() * N) for i in range(N)]
    start = time.time()
    sorted = SelectionSort2( unsorted )
    print ( "SelectionSort2: " + str( time.time() - start ) )
    # print ( ''.join(sorted) )

    array = [int(random.random() * N) for i in range(N)]
    start = time.time()
    MergeSort( array, 0, len(array)-1 )
    print ( "MergeSort:      " + str( time.time() - start ) )
    # print ( ''.join(array) )

    array = [int(random.random() * N) for i in range(N)]
    start = time.time()
    QuickSort( array, 0, len(array)-1 )
    print ( "QuickSort:      " + str( time.time() - start ) )
    # print ( ''.join(array) )

Group of the Week (III): James Blake

It has been a while since the last Group of the Week (I had a feeling it turn out this way…).

Anyway, if you do a bold extrapolation from the two groups featured so far, I like Metal and Electro-Pop. While this represent a minor portion of the music I listen too, I will continue with James Blake — another Electro-Pop act. His latest album is entitled overgrown, and I really like it. He also has a cool webpage.

Today, I found a show he performed at the Pitchfork Music Festival in Paris.

James Blake on Spotify:

Paper on Optimal Control of the Inhomogeneous Relativistic Maxwell Newton Lorentz Equations

Oliver Thoma and Christian Meyer of the Chair of Scientific Computing at TU Dortmund and I submitted a paper on the optimal control of the inhomogeneous relativistic Maxwell Newton Lorentz equations. The abstract reads

This note is concerned with an optimal control problem governed by the relativistic Maxwell-Newton-Lorentz equations, which describes the motion of charges particles in electro-magnetic fields and consists of a hyperbolic PDE system coupled with a nonlinear ODE. An external magnetic field acts as control variable. Additional control constraints are incorporated by introducing a scalar magnetic potential which leads to an additional state equation in form of a very weak elliptic PDE. Existence and uniqueness for the state equation is shown and the existence of a global optimal control is established. Moreover, first-order necessary optimality conditions in form of Karush-Kuhn-Tucker conditions are derived. A numerical test illustrates the theoretical findings.

Please find the preprint on arXiv.

Graduation of Alexander Kuhl

On Friday, Nov 7 Alexander Kuhl successfully defended his thesis entitled

Entwicklung und Realisierung eines 40 GHz Ankunftszeitmonitors für Elektronenpakete für FLASH und den European XFEL

(Development and Realization of a 40 GHz Bunch Arrival Time Monitor for FLASH and European XFEL)

Congratulations!

Please find his thesis here.

Paper on Transparent Boundary Conditions in a Discontinuous Galerkin Trefftz method

Fritz Kretzschmar, Herbert Egger, Igor Tsukerman, Thomas Weiland and I submitted a paper on transparent boundary conditions in the Discontinuous Galerkin Trefftz method.

EDIT: The paper was published in Applied Mathematics and Computation
Volume 267, Pages 42–55

The abstract reads

The modeling and simulation of electromagnetic wave propagations is often accompanied by a restriction to bounded domains and the introduction of artificial boundary conditions which should be chosen in order to minimize parasitic reflections. In this paper, we investigate a new type of transparent boundary condition and its implementation in a Discontinuous Galerkin Trefftz Finite Element Method. The choice of a particular set of basis functions allows us to split the electromagnetic field into components with a specified direction of propagation. The reflections at the artificial boundaries are then reduced by penalizing components of the field incoming into the space-time domain of interest. We formally introduce this concept, discuss its realization within the discontinuous Galerkin framework, and demonstrate the performance of the resulting approximations in comparison with commonly used absorbing boundary conditions. In our numerical tests, we observe spectral convergence in the L2 norm and a dissipative behavior for which we provide a theoretical explanation.

A preprint is available on arXiv. You will find background information on the Discontinuous Galerkin Trefftz method in our previous article.