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.
Library for solving a linear selection problem in a distributed memory machine
algorithms;c++;mpi;library
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.pdfThe algorithm described there has complexity $O\left(\frac NP \log_2 P\right)$. The code has only some 20 lines.