0
$\begingroup$

For solving a linear system,

$Ax = b$.

If $A$ is a dense but symmetric $n \times n$ matrix, how much memory is required?

$A$ is symmetric, which means only the upper (or lower) triangular part of $n \times (n+1)/2$ entries would be necessary. Does $A$'s memory requirement have to be 8 bytes $\times n \times n$ or can it be lowered toward 8 bytes $\times n \times (n+1)/2$?

$\endgroup$
1
  • $\begingroup$ Specifically, you will want to look up the difference between a regular LU decomposition and the Cholesky decomposition that exploits the symmetry of the matrix. $\endgroup$ Nov 7, 2022 at 16:50

1 Answer 1

2
$\begingroup$

It can be lowered; it is called packed storage and Lapack has some functions to deal with it, e.g., ?PPSVX, ?SPSVX.

As this storage scheme is somewhat uncommon, I don't think you can use it easily in higher-level packages such as Matlab or Scipy. There is a Julia package though.

Alternatively, if you have an upper and a lower triangular matrix with known diagonal, such as the results of an LU factorization, you can pack two in the space of one $n\times n$ array.

$\endgroup$
1
  • 1
    $\begingroup$ A small word of caution is that these packed storage routines are slower than the corresponding non-packed ones, as they rely on BLAS-1 routines instead of BLAS-2 or BLAS-3. You might also look into "rectangular packed format", which can achieve BLAS-3 performance without using duplicate storage (though this is easier for some kernels than others). $\endgroup$ Nov 11, 2022 at 20:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.