# Optimal division of a matrix for processing

1. Jul 28, 2009

### sam_wilson

I apologies if this is in the wrong place!!!

I'm a Computer science person with a keen interest in maths and occasionally the two topics cross paths.

I am working on an matrix manipulation package in Java/C but seriously require some help with the maths, I am witting into it, parallelization at the moments and i am looking for a solution to this problem below, Hopefully if there is a method to calculate this in linear time i would be great full, if not a heuristic algorithm will have to do

Given a Matrix NxM find a solution x, y which meets the following constraints

z is a Real Positive Interger which is greater than 0 (Set by some processor loading statistics, not variable and could be treated as a constant)

x * y <= z

x mod n = 0

y mod m = 0

n, m, x, y, z > 0

if there is a solution to this, x,y will be the dimensions of a submatrix which will be able to be processed independently of the rest.

Initially I though this would be a trivial Linear programming solution, But up until yet in my maths career i am unaware of how to express a mod function as a feasibility region. From Some of my scribbles on paper and from some simple benchmarking of the problem in my framework i have discovered that the optimal answer is around the sqrt of z, which is would made scene as so far i have only been trying with square matrices.

This problem if solved would provide a fast way of distributing Matrix multiplication across a cluster.

Last edited: Jul 28, 2009
2. Aug 1, 2009

bump :D

3. Aug 2, 2009

### sam_wilson

Refinement of one of the constraints

(n/x)*(m/y) <= z

N.B

N = n, M = m

4. Aug 2, 2009

Is this really the no brainer, that I think you ask for?

you are looking for multiples of n and m we may call a*n and b*m that fulfill the requirement a*b<=z

So if z>=1 you pick any a < z/2 and b can be chosen as b = z /a

But I think you messed up the modules and you are really looking for: m mod x = 0 This will require prime factorization and you will not find a general linear time algorithm for this.

5. Aug 3, 2009

### sam_wilson

You are correct i did mess up the modulus constraints opps!!!

So is the only solution to this problem factorization?

Thanks