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.

New contributor
Vy Trieu is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
6
  • 5
    $\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 at 22:02
  • 6
    $\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
  • 3
    $\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$ – sssssssssssss 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$ – Amit Hochman 2 days ago

Your Answer

Vy Trieu is a new contributor. Be nice, and check out our Code of Conduct.

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.