GCR算法单次迭代FLOPS分析及第i次迭代内存与FLOPS计算

First, here's the GCR algorithm pseudocode from your question for reference:

\begin{split}\text{for }&i = 1,2,\ldots\text{ do}\\&s^i = r^{i-1},\\&v^i = As^i,\\&\text{for }j =1,\ldots,i-1\,\text{do}\\&\,\,\,\alpha = (v^j)^Tv^i,\\&\,\,\,s^i:=s^i - \alpha s^j,\,v^i:=v^i - \alpha v^j\\&\text{end for}\\&s^i:=s^i\big/\|v^i\|_2,\,v^i:=v^i\big/\|v^i\|_2\\&\beta = (v^i, r^{i-1});\\&u^i:=u^{i-1}+\beta s^i;\\&r^i = r^{i-1} - \beta v^i \end{split}

Memory Footprint #

Let's count all the vectors we need to persistently store:

• Fixed vectors: We need to keep the right-hand side b, the current solution vector u, and the current residual vector r — that's 3 n-dimensional vectors total.
• Iteration-dependent vectors: By the i-th iteration, we've generated and need to retain all s^1 through s^i, plus their corresponding v^1 through v^i — that's 2i n-dimensional vectors.

Assuming each vector element takes up one memory unit (e.g., a single-precision float), the total number of memory units required is:
$$(2i + 3)n$$

Floating-Point Operations (FLOPS) #

Let's break down the FLOPS by each key operation in the i-th iteration:

• Matrix-vector multiplication: The operation v^i = As^i takes $2n^2$ FLOPS for an n×n dense matrix A. This comes from computing the dot product of each row of A with s^i (n multiplications and n-1 additions per row, so ~2n operations per row, times n rows).
• Dot products: We perform a total of $i+1$ dot products: i-1 of them in the inner loop ((v^j)^Tv^i for j=1 to i-1) plus one more to calculate $\beta = (v^i, r^{i-1})$. Each dot product uses roughly $2n$ FLOPS (n multiplications, n-1 additions), so total dot product FLOPS are $2n(i+1)$.
• Vector updates: There are $2i$ vector update operations total: 2 per iteration of the inner loop (updating s^i and v^i) for i-1 loops, plus two more updates for u^i and r^i at the end. Each update (e.g., s^i -= αs^j) uses $2n$ FLOPS (n multiplications for α*s^j, n subtractions/additions to combine with s^i), so total vector update FLOPS are $4ni$.
• Vector scaling: The two scaling operations (s^i /= ||v^i||_2 and v^i /= ||v^i||_2) each take $n$ FLOPS (n divisions), so that's $2n$ total FLOPS.

Adding all these up, the total FLOPS for the i-th iteration is approximately:
$$2n^2 + 2n(i+1) + 4ni + 2n = 2n^2 + 6ni + 4n$$

Note: If matrix A is sparse, the FLOPS for the matrix-vector multiplication will depend on the number of non-zero elements — the above calculation assumes a dense matrix.

内容的提问来源于stack exchange，提问作者titusAdam