# Library for solving a linear selection problem in a distributed memory machine

I need to solve a very large O(10^10) linear selection problem in a distributed memory machine, is there any library that will solve it for me?

In shared memory machines, e.g. std::nth_element does it in average O(n) but deterministic O(n) algorithms also exist. I could live with something worse as long as it's easy to implement. I would also prefer for it to work on input iterator/input ranges than to have linear complexity in order to save memory. I have a dataset that I want to postprocess and then use as input to the linear selection algorithm, it would be better if I could do it "on the fly". I also only want to solve the linear selection problem for certain values, and wouldn't care to solve it multiple times, once for each value.

• Can you give us an order of magnitude for $n$? – Bill Barth Mar 26 '13 at 20:37
• The baseline algorithm to beat would be a short-circuited distributed-memory sort. You would be paying at extra $\log n$ factor though. – Jack Poulson Mar 26 '13 at 22:23
• @BillBarth the order is O(10^10). – gnzlbg Mar 27 '13 at 7:52
• @JackPoulson for the sort do I need to have all my values in memory? The point is that input iterators/ranges are one-way passes (you can't go back). However if I need to have everything in memory I can construct a random-access range from the input range. – gnzlbg Mar 27 '13 at 7:55
• Do you mean that each process would have a one-way iterator which allows for traversal over a subset of the list? – Jack Poulson Mar 27 '13 at 13:33

## 1 Answer

I think you want to take a look at section 5.1 of this one of my papers: http://www.math.tamu.edu/~bangerth/publications/2010-distributed.pdf

The algorithm described there has complexity $O\left(\frac NP \log_2 P\right)$. The code has only some 20 lines.