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.

$\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$ Jul 19 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 at 22:14
  • $\begingroup$ Just to double check - the elements of the diagonal matrix are not all the same? $\endgroup$
    – Ian Bush
    Jul 20 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$ Jul 20 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$ Jul 20 at 19:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.