turbocor
This is little program designed to compute (sparse) Pearson correlation matrices as efficiently as possible.
The main ideas are thus:
- Pairwise correlations computed using AVX2 and FMA instructions.
- Multithreading, of course.
- Save space by discarding correlations with absolute value below some threshold. (Hense, "sparse" correlation matrix.)
- Use constant space and avoid thread contention and overhead from reallocation by using thread local buffers which are dumped to a temporary file when full.
- Find the top-
kcorrelations using partial sort takingO(n^2 + k log(k))time, rather than full sort takingO(n^2 log(n))time.
Combined, this lets you compute a correlation network in ~10min and 10GB memory that would ordinary take a day and hundreds of GBs.
Usage
There are two subcommand: compute computes the sparse correlation matrix, and topk does a partial sort of that matrix to find the top-k correlations by absolute value.
Compute sparse correlation matrix (rounding entries with absolute value below 0.7 to zero). Features are expected to be in hdf5 format in a dataset determined by the --dataset argument.
turbocor compute --lower-bound 0.7 --dataset "some_interesting_data" features.h5 correlations.h5
Write the top-k correlations in comma delimited format to standard output:
turbocor topk 1000 correlations.h5 > topk-correlations.csv
Possible improvements
The most obvious way to make this even faster to is to compute pairwise correlations on a GPU. A less obvious way would be to try to tweak the order matrix entries are computed in to improve data locality.
9 Oct 10, 2022
103 Dec 12, 2022
123 Nov 20, 2022
45 Jan 3, 2023
17 Dec 13, 2021
9 Sep 28, 2022
2 Sep 26, 2021
9 Apr 8, 2022
2 May 2, 2022
5 Aug 20, 2022
3 Nov 2, 2023
5 Dec 5, 2022
4 Oct 24, 2022
5 May 2, 2024
3 Jan 3, 2023
776 Jan 1, 2023
14.1k Jan 4, 2023
12.2k Dec 30, 2022
9 Dec 7, 2022