Thomas Klimpel
  • Member for 10 years
  • Last seen this week
  • Munich, Germany
How do I take the FFT of unevenly spaced data?
10 votes

In signal processing, aliasing is avoided by sending a signal through a low pass filter before sampling. Jack Poulson already explained one technique for non-uniform FFT using truncated Gaussians as ...

View answer
Why would a computational scientist need to implement their own version of std::complex?
8 votes

I use std::complex<> in my programs, and have to fight with compiler flags and workaround for each new compiler or compiler upgrade. I will try to recount these fights in chronological order: ...

View answer
Are there any famous problems/algorithms in scientific computing that cannot be sped up by parallelisation
8 votes

The (famous) fast marching method for solving the Eikonal equation cannot be sped up by parallelization. There are other methods (for example fast sweeping methods) for solving the Eikonal equation ...

View answer
Can my project survive without Object Orientation?
Accepted answer
6 votes

There is no need to convert to a OOP framework, in order to benefit from object orientation where it helps. Note that the number of functions is less of an indicator than code duplication within and ...

View answer
Find cfl condition
Accepted answer
5 votes

Your image of the numerical domain of dependence is correct. But try to also draw the analytical domain of dependence, maybe this could help you to better understand what is going on. Note that the ...

View answer
Why does `symrcm` create larger band width?
Accepted answer
5 votes

Nothing is wrong here. The Cuthill-McKee algorithm is a greedy algorithm, and doesn't depend too much on the order of A on input. The reverse Cuthill-McKee algorithm is often used to produce nice ...

View answer
Solving sparse linear equations with an iterative, out-of-core algorithm
Accepted answer
5 votes

For a sparse parallel solver, it's your own responsibility to provide a matrix vector product and a suitable preconditioner. The data for the vector itself should fit into main memory in any case. If ...

View answer
ODEs vs DAE vs ADE?
4 votes

Here is an identical copy of an answer on MO: One intuitive way to understand a DAE is to interpret it as a dynamical system which can be controlled by some input signals, whose output signals have ...

View answer
uniform vs. non-uniform grid
4 votes

The typical reason why a non-uniform can lead to higher accuracy is that the PDE to solve is not of the form $u_t(x,t)=u_{xx}(x,t)$, but of the form $u_t(x,t)=(D(x)u_x(x,t))_x$. If your non-uniform ...

View answer
Fourier transform for Neumann boundary condition
4 votes

The FFT can be used for periodic boundary conditions. Because von Neumann boundary conditions are effectively "mirror" boundary conditions, you have to do a "mirrored continuation", before you can ...

View answer
Under what circumstances is Monte Carlo integration better than quasi-Monte Carlo?
Accepted answer
4 votes

Monte Carlo simulations are the method of choice for computation of electron scattering. Tricks like importance sampling are used sometimes, so you might say it's not plain old Monte Carlo. But the ...

View answer
Iterative solution to a nonlinear equation
4 votes

The Banach fixed-point theorem describes the standard situation when a fixed-point iteration is globally convergent. Especially the uniqueness part of the theorem indicates that you can only expect ...

View answer
Can all eigenvalues of a Hermitian Toeplitz matrix be computed in $\tilde{O}(n)$ time?
4 votes

My first idea for computing the eigenvalues of a Hermitian Toeplitz matrix would be to use the fast $O(n \log n)$ matrix multiplication for Toeplitz matrices together with the Lanczos algorithm to get ...

View answer
Convert an implicit ODE system to an explicit ODE set to use Runge-Kutta
Accepted answer
3 votes

You certainly have a number of cursoriness mistakes in your derivation, but often only part of the mistake is propagated to later equations. $V=mgly_2$ should be $V=mgy_2$. $L=\frac{m}{2}\left(2\dot ...

View answer
Single versus double floating-point precision
3 votes

My advice would be to focus mainly on the memory consumption for the decision when to use single precision (float). So the bulk data for a FDTD computation should use float, but I would keep the ...

View answer
How to fill a 2D set over a cartesian lattice with as few rectangles as possible?
3 votes

The boundary of the domain has exactly two types of corners: convex 90 degree corners and concave 90 degree corners. For filling the domain with non-overlapping rectangles, only the concave corners ...

View answer
Algebraic multigrid for complex valued matrices
Accepted answer
2 votes

How can this approach be recycled to also solve complex valued problems like every harmonic simulation? The difference of an harmonic simulation to a static simulation are bigger than just replacing ...

View answer
Natural spline conditions for 2D cubic splines
2 votes

There are two different ways to extent cubic splines to 2D. The more official approach is the tensor product approach. On the boundaries where $x$ is constant, you require $S_{xx}=0=S_{xxy}$. On the ...

View answer
What are good parametrizations of rational functions for response surface models?
2 votes

What are good parametrizations of rational functions for response surface models? A widely used flexible parametrization of (piecewise) rational functions are non-uniform rational basis spline (NURBS)...

View answer
A better Fast Marching Method?
2 votes

My current implementation have two problems: I. I must keep the whole cost (slowness) function in RAM. This limits the size of the cost function I can use. II. I would like it to be even ...

View answer
When we use Bernstein polynomials in application
2 votes

The control points of a Bézier curve are close to the curve, but not necessarily on the curve. This is exactly the same situation as for the approximation by Bernstein polynomials, and in fact the ...

View answer
Computational cost of numerical methods for PDEs
2 votes

The computational cost depends not just on the number of DOF, but also on how efficient you can solve the resulting (nonlinear?) equation system. As an extreme case, the time harmonic Maxwell ...

View answer
Rule of thumb for time-step for solving Maxwell's Equation using 3D-FDTD?
1 votes

There is a very simple rule of thumb for the time step in FDTD: set it as large as possible while still satisfying the CFL condition. Basically your space discretization dicatates you your time step. ...

View answer
How to solve ODEs with constraints using BVP4C?
1 votes

You call this system an ODE (ordinary differential equation), but this sort of system is actually called an DAE (differential algebraic equation). What should I do to deal with above constraint? ...

View answer
Does ADI/Split-operator change the stability properties of the Crank-Nicholson method?
Accepted answer
1 votes

The time-dependent Schrödinger equation is not really a heat equation. Still, the Crank–Nicolson method is well suited for its solution. However, the Crank-Nicolson method is fully implicit, so the ...

View answer
Restrict Voronoï diagram to a polygon
1 votes

Building the Voronoï diagram of $n$ points already takes time $O(n \log n)$. I assume that what you want to compute is the intersection of the Voronoï diagram with the polygon. One way to compute this ...

View answer
Simulated Annealing proof of convergence
1 votes

Do you have box constraints, or do your constraints at least define a convex region? If not, they certainly can cause bad convergence. I looked up SA with downhill simplex in my copy of Num.recipes. ...

View answer
fortran code-algorithm for qr decomposition of non-square matrix
0 votes

MINPACK uses a non-square QR factorization with pivoting, i.e. it's not a real QR decomposition (like the one in LAPACK), but a generalized more robust QRP decomposition (where P is the permutation ...

View answer
How to sample numerically from an arbitrary smooth distribution?
0 votes

I have solved my problem now. The reason why I lost accuracy doesn't even occur in the question. Let's first address the proposed solution ideas from the question: Trying to learn more was a good ...

View answer
Why isn't my Matrix-Vector Multiplication Scaling?
0 votes

I have the impression that row-major ordering is optimal for this problem with respect to memory access times, cache lines usage and TLB misses. I guess your FORTRAN version used column-major ordering ...

View answer