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?

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Optimal division of a matrix for processing
  1. Matrix Division? (Replies: 5)

  2. What is division? (Replies: 10)

  3. Division for ratios (Replies: 4)