1
$\begingroup$

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*}

Improve this question
$\endgroup$
15
  • 1
    $\begingroup$ 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$. $\endgroup$
    – lightxbulb
    Oct 7, 2022 at 16:24
  • 2
    $\begingroup$ 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. $\endgroup$
    – lightxbulb
    Oct 7, 2022 at 17:27
  • 1
    $\begingroup$ How did you get $\kappa(K') = (\lambda_{\max} + \epsilon_1) / (\lambda_{\min} + \epsilon_2)$?; $\endgroup$
    – lightxbulb
    Oct 7, 2022 at 23:38
  • 1
    $\begingroup$ 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. $\endgroup$
    – lightxbulb
    Oct 8, 2022 at 0:03
  • 1
    $\begingroup$ 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. $\endgroup$
    – lightxbulb
    Oct 8, 2022 at 0:10

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – lightxbulb
    Oct 9, 2022 at 11:53
  • $\begingroup$ 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. $\endgroup$
    – Tucker
    Oct 10, 2022 at 16:33
  • $\begingroup$ Another aspect about my problem is that $D$ is poorly conditioned. So I cannot use $\kappa(D)\leq \kappa(K)$. $\endgroup$
    – Tucker
    Oct 10, 2022 at 16:34
  • $\begingroup$ @Tucker Then clearly you cannot conclude in general that $K+D$ is better conditioned than $K$; take $K=I$ for instance. $\endgroup$
    – Federico Poloni
    Oct 10, 2022 at 16:35
  • $\begingroup$ 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$. $\endgroup$
    – Tucker
    Oct 10, 2022 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.