[petsc-dev] DMPlexMarkBoundaryFaces is quadratic time

[Geoffrey Irving]

On Wed, Nov 20, 2013 at 6:30 PM, Matthew Knepley <knepley at gmail.com> wrote:
> On Wed, Nov 20, 2013 at 7:22 PM, Geoffrey Irving <irving at naml.us> wrote:
>>
>> Was there any particular reason for making DMPlexMarkBoundaryFaces a
>> quadratic time algorithm?  I realize it's hard to write a subquadratic
>> time algorithm on top of DMLabelSetValue; maybe PETSc needs some basic
>> integer hash tables?
>
> Why is it quadratic time? I just looked again, and it seems to be linear
> time to me.

It calls DMLabelSetValue for each boundary face.  Each call to
DMLabelSetValue seems to be O(log n) if the value is already set
(binary search) and O(n/2) if the value is missing, since it does a
PetscMemmove to shift roughly half the existing values over by one in
order to insert the new entry in the middle of a sorted list.

Geoffrey