# Split matrix by groups of columns but *capture all combinations of X columns* for some X

Say I have a big matrix, ~50000 rows, ~80000 columns. I want to split it up and solve subproblems on different machines (horizontal scaling).

But I need to make sure every column can be combined with every other column.

Thinking about, I can't really think of an efficient algorithm that could split the matrix up and still do all combinations, without the cost of i/o overcoming the benefits of splitting the problem up. I am sure this is a solved problem, does anyone know how to do this?

• if someone could add tag "distributed-computing" or "horizontal-scaling" that'd be great. Nov 7, 2022 at 19:25
• I don't think I understand the problem statement yet. I'm not sure quite what "capture all combinations" or "every column can be combined with every other column" mean, exactly. Can you define the problem more precisely? Define what kind of split is allowed, and what precisely are the conditions for a split to be acceptable? Perhaps you can define those conditions using mathematics?
– D.W.
Nov 7, 2022 at 21:26

## 1 Answer

I am not sure what you mean by "combining" exactly. I assume you want the parallel threads to have read and write access to all data without maintaining multiple copies.

I have dealt with a similar problem while working with large networks in a GPU environment (for doing multi-device scaling), this answer will be apt for CUDA environment, but I am sure OMP and MPI have similar mechanisms.

CUDA supports unified memory where the i/o overhead is managed at the backend. So, a simple solution is to use cudaMallocManaged to initiate unified memory and allocate the whole matrix in it. Now each GPU connected to the CPU can access all of the data available at this location. Naturally, lesser the amount of conflicted accesses (resulting in race conditions and page faults), better the performance. There are also some cudaMemAdvice flags to tell the compiler if the shared data is going to be read mostly or written mostly.

• thanks, I mean combining columns of the matrix - for an easy assumption - assume we need to run all combinations of X columns...so if there are N total columns, we need N choose X combinations. Nov 7, 2022 at 21:56
• Right, then I guess the above memory pool idea would work. It will not be a good idea to partition columns as you are trying to break a strongly connected hypergraph! Nov 9, 2022 at 3:30