DEV Community

Anmol Jindal
Anmol Jindal

Posted on • Originally published at Medium on

C++ Matrix Compression: Reduce Memory Usage by 90% with Smart 1D Storage

#matrixstructure #cpp #math #compression


Photo by HarrisonBroadbent on Unsplash

The majority of matrices in the real world contain more than just random numbers. They contain repeated values or big blocks of zeros. However, a lot of people store them as full 2D arrays, which wastes CPU cache and RAM and degrades performance, particularly when used on a large scale.

For example , even though only 100 integers are truly important, an int mat[100][100] allocates 10,000. This results in the waste of speed and memory.

The solution? Storing only the meaningful elements in a 1D array using smart indexing. This increases the speed of your code and compresses memory by up to 90%+.

Here is the complete working code → MatrixOptimizedADT GitHub Repo

Matrix Types & How to Compress Them

Here are common matrix types and the strategies to store them efficiently.

1. Diagonal Matrix

  • Structure: Non-zero elements exist only on the main diagonal (where row index i equals column index j).
  • Storage Size: n
  • Compression Idea: Since only n diagonal elements matter, just store those n elements in a 1D array.

2. Lower Triangular Matrix

  • Structure: Non-zero elements are on and below the main diagonal (where i >= j).
  • Storage Size: n(n+1)/2
  • Compression Idea: Store the elements row-by-row (row-major order).

3. Upper Triangular Matrix

  • Structure: Non-zero elements are on and above the main diagonal (where i <= j).
  • Storage Size: n(n+1)/2
  • Compression Idea: Store the elements column-by-column (column-major order).

4. Symmetric Matrix

  • Structure: The element at A[i][j] is equal to the element at A[j][i].
  • Storage Size: n(n+1)/2
  • Compression Idea: You only need to store either the lower or upper triangular part. The other half can be derived.

5. Tridiagonal Matrix

  • Structure: Non-zero elements are only on the main diagonal, the one above it, and the one below it.
  • Storage Size: 3n - 2
  • Compression Idea: Store these three diagonals as three separate sections within one array.

6. Toeplitz Matrix

  • Structure: Elements are constant along each descending diagonal (A[i][j] depends on i - j).
  • Storage Size: 2n - 1
  • Compression Idea: You only need to store the first row and the first column to reconstruct the entire matrix.

The Math Behind Compression: Why These Indexing Formulas Work

Let’s break down the logic behind the formulas that let you store only what matters in 1D arrays:

1. Diagonal Matrix

Only n elements matter , the diagonal entries where i == j. So store them in a 1D array of size n, and index with arr[i-1].

2. Lower Triangular Matrix

Non-zero elements lie where i >= j. The number of such elements is the sum of the first n natural numbers: n(n+1)/2.

Indexing formula:

// Lower Triangular Matrix indexing
int index = (i * (i - 1)) / 2 + (j - 1);
Enter fullscreen mode Exit fullscreen mode

This counts how many elements are in all rows before i plus the position in the current row.

3. Upper Triangular Matrix

Here non-zero elements lie where i <= j. We store column-wise:

// Upper Triangular Matrix indexing
int index = (j * (j - 1)) / 2 + (i - 1);
Enter fullscreen mode Exit fullscreen mode

Same logic but transposed.

4. Symmetric Matrix

Since A[i][j] =A[j][i] , we will only store the lower triangle (or upper). If i < j, swap indices to access the stored half:

// Symmetric Matrix indexing (store lower triangle only)
if (i < j) std::swap(i, j);
int index = (i * (i - 1)) / 2 + (j - 1);
Enter fullscreen mode Exit fullscreen mode

5. Tridiagonal Matrix

Non-zero elements are on main diagonal, plus one above and one below. We can store three arrays concatenated in one:

  • Lower diagonal: indices 0 to n-2
  • Main diagonal: indices n-1 to 2n-2
  • Upper diagonal: indices 2n-1 to 3n-3 
// Tridiagonal Matrix indexing
if (i == j)
    index = (n - 1) + (i - 1);
else if (i == j + 1)
    index = i - 2;
else if (i == j - 1)
    index = (2 * n - 1) + (i - 1);
else
    index = -1; // invalid
Enter fullscreen mode Exit fullscreen mode

Indexing adjusts to which diagonal you’re accessing.

6. Toeplitz Matrix

Each descending diagonal has the same value, So store the first row and first column without duplicating the [1][1] element.

// Toeplitz Matrix indexing
int index = (i <= j) ? (j - i) : (n + i - j - 1);
Enter fullscreen mode Exit fullscreen mode

Memory Efficiency : Navie vs Compressed

Matrix Type Naive Storage Compressed Storage Memory Reduction
Diagonal n^2 n ~99%
Lower/Upper Triangular n^2 n(n+1)/2 ~50%
Symmetric n^2 n(n+1)/2 ~50%
Tridiagonal n^2 3n - 2 ~97%
Toeplitz n^2 2n - 1 ~98%

C++ Implementation

Instead of showing you repeated code, here’s the full Diagonal class implementation and an example for Lower Triangular focusing on the indexing difference:

class Diagonal {
private:
    int n;
    int* arr;
public:
    Diagonal(int n) : n(n), arr(new int[n]()) {}
    void set(int i, int j, int val) {
        if (i == j) arr[i - 1] = val;
    }
    int get(int i, int j) {
        return (i == j) ? arr[i - 1] : 0;
    }
    void display() {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                std::cout << get(i, j) << (j == n ? "\n" : " ");
            }
        }
    }
    ~Diagonal() { delete[] arr; }
};
Enter fullscreen mode Exit fullscreen mode

Lower Triangular indexing formula difference:

int index(int i, int j) {
    return (i * (i - 1)) / 2 + (j - 1);
}
Enter fullscreen mode Exit fullscreen mode

Final Words

If your codebase still stores full 2D arrays for structured matrices, you’re wasting memory and CPU cycles unnecessarily. Matrix compression is a foundational skill for system design, competitive programming, and interviews.

Clone the MatrixOptimizedADT GitHub Repo, experiment with the code, and contribute new matrix types or features.

About the Author

Hey, I’m Anmol aka TimelessRecall

Follow me here:

Top comments (0)