[Octave-bug-tracker] [bug #60818] delaunayn - 2D code path vectorization doesn't match nD algorithm

[Nicholas Jankowski]

Follow-up Comment #51, bug #60818 (project octave):

regarding R, that was the original way of looking for small elements, but was
switched to a volume calculation to make for a consistent check between the
two codepaths.  Getting R is the expensive part (it is essentially a single
vector of the components of the simplex volume before running a prod(R) to get
volume.) the overhead for reshaping and prod() are fairly trivial after
getting R. note in the latest version, both code paths start with the same
edge_vectors form and end with the same volume check.

R could easily be formed in pieces. each simplex has a [dim+1 x dim+1]
edge-vector matrix that is then used to get the volume. old loop used det[x].
LU decomp turns x into R, reducing det(x) into the product of the main diag of
u.  but the block diagonal form makes each simplex independent within LU,
which lets the whole thing be done in one step. arbitrarily picking a portion
of the simplex set, you could easily LU on each one to build R. 

now, how to decide on a memory based partition, and how that relates to input
geometry - i guess we could come up with a simplex count. at 7D, going from 10
> 100 > 1000 input points increases simplex count from 8 > 68E3 > 3E6.  the
latter takes 4.3MB in storage, but the process peaked at <<12GB (switched to
drive swapping) with LU and 3800 with laplace.

    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?60818>

_______________________________________________
  Message sent via Savannah
  https://savannah.gnu.org/