\bsk \perp \mP^{-1}\mathcal{K}_k (\mA\mP^{-1},\br_0),$$ where $\mathcal{K}_k (\mA,\br_0)$ denotes the $k$th Krylov subspace generated by $\mA$ and $\br_0$. The determining conditions imply that $$\begin{aligned}
    \label{orthog}
    (\byk-\by_0)^{\T} \brk = 0, \qquad 
    \bskT (\bxk-\bx_0) = 0.
  \end{aligned}$$ Note that during the BiCG finite precision computations, the bi-orthogonality conditions are usually not satisfied, and this fact cannot be ignored in our considerations. However, not all properties of BiCG vectors are lost in finite precision arithmetic. Because of the choice of coefficients $\alpha_{k}$ and $\beta_{k+1}$ (cf. Algorithm \[alg:BiCG\]), the bi-orthogonality of two consecutive vectors (local bi-orthogonality) is usually well preserved. This fact can be exploited to derive a more efficient way of approximating the quantities of interrest; for more details, see [@StTi2011].

Algorithm \[alg:BiCG\] shows the BiCG algorithm which generates sequences of primal and dual approximations $\{\bxk\}$ and $\{\byk\}$, respectively. Note that $\tilde{\br}_{k+1}=\mP^{-1} \br_{k+1}$ and $\tilde{\bs}_{k+1}=\mP^{-\T} \bs_{k+1}$ is equivalent to solving the system $$\begin{aligned}
  \label{mP}
  \mP\:\tilde{\br}_{k+1}=\br_{k+1}\quad\mbox{and}\quad \mP^{\T}\:\tilde{\bs}_{k+1}=\bs_{k+1},\end{aligned}$$ respectively. At lines 2 and 14 of Algorithm \[alg:BiCG\] we compute an additional sequence $\{\bxi_k^B\}$. The meaning of quantities $\bxi_k^B$ is explained in the text below. The algorithm has to be furnished by a suitable stopping criterion, which is discussed in Section \[sec:estim\].

**input** $\mA$, $\bx_{0}$, $\by_{0}$, $\mP$

