Biconjugate gradient method

(Difference between revisions)

Revision as of 00:30, 15 September 2005

Biconjugate gradient method could be summarized as follows

For the given system of equation
Ax = b ;
b = source vector
x = solution variable for which we seek the solution
A = coefficient matrix

M = the precondioning matrix constructued by matrix A

Allocate temperary vectors r,z,p,q, rtilde,ztilde,qtilde

Allocate temerary reals rho_1, rho_2 , alpha, beta

r := b - A $\bullet$ x

rtilde = r

for i := 1 step 1 until max_itr do

solve (M $\bullet$ z = r )

solve (M^T $\bullet$ ztilde = rtilde )

rho_1 = z $\bullet$ rtilde

if i = 1 then

p := z

ptilde := ztilde

else

beta = (rho_1/rho_2)

p = z + beta * p

ptilde = ztilde + beta * ptilde

end if

q := A $\bullet$ p

qtilde := A^T $\bullet$ ptilde

alpha = rho_1 / (ptilde $\bullet$ q)

x = x + alpha * p

r = r - alpha * q

rtilde = rtilde - alpha * qtilde

rho_2 = rho_1

end (i-loop)

deallocate all temp memory

return TRUE

@@ Line 12: / Line 12: @@
 === Algorithm ===
-  Has to be added very soon.
+----
+:  Allocate temperary vectors r,z,p,q, rtilde,ztilde,qtilde <br>
+:  Allocate temerary reals rho_1, rho_2 , alpha, beta<br>
+: <br>
+:  r := b - A<math>\bullet</math>x <br>
+:  rtilde = r <br>
+: <br>
+:  for i := 1 step 1 until max_itr do
+::      solve (M<math>\bullet</math>z = r ) <br>
+::      solve (M<sup>T</sup><math>\bullet</math>ztilde = rtilde ) <br>
+::      rho_1 = z<math>\bullet</math>rtilde <br>
+::      if i = 1 then
+:::        p := z <br>
+:::        ptilde := ztilde <br>
+::        else <br>
+:::         beta = (rho_1/rho_2) <br>
+:::         p = z + beta * p <br>
+:::         ptilde = ztilde + beta * ptilde <br>
+::      end if <br>
+::      q := A<math>\bullet</math>p <br>
+::      qtilde := A<sup>T</sup><math>\bullet</math>ptilde <br>
+::      alpha = rho_1 / (ptilde<math>\bullet</math>q) <br>
+::      x = x + alpha * p <br>
+::      r = r - alpha * q <br>
+::      rtilde = rtilde - alpha * qtilde <br>
+::      rho_2 = rho_1 <br>
+:  end (i-loop)
+:  <br>
+:  deallocate all temp memory <br>
+:  return TRUE <br>
+----