Optimal division of a matrix for processing

Click For Summary

Discussion Overview

The discussion revolves around the mathematical problem of optimally dividing a matrix for processing, specifically focusing on finding dimensions for a submatrix that can be processed independently. The context includes aspects of parallelization and matrix manipulation in programming, with an emphasis on constraints involving modular arithmetic and optimization techniques.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant describes the problem of finding dimensions x and y for a submatrix under specific constraints, including modular conditions and a limit based on processor loading statistics.
  • Another participant suggests that the problem may involve finding multiples of n and m that satisfy the inequality a*b <= z, proposing a method to choose a and b based on z.
  • A later reply questions the correctness of the modulus constraints, suggesting that the correct condition might involve m mod x = 0 instead of y mod m = 0.
  • There is a mention of the potential need for prime factorization to solve the problem, with a participant expressing uncertainty about whether this is the only solution.

Areas of Agreement / Disagreement

Participants express differing views on the approach to solving the problem, particularly regarding the modulus constraints and the necessity of factorization. The discussion remains unresolved with multiple competing ideas presented.

Contextual Notes

Participants note the complexity of expressing modular functions as feasibility regions, and there is uncertainty about the existence of a linear time algorithm for the problem. The discussion also highlights the need for clarification on the constraints involved.

sam_wilson
Messages
4
Reaction score
0
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:
Physics news on Phys.org
bump :D
 
Refinement of one of the constraints

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

N.BN = n, M = m
 
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.
 
You are correct i did mess up the modulus constraints opps!

So is the only solution to this problem factorization?


Thanks
 

Similar threads

Undergrad Un-skewing a skew symmetric matrix (for want of a better phrase)
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Proof for subgroup -- How prove it is a subgroup of Z^m?
  • · Replies 11 ·
Replies
11
Views
3K
Graduate How to augment a machine learning matrix?
  • · Replies 10 ·
Replies
10
Views
3K
Undergrad What is the size of the quotient group L/pZ^m?
  • · Replies 1 ·
Replies
1
Views
2K
Graduate Displacement-Rotation Algorithm
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Passive Transformation and Rotation Matrix
  • · Replies 1 ·
Replies
1
Views
4K
Undergrad DSP: Recurrence Relations in a Linear Algebra Equation
  • · Replies 1 ·
Replies
1
Views
2K
Graduate Elementwise Derivative of a Matrix Exponential
  • · Replies 2 ·
Replies
2
Views
3K
Undergrad What Does the F Matrix Look Like for a Linear Bezier Curve?
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Dimension and solution to matrix-vector product
  • · Replies 4 ·
Replies
4
Views
3K