Optimal division of a matrix for processing

[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.

 

[sam_wilson]

bump :D

 

[sam_wilson]

Refinement of one of the constraints

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

N.BN = n, M = m

 

[0xDEADBEEF]

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.

 

[sam_wilson]

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

So is the only solution to this problem factorization?


Thanks