# How to compute the computational cost and storage of the Full Orthogonalization Method?

About the analysis of Full Orthogonalization Method (FOM) in Prof. Saad's book, wrote as follows:

Algorithm 6.4 (FOM): $$\begin{array}{l} r_0=b-Ax_0,\beta=\|r_0\|_2,v_1 = r_0/\beta\\ Define \quad H_m = \{h_{ij}\}_{i,j=1,\dots,m}, Set\quad H_m=0;\\ For \quad {j=1,\dots,m}\\ {\quad w_j = Av_j\\ \quad\quad For\quad{i=1,\dots,j}\\ \quad\quad{h_{ij}=(w_j,v_i)\\ w_j=w_j-h_{ij}v_i\\ }\\ \qquad end\\h_{j+1,j}=\|w_j\|_2\\ v_{j+1}=w_j/h_{j+1,j}\\ }\\ end \\y_m = H^{-1}_m(\beta e_1),x_m=x_0+V_my_m.\\ \end{array}$$

This is the FOM method from Krylov subspace for solving $$Ax=b$$, where $$A\in \mathbb{R}^{n\times n}$$ is nonsingular. Considering the computational cost and storage it is wrote as

A rough estimate of the cost of each step of the algorithm is determined as follows. If Nz(A) is the number of nonzero elements of A, then m steps of the Arnoldi procedure will require m matrix-vector products at the cost of 2m × Nz(A). Each of the Gram-Schmidt steps costs approximately 4 × j × n operations, which brings the total over the m steps to approximately $$2m^2n$$. Thus, on the average, a step of FOM costs approximately 2Nz(A) + 2mn. Regarding storage, m vectors of length n are required to save the basis Vm. Additional vectors must be used to keep the current solution and right-hand side, and a scratch vector for the matrix-vector product. In addition, the Hessenberg matrix Hm must be saved. The total is therefore roughly $$(m + 3)n +\frac{m^2}{2}.$$ In most situations m is small relative to n, so this cost is dominated by the first term.

I want to ask that How to estimate the computational cost and storage, in general?

• The explanation in Saad is pretty clear as to how to estimate storage and computational cost. You sum up what each component requires in terms of storage and cost. With the caveat that sometimes storage can be reused and you need to look at the method specifically to figure out what can be reused. What part of the analysis do you need clarification for? Because at present this question is too broad for a good answer. – EMP Dec 18 '19 at 18:24
• Thanks for your reply, I have tried. But I still have a question about the storage, for the storage of the upper Hessenberg matrix $H_m\in R^{m\times m}$, which is a full matrix not a sparse matrix, so I think it needs to store all the $m^2$ entries including the zeros entries. But in the book, it wrote $m^2/2$, it is not correct? Thanks. – sunshine Dec 19 '19 at 0:35
• The hessenberg matrix can be rotated through the iterations to make it upper triangular. so it doesn't require full $m^2$. This is something that you Saad is very clear about. – EMP Dec 19 '19 at 17:00
• Get it, Thanks very much. Because when I code in matlab, I often initialize the marix $H_m \in R^{m\times m}$ using H = zeros(m,m) to preallocate the space for speed. Then I thought we need to store the $m^2$ entries of $H_m$. I misunderstand the idea of the way of the real storage from Saad. Thanks very much. – sunshine Dec 20 '19 at 7:16