[Scilab-users] Pairwise distance of a huge amount of points

[Ezequiel Soule]

Hi, I am working in something related, which is deteriming overlaps in a 
sistem of spheres with random positions. So I have to compute the 
distance between centers of spheres, and compare it with the contact 
distance. I implemented a cell algorithm, which is used in molecular 
dynamics (you can look it up in internet if you don´t know it): 
essentially you divide the space in "cells", with a size that has to be 
larger than the maximum posible distance, then you identify in which 
cell each point is located, and then you compute the distance between 
each point and the points located in the same and the neigbhouring 
cells. The speed of the algorithm scales with n, and the computed 
distance matrix has n*c*b non-zero elements, where "c" is the average 
number of points in a cell and "b" is the number of neiborghs of each 
cells, plus one. "c*b" might be orders of magnitude smaller than "n" so 
there is a big advantaje in using sparse matrices. I used this with 
hundred thousands spheres without exeding the maximum stacksize.
The only problem is that you need to know the maximum possible distance 
in order to define the cell size (if your cell is to small you can miss 
relevant meassurements, if it is too large, you lose efficiency); I 
don´t know if this is possible in your application.

El 29/08/2014 07:01 p.m., Samuel Gougeon escribió:
> Le 29/08/2014 12:58, Dang, Christophe a écrit :
>> Just to close the subject:
>>
>> I tried to implement the algorithm with sparse matrices, and it is 
>> less efficient than scanning over one dimension: 7 times faster than 
>> the naive algorithm.
> Yes, it was somewhat expected. Also for memory consumption, the sparse 
> encoding becomes interesting vs the dense encoding only when the 
> sparsity becomes smaller than .. 50%.
> There was a quite recent thread on bugzilla, about the relevance of 
> keeping a sparse encoding for the result of cos(SP) where SP is a 
> sparse (so with a good fraction of null values).
> It was finally -- wisely -- decided (after some tests) to switch to a 
> dense encoding for that case (as it should be for any function turning 
> 0 into a non-null value).
>
> Samuel
>
> _______________________________________________
> users mailing list
> users at lists.scilab.org
> http://lists.scilab.org/mailman/listinfo/users