librelist archives

« back to archive

p4est_iterate over unbalanced quadtrees

p4est_iterate over unbalanced quadtrees

From:
Trevor Vincent
Date:
2015-08-11 @ 15:14
Dear p4est developers,

In a code I am writing I need to iterate over the faces of an unbalanced
quadtree (neighbouring octants are not 2:1) and retrieve the user_data of
quadrants sharing each face. If I understand the source code for the
p4est_iter_face_info struct correctly, it appears that it will not provide
the full array of quadrants sharing a face unless p4est_iterate is called
on a 2:1 balanced forest. Does the p4est API offer some way to get the data
of the quadrants sharing a face when the tree is unbalanced? Any help on
this matter would be greatly appreciated.

Sincerely,
Trevor Vincent

Re: [p4est] p4est_iterate over unbalanced quadtrees

From:
Tobin Isaac
Date:
2015-08-12 @ 01:31
Hi Trevor,

On Tue, Aug 11, 2015 at 11:14:39AM -0400, Trevor Vincent wrote:
> Dear p4est developers,
> 
> In a code I am writing I need to iterate over the faces of an unbalanced
> quadtree (neighbouring octants are not 2:1) and retrieve the user_data of
> quadrants sharing each face. If I understand the source code for the
> p4est_iter_face_info struct correctly, it appears that it will not provide
> the full array of quadrants sharing a face unless p4est_iterate is called
> on a 2:1 balanced forest. Does the p4est API offer some way to get the data
> of the quadrants sharing a face when the tree is unbalanced? Any help on
> this matter would be greatly appreciated.

In short, no, there is no function in the API that does this, but
depending on what you're trying to do, what you want can be cobbled
together pretty easily.  Do you just need to identify neighbors, or
are you looking to do something more complicated?

  Toby


> 
> Sincerely,
> Trevor Vincent

Re: [p4est] p4est_iterate over unbalanced quadtrees

From:
Trevor Vincent
Date:
2015-08-12 @ 15:06
Hi Toby,

Thank you for your reply. I am trying to do a flux calculation on the
boundary data of a quadrant similar to what's done in p4est_step3.c, but
without the 2:1 balance. So I just need to identify the quadrants sharing
each face. When the forest is unbalanced it appears that p4est_iter_face_info
will give the first quadrant in each of the two hanging quadrant families
touching the full side. So I could conceivably just iterate over the
morton-ordered quadrants close to these first quadrants until some
condition fails (i.e. the corner coords of the quadrant are >= half the
length of the full side + corner coords of the first quadrant) and check
for other quadrants sharing the face within this set, but this naive
implementation would be less than 50% efficient if the face in question was
8:1 or even more unbalanced. I assume there is some simpler, more efficient
method?

Sincerely,
Trevor Vincent

On Tue, Aug 11, 2015 at 9:31 PM, Tobin Isaac <tisaac@ices.utexas.edu> wrote:

>
> Hi Trevor,
>
> On Tue, Aug 11, 2015 at 11:14:39AM -0400, Trevor Vincent wrote:
> > Dear p4est developers,
> >
> > In a code I am writing I need to iterate over the faces of an unbalanced
> > quadtree (neighbouring octants are not 2:1) and retrieve the user_data of
> > quadrants sharing each face. If I understand the source code for the
> > p4est_iter_face_info struct correctly, it appears that it will not
> provide
> > the full array of quadrants sharing a face unless p4est_iterate is called
> > on a 2:1 balanced forest. Does the p4est API offer some way to get the
> data
> > of the quadrants sharing a face when the tree is unbalanced? Any help on
> > this matter would be greatly appreciated.
>
> In short, no, there is no function in the API that does this, but
> depending on what you're trying to do, what you want can be cobbled
> together pretty easily.  Do you just need to identify neighbors, or
> are you looking to do something more complicated?
>
>   Toby
>
>
> >
> > Sincerely,
> > Trevor Vincent
>

Re: [p4est] p4est_iterate over unbalanced quadtrees

From:
Carsten Burstedde
Date:
2015-08-20 @ 08:37
Hi Trevor,

> Thank you for your reply. I am trying to do a flux calculation on the
> boundary data of a quadrant similar to what's done in p4est_step3.c, but
> without the 2:1 balance. So I just need to identify the quadrants sharing
> each face. When the forest is unbalanced it appears that p4est_iter_face_info
> will give the first quadrant in each of the two hanging quadrant families
> touching the full side. So I could conceivably just iterate over the
> morton-ordered quadrants close to these first quadrants until some
> condition fails (i.e. the corner coords of the quadrant are >= half the
> length of the full side + corner coords of the first quadrant) and check
> for other quadrants sharing the face within this set, but this naive
> implementation would be less than 50% efficient if the face in question was
> 8:1 or even more unbalanced. I assume there is some simpler, more efficient
> method?

I don't have much to add -- extending p4est_iterate for non-balanced
forests would be the solution you seek, but that's technically demanding
and requires some serious work.  I don't want to discourage you though,
we'd be very happy if you'd really wanted to go that way and discuss the
interface with us.

