# Invert a huge sparse operator;

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.

• 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? Jul 19 at 22:02
• 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)? Jul 19 at 22:14
• Just to double check - the elements of the diagonal matrix are not all the same? Jul 20 at 7:10
• 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). Jul 20 at 10:31
• 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. Jul 20 at 19:11