[Math] Splitting Matrix Into Sub-Matrices With Constraints

linear algebramatrices

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 5×5 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!

Best Answer

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}

Related Question