疎行列ベクトル積の演算量

CSR 形式の $A\in M_{m,n}(\mathbb{R})$ と $\boldsymbol{x}\in\mathbb{R}^n$ について、$y_i=\sum_{t=\mathtt{rowptr}[i]}^{\mathtt{rowptr}[i+1]-1}\mathtt{val}[t]\,x_{\mathtt{colind}[t]}$ で $\boldsymbol{y}=A\boldsymbol{x}$ が求まり、乗算と加算はそれぞれ $\mathrm{nnz}(A)$ 回である。記憶量は $2\,\mathrm{nnz}(A)+m+1$ 語である。