Speed of advect v solve for deforming mesh

[RebeccaFarrington]

@jmansour - can you add more details?

[jmansour]

Yes I can! So, in uw-retro, we had a cheeky little hack that allowed for a faster owning cell search for deformed mesh. Basically it started the search from the previous owning cell, whereas currently we start the search from the cell with the middle local index.

Again, this is for deformed mesh.. where the mesh is cartesian, we use much faster regular-mesh routines as opposed to the drunken walk search (/newborn giraffe walk / drunken stiletto walk).

My proposed solution is the expose the global coord -> (local coord, elementId) routine as a Function™. This function can then optionally also take a hint function which for swarms might provide the previous owning cell.

[lmoresi]

The mirko's walk algorithm is not directed and not guaranteed to visit each cell only once ... so this seems like a very poor algorithm for finding a particle.

I don't think the other algorithm is really a cheeky hack at all given that we choose a timestep which ensures that the particles haven't moved very much. If the mesh is actively deforming as well due to boundary conditions then we have a similar restriction on how many cells a typical particle will traverse.

The troublesome case is where the mesh-movement is arbitrary (e.g. for mesh refinement) - especially if we end up re-partitioning. But that is easily fixed - for irregular meshes, we might have to use scipy which is chock full of kd-tree algorithms for doing fast searches on grids.

L

---

From: jmansour [notifications@github.com] Sent: Wednesday, April 20, 2016 7:23 AM To: underworldcode/underworld2 Subject: Re: [underworldcode/underworld2] Speed of advect v solve for deforming mesh (#112)

Yes I can! So, in uw-retro, we had a cheeky little hack that allowed for a faster owning cell search for deformed mesh. Basically it started the search from the previous owning cell, whereas currently we start the search from the cell with the middle local index.

Again, this is for deformed mesh.. where the mesh is cartesian, we use much faster regular-mesh routines as opposed to the drunken walk search (/newborn giraffe walk / drunken stiletto walk).

My proposed solution is the expose the global coord -> (local coord, elementId) routine as a Function™. This function can then optionally also take a hint function which for swarms might provide the previous owning cell.

— You are receiving this because you are subscribed to this thread. Reply to this email directly or view it on GitHub<redir.aspx?REF=5INPiUe9uAkQ1oGPlcDAEvobmwJhDm-ROnb0lFhcFk-YWQfumWjTCAFodHRwczovL2dpdGh1Yi5jb20vdW5kZXJ3b3JsZGNvZGUvdW5kZXJ3b3JsZDIvaXNzdWVzLzExMiNpc3N1ZWNvbW1lbnQtMjEyMTM1NjUw>

[jmansour]

I didn't mean cheeky in its logic, just in its implementation. :-)

[lmoresi]

That's what happens when you write code in the hot tub I suppose.

---

From: jmansour [notifications@github.com] Sent: Wednesday, April 20, 2016 7:44 AM To: underworldcode/underworld2 Cc: Louis Moresi; Comment Subject: Re: [underworldcode/underworld2] Speed of advect v solve for deforming mesh (#112)

I didn't mean cheeky in its logic, just in its implementation.

— You are receiving this because you commented. Reply to this email directly or view it on GitHub<redir.aspx?REF=PwWBkS99kg1_3w7WIuOvvMk8nrWcHEsAGLQpWGY979mQkSFjnmjTCAFodHRwczovL2dpdGh1Yi5jb20vdW5kZXJ3b3JsZGNvZGUvdW5kZXJ3b3JsZDIvaXNzdWVzLzExMiNpc3N1ZWNvbW1lbnQtMjEyMTQxOTE3>

[julesghub]

Well said louis. I think the previous "cheeky" solution was quite reasonable and we should have that functionality back again for default deformed meshes....but the implementation was a hottub disaster for which I am to blame ;)

John, the proposed solution essentially recreates the cheeky algorithm right? Also with the general proposed solution. What are other "hint functions" it could take? IJK search

On 20 April 2016 at 08:04, Louis Moresi notifications@github.com wrote:

That's what happens when you write code in the hot tub I suppose.

---

From: jmansour [notifications@github.com] Sent: Wednesday, April 20, 2016 7:44 AM To: underworldcode/underworld2 Cc: Louis Moresi; Comment Subject: Re: [underworldcode/underworld2] Speed of advect v solve for deforming mesh (#112)

I didn't mean cheeky in its logic, just in its implementation.

— You are receiving this because you commented. Reply to this email directly or view it on GitHub<redir.aspx?REF=PwWBkS99kg1_3w7WIuOvvMk8nrWcHEsAGLQpWGY979mQkSFjnmjTCAFodHRwczovL2dpdGh1Yi5jb20vdW5kZXJ3b3JsZGNvZGUvdW5kZXJ3b3JsZDIvaXNzdWVzLzExMiNpc3N1ZWNvbW1lbnQtMjEyMTQxOTE3>

— You are receiving this because you are subscribed to this thread. Reply to this email directly or view it on GitHub https://github.com/underworldcode/underworld2/issues/112#issuecomment-212148122

[lmoresi]

Does the projection functionality enable you to do SPR ? I am not sure if the requirement for C1 continuity is built in ?

Sent from my iPhone

On 19 Apr 2016, at 17:37, julesghub notifications@github.com<mailto:notifications@github.com> wrote:

Well said louis. I think the previous "cheeky" solution was quite reasonable and we should have that functionality back again for default deformed meshes....but the implementation was a hottub disaster for which I am to blame ;)

John, the proposed solution essentially recreates the cheeky algorithm right? Also with the general proposed solution. What are other "hint functions" it could take? IJK search

On 20 April 2016 at 08:04, Louis Moresi notifications@github.com<mailto:notifications@github.com> wrote:

That's what happens when you write code in the hot tub I suppose.

---

From: jmansour [notifications@github.commailto:notifications@github.com] Sent: Wednesday, April 20, 2016 7:44 AM To: underworldcode/underworld2 Cc: Louis Moresi; Comment Subject: Re: [underworldcode/underworld2] Speed of advect v solve for deforming mesh (#112)

I didn't mean cheeky in its logic, just in its implementation.

— You are receiving this because you commented. Reply to this email directly or view it on GitHub<redir.aspx?REF=PwWBkS99kg1_3w7WIuOvvMk8nrWcHEsAGLQpWGY979mQkSFjnmjTCAFodHRwczovL2dpdGh1Yi5jb20vdW5kZXJ3b3JsZGNvZGUvdW5kZXJ3b3JsZDIvaXNzdWVzLzExMiNpc3N1ZWNvbW1lbnQtMjEyMTQxOTE3>

— You are receiving this because you are subscribed to this thread. Reply to this email directly or view it on GitHub https://github.com/underworldcode/underworld2/issues/112#issuecomment-212148122

— You are receiving this because you commented. Reply to this email directly or view it on GitHubhttps://github.com/underworldcode/underworld2/issues/112#issuecomment-212184720

[lmoresi]

kdtree

[julesghub]

I threw in the cheeky solution with a somewhat-nicer implementation. https://github.com/underworldcode/underworld2/commit/c3be1e4e6e07f350f67bf032ba5e2be4482fdc07 This significantly speeds up evaluate(swarm) and advection within non-regular meshes. I thought I'd throw this now because currently particles+deformed mesh models are painfully slow. I still believe other implementations of the problem should be explored.

[rbeucher]

+1 for KdTree but the cheeky solution is more than welcomed for now...!