0
$\begingroup$

I've read Boxerman's thesis and I feel that there is possibly a mistake.

We have to resolve $$Ax=b$$ $A$ is a positive-definite symmetric matrix and is very sparse so the conjugate gradient method is chosen.

He wrote (p70 to p73) that to improve the convergence, we can use the following preconditionner : $$P=SC+(I-S)$$ where $C$ is the 3x3 block-diagonal sub-matrix of $A$, $I$ is the identity matrix and $S$ is a 3x3 block-diagonal matrix where each block can be

$S_i=I_3$ or $S_i=0$ or $S_i=I_3-nn^T$ ($n$ is a 3-dimension unit vector)

So, the preconditionner $P$ is a 3x3 Block-Diagonal matrix and can be easily inverted BUT I think it is not necessary symmetric. As far as I know, a preconditionner for the conjugate gradient method must be symmetric.

Am I missing something or there is a mistake in the thesis ?

$\endgroup$
0
$\begingroup$

Conjugate gradients need not to be necessarily preconditioned by a symmetric positive definite preconditioner. There is usually some "hidden" symmetry and positive definiteness behind sometimes introduced by a "special" inner product.

A simple example could be applying an SPD preconditioner $M$ to solve $Ax=b$ ($A$ SPD) as in the left preconditioning: $M^{-1}Ax=M^{-1}b$. $M^{-1}A$ is clearly neither symmetric nor positive definite and still, it is symmetric with respect to the inner product induced by $M$: $(M^{-1}Ax,y)_M=(MM^{-1}Ax,y)=(Ax,y)=(x,Ay)=(x,MM^{-1}A)=(Mx,M^{-1}Ay)=(x,Ay)_M$. Therefore it is safe to apply CG on $M^{-1}A$ but instead of the standard Euclidean inner product you use the inner product induced by the preconditioner $M$. In fact, this is just what is usually called preconditioned conjugate gradient method (PCG) and is equivalent to applying CG on $M^{-1/2}AM^{-1/2}$.

There are also other exotic preconditioners for CG, e.g., constraint preconditioning particularly popular in optimization. You can apply CG, e.g., on the system in the block form $$ A=\begin{bmatrix} K & B \\ B^T & 0 \end{bmatrix}, $$ where $K$ is SPD and B has full column rank. The preconditioner $M$ has the same form as $A$ with $K$ replaced by some reasonable approximation $G$, e.g., diagonal. Both the matrix and the precondtitioner are symmetric but indefinite and still CG can be applied since it turns out that it is equivalent to applying CG on $PG^{1/2}KG^{-1/2}P$, where $P$ is a projection onto the range of $B$ (if I remember correctly). You can see more information, e.g., in this article.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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