Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

On an uniform mesh of positions in space $\ (xi,yj,zk)$:

$\ xi = x0 + i*dx, 0 <=i<nx$

$\ yj = y0 + j*dy, 0 <=j<ny$

$\ zk = z0 + k*dz, 0 <=k<nz$

I have a velocity function: V(xi,yj,zk).

Given a start position (xs,ys,zs) I can calculate the time it takes to reach all points in space: T(xi,yj,zk) by the Fast Marching Method (FMM).

However I would like to do this on an mesh larger than can fit in RAM, e.g. nx=ny=nz=2000.

FMM need access to ALL velocity data. It is NOT possible to run it on only a part of the mesh and then later combine results somehow.

The data structure storing the velocity data can however be sparse. As long as the FMM can ask for the value at any (xi,yj,zk) it do not care how it is stored internally.

I imagine setting blocks of values at a time:

struct SparseArray3D {
    SparseArray3D(int nx, int ny, int nz);
    void setBlock(int i0, int j0, int k0, float block[64][64][64]); // i0 <= i < i0 + 64, j0 <= j < j0 + 64, k0 <= k < k0 + 64  
    float& operator()(int i, int j, int k); // needed by FMM

Do you have any tips on which data structure I could use?

(As you probably already have guessed) I am programming in C/C++.

share|improve this question
There are distributed-memory parallel implementations of the Fast Marching Method, e.g. Tugurlan's 2008 thesis:…. You could overcome your memory limits by using more computers. – Bill Barth Feb 13 '13 at 23:51

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.