Is there an efficient way of (numerically) solving a linear system, where the matrix is a sum of circulant and diagonal matrices? I need to solve a linear system of the form
(V+D)x=y
where
V is a circulant matrix, symmetric, positive definite, and invertible, but with eigenvalues spanning a wide range.
D is a diagonal matrix, the values on the diagonal varying between 0 and 1.
Either component can be easily inverted, D directly and V using Fourier technique, but their sum is not. I do get a solution via conjugate-gradient iteration, with V+I as preconditioner, but the convergence is painfully slow (without preconditioning it is horrible). I would need to solve this kind of system for thousands of times, with V always staying the same but D and y changing. The size of the matrix is of the order of 10^5.
Is there a general technique for solving this kind of linear systems, or alternatively, can someone suggest a better preconditioner?