Preconditioned Conjugate Gradient Step

Problem

Perform one preconditioned conjugate gradient step on a quadratic.

With diagonal preconditioner minv, compute z = minv * r, alpha = (r dot z) / (p dot A p), x_new = x + alpha * p, r_new = r - alpha * A p, z_new = minv * r_new, and beta = (r_new dot z_new) / (r dot z). Return [x_new, r_new, p_new] with p_new = z_new + beta * p. Use 0 for alpha or beta when the corresponding denominator is zero.

Hint

The preconditioner turns the residual into z; alpha and beta use r dot z, not r dot r.

Test cases

case 1

in: [[0,0],[1,2],[1,2],[[4,1],[1,3]],[0.5,0.25]]

expected: [[0.075,0.15],[0.55,1.475],[0.7384375000000001,1.295625]]

case 2

in: [[1,1],[0,2],[0,2],[[2,0],[0,2]],[1,1]]

expected: [[1,2],[0,0],[0,0]]

case 3

in: [[0.5,-0.5],[1,1],[1,1],[[3,0],[0,2]],[1,0.5]]

expected: [[0.8,-0.2],[0.10000000000000009,0.4],[0.16000000000000011,0.26]]

Starter codePython

def pcg_step(x, r, p, A, minv):
    # Returns [x_new, r_new, p_new]
    # Your code here
    pass

3 test cases · run your code against them in the editor