How "sparse" should a sparse matrix be to see benefits?

Question

I have a matrix, whose size scales as $2^N$ (assume even $N$). In each row of the matrix, only about $2^{N/2}$ of the entries are filled ($N$ can be somewhere between 10 and 40, depending on what's feasible computationally). I'm not sure whether using sparse matrices would be suitable for storage and computation - there aren't that many non-zero entries in a relative sense compared to the overall matrix size, but there are still a lot in an absolute sense.

As an additional question, if using sparse matrices is indeed the way to go, what's an approximate order-of-magnitude size for which I could reasonably solve systems of linear equations, i.e. $Ax=b$, with a direct solver? I, unfortunately, don't have a good sense of what sort of size is reasonable, and this influences whether the method of solving the problem I'm considering is even remotely feasible (the exact number, of course, depends on the resources I have available - I was wondering in a more general sense what this dependency between size and resources/time was like, but specific examples would also be helpful, i.e. how big of a system size I could do on an average desktop in a few hours).

Answer 1

This kind of scaling is fairly common and sparse direct factorization methods are commonly used on matrices of up to a few hundred thousand rows and columns. By the time you get to $N=20$, you’ll have a million rows with a thousand nonzero entries per column. This is getting into the range where sparse direct factorization becomes impractical and you’ll need to look at iterative methods.

At $N=20$, you would need about 10 gigabytes to store your matrix in double precision, which should be no problem on a contemporary PC. However, by the time you get to $N=40$, you would need about 10^19 bytes of storage, which is beyond the capacity of current supercomputers.

Answer 2

This really comes down to what methods you are intending to use. If you store the matrix dense then you will use dense factorization routines, the cost of which will scale cubically with the matrix size, and so $2^{3N}$ for your case. That limits the $N$ dramatically, even on today's best supercomputers.

You might be able to push this slightly further with a sparse representation and a direct solver, but based on your comment about how many nonzeros you have per row I highly doubt a sparse direct solver will really outperform a dense one. The reason is that sparse direct solvers will try and compute fill-reducing reorderings of your unknowns and equations, but this becomes less effective with less sparse matrices. I suspect that in the end, even with an optimal reordering in your case, the resulting factorization will still be completely dense, and so leaving us with the same limitations as the dense case.

With the above comments in mind we might consider iterative solvers like GMRES. The primary barrier in these methods for your case isn't computational cost, but memory. These will scale significantly better than the direct solvers mentioned above, but rarely work in a black-box fashion. You can try it black-box first to see if it works, but experience suggests it will not converge for larger $N.$

To fix this you will need some preconditioner. There are a few black-box preconditioners to choose from that might work, but this requires some experimentation to find out. As a rule of thumb, a good preconditioner will take about as much memory to store as the matrix does itself. Thus in this case it might make sense to store your matrix sparse in order to make more space for preconditioners in memory. Also most available black-box preconditioners require you to have your matrix in a sparse format anyways, so if you don't want to rewrite those yourself a likely next step is to transition into a sparse format.

This is leaving out some other questions that might impact what you do: like how much memory you actually have available. (as suggested by comment: take "memory" here to mean whatever storage you are using, whether it be DRAM, Burst Buffer, Disk,... )