Memory-Efficient 2D Array Creation for Lower Triangle Matrices

This blog discusses a technique to reduce memory usage while creating lower triangle matrices. The technique involves storing the matrix elements in a single array, with each element’s index calculated based on its row and column position. This can significantly reduce memory usage, as only the non-zero elements of the matrix need to be stored. The technique is also relatively simple to implement, making it a valuable tool for programmers who need to create lower triangle matrices in a memory-efficient way.

A lower triangular matrix is a square matrix in which all the elements above the main diagonal are zero, in the above diagram, all the red portions are zero while the remaining green portions are non-zero elements.

In this blog, we’ll learn how to transform the 2-D matrix to 1-D array and reduce the number of memory blocks which are unused. To do so, we need some kind to formula to transform it, so let’s learn how to implement the formula. First, we’ve to figure out the formula for number of zeros and non-zero’s element in 2-D array.

In the above diagram, in 1st row, we’ve 1 non-zero block. In 2nd row, we’ve 2 non-zero blocks. Likewise for 4th row, we’ve 4 non-zero blocks. Therefore, for n x n array, we’ve 1 + 2 + 3 + 4 + … + n non-zero blocks. This is the series for sum of n natural numbers, so the formula for it is n * (n + 1) / 2.

So, to convert 2D matrix, we’ll use ROW-MAJOR formula, which we’ve learn in previous blog post. In the above diagram, we’ve split the array in different rows, 1st row contains 1 element, 2nd row contains 2 element, likewise nth row contains n element.

For accessing element at A [4][3], we’ve to generate a formula such that it points to index 8. So, let’s generate the formula.

A[4][3] = [1 + 2 + 3] + (3 - 1) = 8

A[3][2] = [1 + 2] + (2 - 1) = 4

General formula,
A[i][j] = [summation of all element till i-1] + (j - 1)

A[i][j] = [1 + 2 + 3 + ... i-1] + (j - 1)
        = [i * (i-1) / 2] + (j - 1)

I hope, you we’ve learn something new from this blog. Do like, share and comment on the blog post. Also, if you’ve some doubt, do comment down the blog, I’ll try my best to answer your questions.