Memory usage of decomposition

Hello,

Consider linear systems Ax=b_i with A sparse and positive definite and several right hand sides b_i. In the experiments I have done, it is faster to use

dA = decomposition(A,'chol','upper');
x_i = dA\b_i; % repeat as needed

than the classical

R = chol(A);
x_i=R\(R'\b_i); % repeat as needed

But dA occupies much more memory than R

n = 1e5;d = 1e-5;rc = 1e-5;
A=sprand(n,n,d,rc);
A = A+A'+10*speye(n,n);
R = chol(A);
dA = decomposition(A,'chol','upper');
memR = whos("R"); memR = memR.bytes;
memdA = whos("dA"); memdA = memdA.bytes;
fprintf(' R occupies %.1e bytes.\ndA occupies %.1e bytes\n',memR,memdA)

 R occupies 5.6e+06 bytes.
dA occupies 1.5e+07 bytes

Any idea of why? Any solution?

Thanks,

Mariano

[Walter Roberson]

dA is only about 2.7 times the size of R. I do not see that as being a significant difference.

[Walter Roberson]

A couple of levels down, the decomposition has a field named cholmod_ which is matlab.internal.decomposition.builtin.CHOLMODWrapper . The wrapper has a few properties, one scalar double and one empty, and one an exact copy of the OriginalMatrix (sparse where the original was sparse.)

The copied OriginalMatrix has the same size as the original matrix (A); add to that a scalar and an empty and the total should be less than 500 bytes larger than the original matrix. But instead it is about 2.7 times the original matrix.

The only conclusion is that matlab.internal.decomposition.builtin.CHOLMODWrapper is not a pure MATLAB class and instead has hidden internal attributes that point into a block of memory.

[Mariano]

Thanks for the answer.

In my case, multiplting the size by 2.7 is a significant difference, since I am working on a project with lots of big sparse matrices, and I am at the edge of the avalaible RAM. So the speed up gained by decomposition would be completely spoiled by the IO to the virtual memory on the hard drive.

For this, I will keep using good old \.

[Walter Roberson]

If you are up against the system RAM limits, then install a fast SSD and configure it as the paging drive.

Google's AI describes this method for Windows:

• Open the Start menu and click Run
• Type sysdm
• Click the Advanced tab
• In the Virtual Memory section, click Change
• Uncheck Automatically manage paging file size for all drives
• Select the drive that contains your paging file
• Select Custom Size
• Enter the initial and maximum size of your page file
• Click Set and confirm with OK
• Reboot your system

[Mariano]

Thanks for the tip!

[Christine Tobler]

The number of bytes returned by whos isn't always reliable, since it will count arrays that share memory multiple times (see below). I would trust the system's memory indicator more than the whos command. For example:

>> A = randn(1000);
>> B = A;
>> s.A = A; s.B = A;
>> whos
Name         Size                 Bytes  Class     Attributes

A         1000x1000             8000000  double              
B         1000x1000             8000000  double              
s            1x1               16000274  struct   

The whos command would have you think we're using 32 MB of RAM - but in fact, all of these are shared copies and we only allocated significant memory once, for A.

For the internal object using more memory than its properties require, this is because it's storing an object from an external library, which can't be represented in MATLAB directly. The byte-count told to us by that third-party library is shown by whos.

Note that this same object is also used inside of mldivide, and gets destroyed at the end of the mldivide command. So whether to use mldivide or decomposition is a question of if you can afford to keep this memory allocated for a longer time, not if you can afford to allocate it in the first place.

Answer 1

[Umar]

Hi @Mariano,

When dealing with large sparse matrices in numerical computing, especially in environments like MATLAB, it is crucial to understand both the computational efficiency and memory implications of various algorithms. Here’s a detailed breakdown of the situation:

1. Performance Comparison: The two methods being compared are:

Method 1:Using `dA = decomposition(A,'chol','upper'); x_i = dA\b_i;` Method 2:Using classical Cholesky factorization `R = chol(A); x_i=R\(R'\b_i);`

In your experiments, Method 1 appears faster for repeated solves against multiple right-hand sides b_i. This is likely due to the efficiency of reusing the decomposition stored in `dA`, which is optimized for repeated operations.

2. Memory Usage: You reported that `dA` occupies approximately 1.5 \times 10^7 bytes while R only takes up 5.6 \times 10^6 bytes. This difference (approximately 2.7 times more memory) can be attributed to several factors:

Internal Representation:The `decomposition` function utilizes a wrapper class (`cholmod_`), which may include additional metadata or structures that are not present in the simple Cholesky factorization. This wrapper likely maintains references to the original matrix and other necessary data for efficient computations.

Sparse Matrix Handling: While both methods work with sparse matrices, the internal representation used by `decomposition` might lead to increased overhead due to maintaining extra structures necessary for its optimizations.

3. Implications on Large Scale Problems:

As you noted, working with large matrices close to system RAM limits can lead to performance degradation if excessive paging occurs. If MATLAB begins to use virtual memory (swapping data to disk), it can severely impact performance despite any gains from faster algorithms.

Given your constraints and requirements, here are some strategies you could consider:

Stick with Classical Cholesky: If memory usage is a critical concern and you have confirmed that classical Cholesky is sufficiently fast for your needs, it may be prudent to continue using this method despite its longer execution time per solve.

Optimize Memory Usage: Investigate whether you can reduce the size of your matrices or break them into smaller blocks if applicable. Ensure that other processes consuming RAM are minimized during your computations.

Upgrade Hardware: As suggested by Walter Roberson, installing a fast SSD could help alleviate some issues related to virtual memory usage by improving data access speeds when paging occurs.

Parallel Computing: If applicable, consider using MATLAB's parallel computing toolbox to distribute computations across multiple cores or even machines, which can help mitigate some of the RAM limitations by processing chunks of data independently.

Profiling and Debugging: Use MATLAB’s profiling tools (`profile on`, `profile viewer`) to analyze where most memory is being consumed during execution. This may provide insights into optimizing your code further.

Hope this helps.