1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Optimal division of a matrix for processing

  1. Jul 28, 2009 #1
    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. jcsd
  3. Aug 1, 2009 #2
    bump :D
  4. Aug 2, 2009 #3
    Refinement of one of the constraints

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


    N = n, M = m
  5. Aug 2, 2009 #4
    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.
  6. Aug 3, 2009 #5
    You are correct i did mess up the modulus constraints opps!!!

    So is the only solution to this problem factorization?

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook