# Adaptive mesh data structure for Fast Marching Method to overcome RAM limit

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 {
public:
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++.

-
There are distributed-memory parallel implementations of the Fast Marching Method, e.g. Tugurlan's 2008 thesis: etd.lsu.edu/docs/available/etd-09152008-143521/unrestricted/…. You could overcome your memory limits by using more computers. – Bill Barth Feb 13 '13 at 23:51