Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a question regarding matrices for a personal project of mine.

I have a large matrix that needs to be split into smaller matrices. I know its dimensions are X and Y. I know that the max amount of elements for each child matrix is E. (EX: A 5x5 matrix has 25 elements).

I want to find where to split the matrix into smaller matrices so that I have as few children matrices as possible and none of them go over element limit E.

The final constraint is that the children need to vertically line up.

1 1 1 1 2 2 2 2
1 1 1 1 2 2 2 2
3 3 3 3 4 4 4 4 
3 3 3 3 4 4 4 4 
3 3 3 3 4 4 4 4

1 1 1 1 2 2 2 2
1 1 1 1 2 2 2 2 
1 1 1 1 2 2 2 2 
3 3 3 3 3 3 3 3 
3 3 3 3 3 3 3 3

So In that example, the first matrix is good because the children line up into the columns, however, the second is not because it breaks up the columns.

Any guidance is greatly appreciated!

Thanks!

share|improve this question

1 Answer 1

up vote 0 down vote accepted

Seems like a simple recursive algorithm will do the job.

Let $c = \min(E,X)$. This is the maximum number of columns allowed in each feasible subblock. For $j=1,2,\ldots,c$, define $m_j=\lfloor E/j\rfloor$. This represents the maximum number of rows allowed in a feasible subblock, provided that the subblock has $j$ columns. Therefore, given that a single column of subblocks has $j$ columns of entries, the minimum possible number of feasible subblocks contained in this slice of the big matrix is $n_j = \lceil Y/m_j\rceil$.

Now, let $N_j$ denotes the minimum number of feasible submatrices when the large matrix has $j$ columns. Then our desired answer, $N_X$, is given by the following recurrence: \begin{align} N_1 &= n_1,\\ N_j &= \min\{N_{j-k}+n_k:\ k=1,2, \ldots,\min(c,\,j-1)\},\ j=2,\ldots,X. \end{align}

share|improve this answer
    
Perfect, thanks! –  John Snow Dec 17 '12 at 18:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.