The most funny part - I managed to reduce the running time to 3 seconds, rofl.
In my code I use a lot of computations of the dot(A*B*f,f) for matrices A,B and vectors f filled with complex{float64}. But this is the same as dot(B*f,A'*f) !! So, multiplication of matrices was the most time-consuming part. Even though matrices were sparse with sizes around 50x50.