Fault-Tolerant Iterative Solver for Linear Systems
Assume: no error during preconditioning
---------------------------------
r(0) = b - Ax(0)
rho(-1) = 1
p(0) = (0,...,0)^T
----------------------------------
for k=1,2,...
z(k-1) = M^(-1) * r(k-1)
rho(k-1) = <r(k-1),z(k-1)>
beta = rho(k-1) / rho(k-2)
p(k) = z(k-1) + beta*p(k-1)
q(k) = A * p(k)
dot_pq = <p(k),q(k)>
alpha = rho(k-1) / dot_pq
x(k) = x(k-1) + alpha*p(k)
r(k) = r(k-1) - alpha*q(k)
------------------------------------
-
vector relationship:
z = M^(-1) * r p = z + beta * p q = A * p x = x + alpha * p r = r - alpha * q
-
checksum relationship map:
checksum X *--- checksum P *--- checksum Z | * checksum R *--- checksum Q
-
check checksum X only, ideally
cksQ incorrect -> cksR incorrect -> cksZ incorrect(next iteration) cksZ incorrect -> cksP incorrect -> cksX incorrect
-
check checksum of X and R, practically
Assume no errors in preconditioning z = Br step 3 is insufficient to detect errors in all vectors so, add checking cksR
----------------------------------------
r(0) = b - Ax(0)
rtld(0) = r(0) or random
rho(-1) = 1
p(0) = (0,...,0)^T
ptld(0) = (0,...,0)^T
----------------------------------------
for k=1,2,...
z(k-1) = M^-1 * r(k-1)
ztld(k-1) = M^-T * rtld(k-1)
rho(k-1) = <z(k-1),rtld(k-1)>
beta = rho(k-1) / rho(k-2)
p(k) = z(k-1) + beta*p(k-1)
ptld(k) = ztld(k-1) + beta*ptld(k-1)
q(k) = A * p(k)
qtld(k) = A^T * ptld(k)
tmpdot1 = <ptld(k),q(k)>
alpha = rho(k-1) / tmpdot1
x(k) = x(k-1) + alpha*p(k)
r(k) = r(k-1) - alpha*q(k)
rtld(k) = rtld(k-1) - alpha*qtld(k)
----------------------------------------
-
vector relationship:
z = M^(-1) * r ztld = M^(-1) * rtld p = z + beta * p ptld = ztld + beta * ptld q = A * p qtld = At * ptld x = x + aplha * p r = r - aplha * q rtld = rtld - alpha * qtld
-
checksum relationship map:
1. checksum X *--- checksum P *--- checksum Z | * checksum R *--- checksum Q 2. checksum Rt *--- checksum Qt *--- checksum Pt *--- checksum Zt
-
check checksum of X, R, and Rt
1. cksQ incorrect -> cksR incorrect -> cksZ incorrect(next iteration) cksZ incorrect -> cksP incorrect -> cksX incorrect 2. cksZt incorrect -> cksPt incorrect -> cksQt incorrect -> cksRt incorrect
-----------------------------------
r(0) = b - Ax(0)
rtld(0) = r(0) or random
rho(-1) = 1
p(0) = (0,...,0)^T
q(0) = (0,...,0)^T
-----------------------------------
for k=1,2,...
rho(k-1) = <rtld,r(k-1)>
beta = rho(k-1) / rho(k-2)
u(k) = r(k-1) + beta*q(k-1)
p(k) = u(k) + beta*(q(k-1) + beta*p(k-1))
phat(k) = M^-1 * p(k)
vhat(k) = A * phat(k)
tmpdot1 = <rtld,vhat(k-1)>
alpha = rho(k-1) / tmpdot1
q(k) = u(k) - alpha*vhat(k)
phat(k) = u(k) + q(k)
uhat(k) = M^-1 * (u(k) + q(k))
x(k) = x(k-1) + alpha*uhat(k)
qhat(k) = A * uhat(k)
r(k) = r(k-1) - alpha*qhat(k)
------------------------------------
-
vector relationship
u = r + beta * q p = u + beta * (q + beta * p) phat = M^(-1) * p vhat = A * phat q = u - alpha * vhat uhat = M^(-1) * (u + q) x = x + alpha * uhat qhat = A * uhat r = r - alpha * qhat
-
checksum relationship map
cksU *--- cksR *--- cksQhat *--- cksUhat ---* cksX * | | * cksQ ---* cksP *--- cksU * | | * cksVhat *--- cksPhat
-
check checksum of P and X
1. cksX incorrect 2. cksQhat incorrect -> cksR incorrect -> cksU incorrect <- cksQ incorrect cksU incorrect -> cksQ incorrect <- cksVhat incorrect cksU incorrect -> cksP incorrect <- cksQ incorrect