3
$\begingroup$

please help me with this question, I want to invert a huge sparse (non-circulant) this below in a $Ax=y$ equation:

$$(\lambda I+ \beta D+ \sigma C)x=y$$ where I is an Identity Matrix,D is a Diagonal Matrix,C is a circulant Matrix and $\lambda$, $\beta$, $\sigma $ are positive constants.

And all have the same size of 10000x10000 (in fact it could be much larger because I calculate for processing an image the size of 1000 x 1000, so my matrix will be 1000000x1000000).

I did with scipy solver and the inversion is applicable only for image size of 100x100, which means 100000x100000 matrix.

Improve this question
$\endgroup$
6
  • 6
    $\begingroup$ Your choice of words suggests that you seek to compute the inverse matrix of a large sparse matrix. Your notation suggests that you only need to solve a sparse linear system. You will surely run out of memory in the first case, but you have a fair chance of success in the second case. Do you really need the inverse matrix? $\endgroup$
    – Carl Christian
    Jul 19, 2021 at 22:02
  • 7
    $\begingroup$ Basic questions: do you really want to invert the matrix, or rather solve a linear system? Moreover, are you able to solve the sparse circulant matrix efficiently (e.g. cia FFT)? $\endgroup$
    – davidhigh
    Jul 19, 2021 at 22:14
  • $\begingroup$ Just to double check - the elements of the diagonal matrix are not all the same? $\endgroup$
    – Ian Bush
    Jul 20, 2021 at 7:10
  • 4
    $\begingroup$ If you have a relatively small number of $y$'s to solve for, your best bet is likely iterative solution of the system via something like the conjugate gradient (CG) method or GMRES. Each matrix-vector product required by the iterative solver can be computed in $\mathcal{O}(N\log N)$ time by adding together the results of multiplication of the vector with the two scaled diagonal matrices and the result of the FFT-accelerated application of the circulant matrix (see Wikipedia's entry on circulant matrices for details). $\endgroup$
    – coolguy1000000
    Jul 20, 2021 at 10:31
  • 2
    $\begingroup$ These problems are notoriously difficult. As mentioned by @sssssssssssss, an iterative method seems to be the way to go, but the eigenvalues are usually not clustered and preconditioning is essential. Preconditioners for these problems have been investigated (e.g., sciencedirect.com/science/article/pii/S0377042716303028) but results aren’t great in my experience. $\endgroup$
    – Amit Hochman
    Jul 20, 2021 at 19:11

0

Reset to default

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.