Recycling a non-contiguous matrix as workspace : Instance of packaging & cutting problem

Abstract: This report explores a common issue in a system involving matrices, namely the mismatch between the allocation and deallocation ratios. This results in more matrices being allocated than deallocated, eventually leading to insufficient memory. The mismatch in the ratio is an implication of how matrices are normally used. A matrix is generally used more than once, requiring them to remain in memory from its initial usage until the final instance. In this thesis, a solution to the problem is presented and then evaluated. The underlying idea behind the solution is to utilize submatrices inside the allocated matrices that we can overwrite, i.e. the information in the submatrix is not needed for further computations. Thus, we can reuse (recycle) the space occupied by the submatrix to store information about other, smaller matrices. This view on the problem creates a strong relation to the class of packaging and cutting problems.