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@lists.scilab.org
http://lists.scilab.org/mailman/listinfo/users
_______________________________________________
users mailing list
users@lists.scilab.org
http://lists.scilab.org/mailman/listinfo/users
