# Reason for why apparent acceleration of algebraic multigrid solve by addition of positive definite diagonal matrix

In passing I was told by someone that $$K^{\prime}\in\mathbb{R}^{n\times n}$$, will be easier to solve by an algebraic multigrid preconditioned conjugate gradient (CG-AMG) solver than $$K$$, where $$K$$ is a discretized elliptic (2nd order) differential operator, that is symmetric positive definite, and \begin{align*} K^{\prime}=K+D, \end{align*} where $$D$$ is a positive definite diagonal matrix. For an example problem, I have observed that solving $$K^{\prime}x=b$$ consistently requires less CG-AMG iterations than the CG-AMG iterations for solving $$Kx=b$$.

I would like to understand why this is the case. So please, if you understand why this is the case I would appreciate your input.

$$\textbf{Update -- following discussion in comments}$$ with lightxbulb.

\begin{align*} \lambda_{\text{min}}(K^{\prime})=\min_{x\in\mathbb{R}^{n},\|x\|_2=1} (x^{\top}K^{\prime}x)=y^{\top}K^{\prime}y, \end{align*}

here $$y\in\mathbb{R}^{n}$$ is a unit length vector which satisfies $$y^{\top}K^{\prime}y=\lambda_{\text{min}}(K^{\prime})$$. Furthermore

\begin{align*} y^{\top}K^{\prime}y\geq y^{\top}Ky\geq\min_{x\in\mathbb{R}^{n},\|x\|_{2}=1}x^{\top}Kx=\lambda_{\text{min}}(K), \end{align*}

so that $$\exists \epsilon_{2}\geq 0$$, such that $$\lambda_{\text{min}}(K^{\prime})=\lambda_{\text{min}}(K)+\epsilon_{2}$$.

Similarly

\begin{align*} \lambda_{\text{max}}(K)=\max_{x\in\mathbb{R}^{n},\|x\|_{2}=1}x^{\top}Kx=z^{\top}Kz \end{align*}

\begin{align*} z^{\top}Kz\leq z^{\top}K^{\prime}z\leq\max_{x\in\mathbb{R}^{n},\|x\|_{2}=1}x^{\top}K^{\prime}x=\lambda_{\text{max}}(K^{\prime}) \end{align*}

so $$\exists \epsilon_{1}\geq 0$$, such that $$\lambda_{\text{max}}(K^{\prime})=\lambda_{\text{max}}(K)+\epsilon_{1}$$, finally

\begin{align*} \kappa(K^{\prime})=\frac{\lambda_{\text{max}}(K^{\prime})}{\lambda_{\text{min}}(K^{\prime})}=\frac{\lambda_{\text{max}}(K)+\epsilon_{1}}{\lambda_{\text{max}}(K)+\epsilon_{2}} \end{align*}

• It changes the condition number of the matrix, note that the result is not the same once you do this. Let's take a simple example: $-\Delta u = \frac{f}{\tau}$ and set $D = \frac{1}{\tau}I$ then you get something like $(-\Delta + \frac{1}{\tau}I)u = \frac{f}{\tau}$. The latter can be rewritten as $\frac{u-f}{\tau} = \Delta u$, i.e. time implicit diffusion for time $\tau$. It is similar to solving $\partial_t u = \Delta u$ with initial condition $u(0) = f$ and computing the solution at time $\tau$. It's clear that this takes fewer iterations for small $\tau$ compared to $\tau \to \infty$. Oct 7 at 16:24
• If $K$ is symmetric positive (semi-) definite, the condition number is $\kappa = \lambda_{\max}/\lambda_{\min}$. Now let $v_i$ be the unit eigenvector of $K$ corresponding to $\lambda_i$. Then it is the eigenvector of $K'$ corresponding to the eigenvalue $\lambda_i + \epsilon$: $K' v = (K+\epsilon I)v_i = \lambda_i v_i + \epsilon v_i = (\lambda_i + \epsilon) v_i$. It is clear that $\frac{\lambda_{\max}}{\lambda_{\min}} \geq \frac{\lambda_{\max}+\epsilon}{\lambda_{\min}+\epsilon}$. The smaller $\lambda_{\min}$ and the larger $\epsilon$ the more this helps, but it foesn't solve the same problem. Oct 7 at 17:27
• How did you get $\kappa(K') = (\lambda_{\max} + \epsilon_1) / (\lambda_{\min} + \epsilon_2)$?; Oct 7 at 23:38
• Ok, I think I get what you meant. Let's pick an extremely simple example with $D = \operatorname{diag}(\vec{\epsilon})$ and $A= \operatorname{diag}(\vec{\lambda})$. Then I can modify any of the eigenvalues of $A$ to increase them by different amounts. Notably this means that I can also make the condition number worse. The bigger problem though is that any such addition of $D$ regardless whether it is $\epsilon I$ or with varying coefficients, modifies the problem that you are solving. I would suggest picking a preconditioner or better solver. Or checking why you get close to singular matrices. Oct 8 at 0:03
• I don't believe it is specigic to AMG, but I could be wrong. My understanding is that $D=\epsilon I$ can change the condition number to be smaller, so it will help any iterative solver. An arbitrary $D$ can make the condition number worse, so I wouldn't recommend it. Oct 8 at 0:10

The computation in your update does most of the work towards a solution. You just need to note that $$\frac{\varepsilon_1}{\varepsilon_2} \leq \frac{\max D_{ii}}{\min D_{ii}} = \kappa(D)$$, and that $$\kappa(K^{\prime})=\frac{\lambda_{\text{max}}(K)+\epsilon_{1}}{\lambda_{\text{min}}(K)+\epsilon_{2}}$$ lies in the segment that joins $$\kappa(K) = \frac{\lambda_{\text{max}}(K)}{\lambda_{\text{min}}(K)}$$ and $$\frac{\epsilon_1}{\epsilon_2}$$. Hence if you are summing a diagonal matrix with $$\kappa(D) \leq \kappa(K)$$ then you are always improving the condition number.
• Indeed the condition $\kappa(D)<\kappa(K)$ guarantees an improvement. I believe the weight for the linear combination $(1-c)\kappa(K) + c\frac{\epsilon_1}{\epsilon_2} = \kappa(K')$ is $\frac{\epsilon_2^2}{\epsilon_2^2+\lambda_{\min}\epsilon_2^2}$ so it is indeed a convex linear combination. Do you know how to write $\epsilon_1, \, \epsilon_2$ in terms of $K$ and $D$ explicitly? Clearly $\epsilon_1 = \lambda_{\max}(K')-\lambda_{\max}(K)$ but I was wondering whether there is something more specific. Oct 9 at 11:53
• I doubt there is more you can do for understanding $\epsilon_{1}$ and $\epsilon_{2}$ in terms of $K^{\prime}$ and $K$ unless you know more details about these matrices. Oct 10 at 16:33
• Another aspect about my problem is that $D$ is poorly conditioned. So I cannot use $\kappa(D)\leq \kappa(K)$. Oct 10 at 16:34
• @Tucker Then clearly you cannot conclude in general that $K+D$ is better conditioned than $K$; take $K=I$ for instance. Oct 10 at 16:35
• I never said that $K+D$ is better conditioned than $K$. The conditioning idea was something that was being explored with lightxbulb. My original question is if there is something specific about algebraic multigrid that makes $K^{\prime}$ better suited for said algorithm than $K$. Oct 10 at 16:37