Biconjugate gradient method

Statement

Let $A$ be a real invertible $n \times n$ matrix, let $b \in \R^n$, and let $x_0 \in \R^n$ with $r_0 = b - A x_0$. Choose a shadow residual $\tilde{r}_0 \in \R^n$ with $\tilde{r}_0^T r_0 \ne 0$, and set $p_0 = r_0$ and $\tilde{p}_0 = \tilde{r}_0$. The biconjugate gradient method (BiCG) computes, for $k = 0, 1, \dots$, $$\alpha_k = \frac{\tilde{r}_k^T r_k}{\tilde{p}_k^T A p_k}, \quad x_{k+1} = x_k + \alpha_k p_k, \quad r_{k+1} = r_k - \alpha_k A p_k, \quad \tilde{r}_{k+1} = \tilde{r}_k - \alpha_k A^T \tilde{p}_k,$$ $$\beta_k = \frac{\tilde{r}_{k+1}^T r_{k+1}}{\tilde{r}_k^T r_k}, \quad p_{k+1} = r_{k+1} + \beta_k p_k, \quad \tilde{p}_{k+1} = \tilde{r}_{k+1} + \beta_k \tilde{p}_k,$$ where $A^T$ is the transpose. Suppose that the denominators $\tilde{p}_k^T A p_k$ and $\tilde{r}_k^T r_k$ are nonzero up to step $m$. Then in exact arithmetic, for $i, j \le m$:

1. $r_k = b - A x_k$, and $x_k \in x_0 + \mathcal{K}_k(A, r_0)$, where $\mathcal{K}_k$ is the Krylov subspace;
2. (biorthogonality) $\tilde{r}_i^T r_j = 0$ for $i \ne j$;
3. (biconjugacy) $\tilde{p}_i^T A p_j = 0$ for $i \ne j$.