How can I initialize vector containing around 300000 vectors of size around 300000

Question

In my implementation of some equation I need to build a NXN diagonal matrix.I'm using vector of vectors for representing matrices. However the N is around 300000 so,

std::vector<std::vector<double> > new_matrix(300000,std::vector<double>(300000,0)) 

on running, gives me

terminate called after throwing an instance of 'std::bad_alloc'

  what():  std::bad_alloc

Is this not possible due to memory limit?

Answer 1

The question can be answered generally: Dealing with large amounts of data in c++

In your case,

The error is due to insufficient contiguous heap memory for a

300,000 * 300,000 vector of double precision floating point numbers.

Maybe, a different container could be preferred that does not need contiguous memory like std::list. But wait, what would be the amount of memory needed for this?

300000 * 300000 * sizeof(double) =

300000 * 300000 * 8 =

720000000000 bytes =

703125000 KB =

686646 MB =

671 GB!

Unless you are working with a supercomputer, forget about this idea.

Back in the olden days, programmers had to come up with clever solutions to work within the limits of tiny RAM. Why not do it today? Let's start by digging patterns in your problem. You are working with a

Diagonal matrix:

A matrix having non-zero elements only in the diagonal running from the upper left to the lower right

Therefore, you do not have to store the non-diagonal elements in the memory because it is guaranteed that those elements are 0. So the problem boils down to storing just the main diagonal elements (matrix[0][0], matrix[1][1],... matrix[n-1][n-1]), a total of n elements only. Now you can consider just 300000 elements, which is way shorter than 90000000000!

Calculating the memory for this:

300000 * sizeof(double) =

300000 * 8 =

2400000 bytes =

2344 KB =

2.3 MB!

As you can see, this approach has reduced our requirement from 670 GB to just 2 MB. It might still not work on some stack memory but it doesn't matter because we are dealing with heap memory (std::vector is a dynamic array).

Now that we have reduced the space complexity, it is just a matter of implementing this logic. But be careful to maintain this convention throughout while accessing, traversing, and storing the array.

For example:

#include <iostream>
#include <vector>

typedef std::vector<double> DiagonalMatrix;

int main()
{
    // std::vector<std::vector<double>> new_matrix(300000, std::vector<double>(300000, 0));
    DiagonalMatrix m(300000, 0);

    // Store the main diagonal elements only

    // Keep this convention in mind while using this implementation of DiagonalMatrix

    return 0;
}

Edit:

To demonstrate this design and after your request in the comments, below is an implementation of the necessary logic:

// Product = DiagonalMatrix * Matrix
Matrix DiagonalMatrix::preMultiply(Matrix multiplier)
{
    // Check if multiplication is possible
    if (multiplier.r != this->n)
        return Matrix();

    // Product is the same as the multiplier where
    // every element in the ith row of the multiplier is
    // multiplied by the ith diagonal element of the diagonal matrix
    Matrix& product = multiplier;
    for (int i = 0; i < multiplier.r; ++i)
    {
        for (int j = 0; j < multiplier.c; ++j)
        {
            product.m[i][j] *= this->m[i];
        }
    }
    return product;
}

// Product = Matrix * DiagonalMatrix
Matrix DiagonalMatrix::postMultiply(Matrix multiplier)
{
    // Check if multiplication is possible
    if (multiplier.c != this->n)
        return Matrix();

    // Product is the same as the multiplier where
    // every element in the jth column of the multiplier is
    // multiplied by the jth diagonal element of the diagonal matrix
    Matrix& product = multiplier;
    for (int j = 0; j < multiplier.c; ++j)
    {
        for (int i = 0; i < multiplier.r; ++i)
        {
            product.m[i][j] *= this->m[j];
        }
    }
    return product;
}