SSOR with acceleration by CG

Question

I need to implement SSOR method with acceleration by conjugate gradient method. But I don't understand how we can to combine two iteration methods? Both algorithms solving $Ax=b$.
In book "Applied Iterative Methods", Hageman, Young described Conjugate Gradient Acceleration for Richardson method (p. 146), but I did't understand: how we combined two methods. I don't understand already at the stage which of the methods should be embedded into the other.
I appreciated any help about my questions.

score 0 · Answer 1 · answered Dec 17 '18 at 06:00

0

You need to use one method as a preconditioner for the other. My guess would be that you are asked to use SSOR as a preconditioner for CG.

answered Dec 17 '18 at 06:00

VorKir

300

It's not exactly what I wanted. Preconditioner it's another way to "merge" iterative methods (e.g. see Preconditioned Conjugate Gradient). – Pennywise Dec 17 '18 at 19:56

score 0 · Accepted Answer · answered Dec 17 '18 at 19:51

So, it's turned out to be simple.
Here's matlab code. It's not needed more explanation. Just read "Applied Iterative Methods", Hageman, Young.

 function [ x, err, iter, flag ] = ssor_cg(A, x, b, w, max_it, tol)
    D = diag(diag(A));
    I = eye(size(A));
    C_L = -tril(A, -1);
    C_U = -triu(A, 1);
    W = mpower(A, 1/2);
    Q = w / (2 - w) * (1 / w * D - C_L) * mpower(D, -1) * (1 / w * D - C_U);
    G = I - mpower(Q, -1) * A;
    k = mpower(Q, -1) * b;

    delta = 0;
    p = 0;
    alpha = 0;
    for iter = 0 : max_it
        x_prev = x;
        p_prev = p;
        delta = G * x + k - x;
        delta_prev = delta;

        if iter == 0
            p = delta;
        else 
            p = delta + alpha * p_prev;
        end

        if iter > 0
            alpha = (dot(W * delta, W * delta)) / (dot(W * delta_prev, W * delta_prev));
        end

        lambda = (dot(W * delta, W * delta)) / (dot(W * p, W * (I - G) * p));

        x = x_prev + lambda * p;
        err = norm(x_prev); % compute error
        if (err <= tol) % check for convergence
            break
        end        
    end    
end

Ill read later but i dont see the difference with the preconditioned CG. You basically modify the system for cg to solve for the system premultiplied by the SSOR operator. — VorKir, Dec 17 '18 at 20:07

SSOR with acceleration by CG

2 Answers2