<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><div>Hi Matt,</div><div><br></div><div>I suppose I should get into why I've been working on this. I had a need to initialize some tracer particles in a FLASH simulation that's already been running. I decided to use yt to open up the checkpoint file and generate the tracer particles based on the gas density, and then I was going to write them back to the checkpoint file in the format FLASH expects.</div><div><br></div><div>It then occurred to me that such particle initialization could be useful for yt in general, particularly for initial conditions generation as you and others have been working on. So I have been working on some classes for generating particle fields on the fly, with positions based on some criterion such as density, a lattice, or any general criterion. For some distributions, the grids the particles belong to would not be known a priori, so it seemed necessary to write a faster implementation of find_point and generalize it to a number of points.</div><div><br></div><div>I was thinking about two applications in particular:</div><div><br></div><div>1) One could generate a grid structure with some fields, generate particle positions, generate other particle fields, and then write everything to disk using GDF.<br><br>2) An existing pf has no particles, but the user has some other criterion that would be used to generate a set of particle fields that they are interested in. These fields could then be "loaded in" as any others would.</div><div><br></div><div>Any thoughts on this? I've already written most of the machinery for this in the last few days.</div><div><br></div><div>John </div><div><br>John ZuHone<div>Laboratory for High-Energy Astrophysics<br><div>NASA/Goddard Space Flight Center</div><div>8800 Greenbelt Rd., Code 662</div><div>Greenbelt, MD 20771</div><div>(w) 301-286-2531</div><div>(m) 773-758-0172</div></div><div><a href="mailto:jzuhone@gmail.com">jzuhone@gmail.com</a></div><div><a href="mailto:john.zuhone@nasa.gov">john.zuhone@nasa.gov</a></div></div><div><br>On Nov 18, 2012, at 5:56 PM, Matthew Turk <<a href="mailto:matthewturk@gmail.com">matthewturk@gmail.com</a>> wrote:<br><br></div><blockquote type="cite"><div>Hi John,<div><br></div><div>I think this looks pretty good for now, certainly for 2.x.</div><div><br></div><div>In 3.0 I want to eventually transition FLASH to the Octree geometry structure, which would mean that particle location could all occur directly inside Cython. We'd also have a number of much faster particle selection routines, which could eventually make it not necessary to directly sort or select particles too strongly in advance, as long as a coarse index could be built.</div>
<div><br></div><div>I say push it and we can move on from there. If you want, one thing you could absolutely do right now is construct a Cython routine that accepted:</div><div><br></div><div>x,y,z</div><div>left_edges, right_edges, parent_index</div>
<div><br></div><div>and then construct an octree from that, assigning particles as they came.</div><div><br></div><div>-Matt</div><div><br>On Saturday, November 17, 2012, John ZuHone wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div style="word-wrap:break-word">By the way, I certainly think that there is much room for improvement, so anyone that would like to take a look at it and make suggestions is most welcome. <div><br><div><div>On Nov 17, 2012, at 6:09 PM, Christopher Moody <<a>cemoody@ucsc.edu</a>> wrote:</div>
<br><blockquote type="cite">Hi John,<div>That speed is similar to what I found. Brute force collision check would make (3x2x7000x10^6) ~ 10^10 floating point operations, which should take a few seconds on a modern single core (3Ghz*10seconds). Making an actually intelligent depth-first search should drop the number of grids to check for every particle by an order of magnitude. So we should really be able to beat a 4-minute gridding time, we just need to figure out what the bottleneck is. And of course this is applicable to particles in yt-3.0.<span></span></div>
<div><br></div><div>chris</div><div><br><br><div>On Sat, Nov 17, 2012 at 6:30 AM, John ZuHone <span dir="ltr"><<a>jzuhone@gmail.com</a>></span> wrote:<br>
<blockquote style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word">Chris,<div><br></div><div>Since last night I've developed a working depth-first approach which is *reasonably* fast, but I think it depends on your definition of reasonable. :) It just did a FLASH dataset with ~7000 blocks and 10^6 points in about 4 minutes. </div>
<div><br></div><div>I'm going to try it out on a few more datasets, and I'm hoping to issue a PR for it today or tomorrow. </div><div><br></div><div>Best,</div><div><br></div><div>John</div><div>
<br><div><div>On Nov 16, 2012, at 6:21 PM, Christopher Moody <<a>cemoody@ucsc.edu</a>> wrote:</div><br><blockquote type="cite">Hi John, <div>
I tried writing a cython routine that matched particles to grids a while back. It works in the opposite order as a recursive octree-like gridding. It starts with the highest-level most-refined grids, recording the grid ID that each particle belongs to. It skips previously gridded particles as it progresses to coarser grids. It's likely not faster than depth-first approach.</div>
<div><br></div><div>It could be helpful, but it's terribly slow, despite several attempts to speed it up. </div><div>Check out assign_particles_to_cell_lists() in yt-hg/yt/utilities/lib/CICDeposit.pyx</div><div><br>
</div>
<div>chris </div><div><br><br><div>On Fri, Nov 16, 2012 at 11:30 AM, Matthew Turk <span dir="ltr"><<a>matthewturk@gmail.com</a>></span> wrote:<br>
<blockquote style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi John,<br>
<br>
I think that would work fine for Enzo, we'd just need to iterate over<br>
root grids.<br>
<br>
-Matt<br>
<div><br>
On Fri, Nov 16, 2012 at 2:28 PM, John ZuHone <<a>jzuhone@gmail.com</a>> wrote:<br>
> Hi Matt,<br>
><br>
> Would it work just to start at the top-level grids and then work down the tree, checking the children as you go? I know this would work for FLASH, but I'm not certain it would work for Enzo.<br>
><br>
> John<br>
><br>
> On Nov 16, 2012, at 2:14 PM, Matthew Turk <<a>matthewturk@gmail.com</a>> wrote:<br>
><br>
>> Hi John,<br>
>><br>
>> That's the ideal way, but we don't yet have the code to do that. I<br>
>> would like to do that. The fastest method would be to create a new<br>
>> version of find_values_at_points (which accepts an array) and make itj<br>
>> ust return grid indices. This would do the NxM collision check of<br>
>> particles in grids.<br>
>><br>
>> Writing an octree-aware particle finder would be a good idea.<br>
>> Necessary, even...<br>
>><br>
>> -Matt<br>
>><br>
>> On Fri, Nov 16, 2012 at 1:07 PM, John ZuHone <<a>jzuhone@gmail.com</a>> wrote:<br>
>>> I did know about that, but given, say, a million points, would that be<br>
>>> *fast*? I need to look at what it does I guess.<br>
>>><br>
>>> In FLASH, what'd we'd normally do is start at the top level and traverse<br>
>>> down the octree until we found the block.<br>
>>><br>
>>> On Nov 16, 2012, at 1:02 PM, Nathan Goldbaum <<a>nathan12343@gmail.com</a>> wrote:<br>
>>><br>
>>> Hi John,<br>
>>><br>
>>> Yes, you can use pf.h.find_point() to do that. There's some documentation<br>
>>> on it here:<br>
>>> <a href="http://yt-project.org/doc/analyzing/low_level_inspection.html#finding-data-at-fixed-points" target="_blank">http://yt-project.org/doc/analyzing/low_level_inspection.html#finding-data-at-fixed-points</a><br>
>>><br>
>>> -Nathan<br>
>>><br>
>>> On Nov 16, 2012, at 10:00 AM, John ZuHone wrote:<br>
>>><br>
>>> Hi all,<br>
>>><br>
>>> Do we have anything in yt right now that, given a set of points, *quickly*<br>
>>> finds out which grids they belong to?<br></div></blockquote></div></div></blockquote></div></div></div></blockquote></div></div></blockquote></div></div></div></blockquote></div>
</div></blockquote><blockquote type="cite"><div><span>_______________________________________________</span><br><span>yt-dev mailing list</span><br><span><a href="mailto:yt-dev@lists.spacepope.org">yt-dev@lists.spacepope.org</a></span><br><span><a href="http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org">http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org</a></span><br></div></blockquote></body></html>