A more immediate path would be searching through the ghost layer
whenever iterate shows you are at a 4:1 or higher interface.  You might
think of binary searches that can hopefully be optimized by exploiting
the Morton order of quadrants in the ghost layer.

Carsten

> Sincerely,
> Trevor Vincent
> 
> On Tue, Aug 11, 2015 at 9:31 PM, Tobin Isaac <tisaac@ices.utexas.edu> wrote:
> 
> >
> > Hi Trevor,
> >
> > On Tue, Aug 11, 2015 at 11:14:39AM -0400, Trevor Vincent wrote:
> > > Dear p4est developers,
> > >
> > > In a code I am writing I need to iterate over the faces of an unbalanced
> > > quadtree (neighbouring octants are not 2:1) and retrieve the user_data of
> > > quadrants sharing each face. If I understand the source code for the
> > > p4est_iter_face_info struct correctly, it appears that it will not
> > provide
> > > the full array of quadrants sharing a face unless p4est_iterate is called
> > > on a 2:1 balanced forest. Does the p4est API offer some way to get the
> > data
> > > of the quadrants sharing a face when the tree is unbalanced? Any help on
> > > this matter would be greatly appreciated.
> >
> > In short, no, there is no function in the API that does this, but
> > depending on what you're trying to do, what you want can be cobbled
> > together pretty easily.  Do you just need to identify neighbors, or
> > are you looking to do something more complicated?
> >
> >   Toby
> >
> >
> > >
> > > Sincerely,
> > > Trevor Vincent
> >

Re: [p4est] p4est_iterate over unbalanced quadtrees

From:
Trevor Vincent
Date:
2015-08-26 @ 18:16
Hi Carsten,

Thank you for your reply. I decided to hard-set a 2:1 balance into my code
for the time being. It would be interesting to study the numerical error
and scalability of unbalanced flux calculations in parallel PDE solvers, so
I hope to return to this problem after my current project is completed. I
will contact you when I attempt to extend p4est_iterate as I will likely
need to discuss a few things in order to get this going.

Sincerely,
Trevor Vincent

On Thu, Aug 20, 2015 at 4:37 AM, Carsten Burstedde <
burstedde@ins.uni-bonn.de> wrote:

> Hi Trevor,
>
> > Thank you for your reply. I am trying to do a flux calculation on the
> > boundary data of a quadrant similar to what's done in p4est_step3.c, but
> > without the 2:1 balance. So I just need to identify the quadrants sharing
> > each face. When the forest is unbalanced it appears that
> p4est_iter_face_info
> > will give the first quadrant in each of the two hanging quadrant families
> > touching the full side. So I could conceivably just iterate over the
> > morton-ordered quadrants close to these first quadrants until some
> > condition fails (i.e. the corner coords of the quadrant are >= half the
> > length of the full side + corner coords of the first quadrant) and check
> > for other quadrants sharing the face within this set, but this naive
> > implementation would be less than 50% efficient if the face in question
> was
> > 8:1 or even more unbalanced. I assume there is some simpler, more
> efficient
> > method?
>
> I don't have much to add -- extending p4est_iterate for non-balanced
> forests would be the solution you seek, but that's technically demanding
> and requires some serious work.  I don't want to discourage you though,
> we'd be very happy if you'd really wanted to go that way and discuss the
> interface with us.
>
> A more immediate path would be searching through the ghost layer
> whenever iterate shows you are at a 4:1 or higher interface.  You might
> think of binary searches that can hopefully be optimized by exploiting
> the Morton order of quadrants in the ghost layer.
>
> Carsten
>
> > Sincerely,
> > Trevor Vincent
> >
> > On Tue, Aug 11, 2015 at 9:31 PM, Tobin Isaac <tisaac@ices.utexas.edu>
> wrote:
> >
> > >
> > > Hi Trevor,
> > >
> > > On Tue, Aug 11, 2015 at 11:14:39AM -0400, Trevor Vincent wrote:
> > > > Dear p4est developers,
> > > >
> > > > In a code I am writing I need to iterate over the faces of an
> unbalanced
> > > > quadtree (neighbouring octants are not 2:1) and retrieve the
> user_data of
> > > > quadrants sharing each face. If I understand the source code for the
> > > > p4est_iter_face_info struct correctly, it appears that it will not
> > > provide
> > > > the full array of quadrants sharing a face unless p4est_iterate is
> called
> > > > on a 2:1 balanced forest. Does the p4est API offer some way to get
> the
> > > data
> > > > of the quadrants sharing a face when the tree is unbalanced? Any
> help on
> > > > this matter would be greatly appreciated.
> > >
> > > In short, no, there is no function in the API that does this, but
> > > depending on what you're trying to do, what you want can be cobbled
> > > together pretty easily.  Do you just need to identify neighbors, or
> > > are you looking to do something more complicated?
> > >
> > >   Toby
> > >
> > >
> > > >
> > > > Sincerely,
> > > > Trevor Vincent
> > >
>