Author: Manas Rachh, Flatiron Institute.
This repository contains Fortran90 routines for fast identification of the list of test (target) points contained within each of a given collection of (source) balls, in 2D or 3D. The results are returned in compressed sparse row (CSR) format, ie, indices of balls that contain each target. The algorithm used a hung pruned level-restricted adaptive quad-tree in 2D (or oct-tree in 3D), with OpenMP parallelization.
We present the 2D case (3D is analogous). Given inputs:
s : 2-by-ns array giving centers of source balls in R2
r : length-ns list of radii of source balls
t : 2-by-nt array giving coords of test points in R2
Then calling:
call findnearmem2d(s,ns,r,t,nt,nnz)
allocate(col_ind(nnz))
call findnear2d(s,ns,r,t,nt,row_ptr,col_ind)
Writes out the following:
nnz (written by findnearmem2d) : total number of target-ball pairs found
row_ptr : length-(nt+1) list of start indices in col_ind array for each target
col_ind : length-nnz list of source ball indices intersecting each target
This may be interpreted as the CSR storage of a nt-by-ns
sparse matrix with nnz nonzero entries.
The element (i,j) is nonzero iff target i is within ball j, ie,
within distance r(j) of source j.
The precise task performed may be also understood by reading the naive source
subroutines findnearslowmem2d and findnearslow2d.
Note: the call is split into two routines so that the user may handle the
memory management for the potentially-large col_ind array.
src/2d : 2D source code
src/3d : 3D source code
src/common : sparse matrix format conversion, low-level utilities including by other authors
test : test drivers and makefiles
You need a fortran compiler and GNU make. For non-linux systems please see the makefile and edit the HOST var. Then:
cd test
./testall.sh
should compile and run test2d and test3d. Each reports timing tests vs the naive method (taking around 1 sec to run), and successful completion of test of correctness of indices found.