FMM using Amrex (or pyamrex)

[a-jp]

Hi,

I would like to implement the fast marching method using an amrex mesh. Using amrex or pyamrex, not bothered either way. Basically, I don't know where to start to implement this approach as I understand specific data structures are required. I wondered if there were any community implementations that could be shared of the FMM that have used amrex as their mesh backend?

Thanks,

[philip-blakely]

Hi,

I'm not aware of any FMM implementations in AMReX, unfortunately. However, I have implemented FMM before (can't share code; sorry) and it was quite tricky. Most of it is based around a std::multimap<double, IntVect> because we need to have a set of cells/indexes ordered by their distance from the level-set interface. One of the trickier parts was then copying the std::multimap<> information from one patch to another, or at least doing this efficiently. This would probably take a bit of effort to work properly with AMReX's parallel functions.

Is there a particular reason why you need to use the FMM? Due to the data-structure, I don't think it would work well with GPUs because the std::multimap<> needs to be updated atomically by cells in the patch. (You didn't mention GPUs, but AMReX is built around multicore architectures so that it's easier to implement GPU-friendly algorithms.)

If you can, I would suggest starting with a simpler method for level-set reinitialization. One example would be the Fast Iterative Method: https://link.springer.com/article/10.1007/s10915-012-9660-1 (see Eqn (7)) or https://www.sciencedirect.com/science/article/abs/pii/S0021999184711557 (Sections 2.5 and 2.6).

(I've assumed this is for level-set reinitialization; if not, my points above should still apply, just reworked for whatever system you're solving.)

Hope this helps,

Philip

[a-jp]

Hi, thanks for your comments. No my main reason was to get just mesh adaption and refinement around the large gradients (in the front arrival time variable, I guess). I was not interested in GPU, or even MPI to be honest, just AMR. I have a situation where the velocity will not change sign, but will vary in space, to me this means FMM is the best way forward. I have quite a bit of experience implementing Level Set (none good) and in this instance I just need an FMM but I really wanted to harness AMR. I know you can't share your code, but can you share any advice - does FMM with adaption provide real benefits, does it work well?

[philip-blakely]

It's been a while since I did any proper performance comparisons, but I think FMM at least worked fairly well with AMR, once we'd managed to get it properly debugged. It worked well enough with AMR that it gave most of the usual benefits of AMR.

The slight drawback is that you have to make sure that the marching propagates across all patches, which will require some kind of barrier or mutual communication between AMR patches. This will be a particular problem if the interface (or whatever your starting-point is for the marching) happens to be close to one or more patch boundaries, so the marching has to transfer from/to different patches.

For us, this caused issues with parallel scaling, which obviously won't affect you if you're not using MPI, but you will still need multiple iterations across patches to make sure the marching has completed.

Hope this helps.

[asalmgren]

@a-jp - Closing this due to inactivity -- let us know if you still have questions!