In this previous thread the following multiplicative way to combine symmetric preconditioners $P_1$ and $P_2$ for the symmetric system $Ax=b$ was suggested:\begin{align}P_\text{combo}^{-1} :=& P_1^{-1} + P_2^{-1}(I - A P_1^{-1})\\=&P_1^{-1} + P_2^{-1} - P_2^{-1} A P_1^{-1}.\end{align}This combined preconditioner is not symmetric. However, I have tried using it in conjugate gradient anyways in several different contexts, and the method always seems to converge just fine. Why is this?Example 1: Random matrices.% Testing multiplicative combination of preconditionersn = 500;[U,S,~] = svd(randn(n,n)); A = U*S*U';[W1,S1,~] = svd(randn(n,n)); noise1 = W1*S1*W1';[W2,S2,~] = svd(randn(n,n)); noise2 = W2*S2*W2';P1 = A + 0.5 * noise1;P2 = A + 0.5 * noise2;solve_P = @(x) P1\x + P2\x - P2\(A*(P1\x));b = randn(n,1);x_true = A\b;pcg(A,b,1e-6,n);pcg(A,b,1e-6,n,P1);x = pcg(A,b,1e-6,n,solve_P);norm(x_true - x)/norm(x_true)Here's the output I get:pcg converged at iteration 127 to a solution with relative residual 9.9e-07.pcg converged at iteration 62 to a solution with relative residual 6.8e-07.pcg converged at iteration 51 to a solution with relative residual 8.1e-07.relative error= 4.23e-07Example 2: Combining multigrid with incomplete cholesky for solving the Poisson equation.n = 50; N = n^2;A = gallery('poisson',n); %Laplacian on n-by-n grid, zero dirichlet BCL = ichol(A);solve_P1 = @(x) L'\(L\x);% Combinatorial multigrid: http://www.cs.cmu.edu/~jkoutis/cmg.htmlsolve_P2 = cmg_sdd(A); solve_P = @(x) solve_P1(x) + solve_P2(x) - solve_P1(A*solve_P2(x));b = randn(N,1);x_true = A\b;pcg(A,b,1e-6,N);pcg(A,b,1e-6,N,solve_P1);pcg(A,b,1e-6,N,solve_P2);x = pcg(A,b,1e-6,N,solve_P);disp(['relative error= ', num2str(norm(x_true - x)/norm(x_true),3)])For this I get the results:pcg converged at iteration 131 to a solution with relative residual 8.4e-07.pcg converged at iteration 44 to a solution with relative residual 6e-07.pcg converged at iteration 19 to a solution with relative residual 7e-07.pcg converged at iteration 12 to a solution with relative residual 4.7e-07.relative error= 5.2e-07Notes:I've also seen the same qualitative behavior on matrices arising in more complicated/realistic situations.Given an incorrect solution to $Ax=b$, the error $e$ and the residual $r$ are related by the error equation $Ae=r$. One can view this combo preconditioner as approximately solving the original equation using $P_1$ instead of $A$, then approximately solving the error equation with $P_2$ instead of $A$, then adding the approximate error back to correct the original approximate solution.
Why does conjugate gradient work with this nonsymmetric preconditioner?
preconditioning;conjugate gradient;krylov method;symmetry