## Unit3.2.6Cost of Gram-Schmidt algorithms

(No video for this unit.)

###### Homework3.2.6.1.

Analyze the cost of the CGS algorithm in Figure 3.2.4.2 (left) assuming that $A \in \C^{m \times n}\text{.}$

Solution

During the $k$th iteration ($0 \leq k \lt n$), $A_0$ has $k$ columns and $A_2$ has $n - k - 1$ columns. In each iteration

\begin{equation*} \begin{array}{|l|c|} \hline {\rm Operation} \amp {\rm Approximate~cost} \\ \amp {\rm (in~flops)} \\ \hline r_{01} := A_0^H a_1 \amp 2 m k \\ a_1 := a_1 - A_0 r_{01} \amp 2 m k \\ \rho_{11} := \| a_1 \|_2 \amp 2 m \\ a_1 := a_1 / \rho_{11} \amp m \\ \hline \end{array} \end{equation*}

Thus, the total cost is (approximately)

\begin{equation*} \begin{array}{l} \sum_{k=0}^{n-1} \left[ 2 m k + 2m k + 2 m + m \right] \\ ~~~=~~~~\\ \sum_{k=0}^{n-1} \left[ 3 m + 4 m k \right] \\ ~~~=~~~~\\ 3 m n + 4 m \sum_{k=0}^{n-1} k \\ ~~~\approx~~~~\lt \sum_{k=0}^{n-1} k = n (n-1 )/2 \approx n^2 / 2 \gt \\ 3 m n + 4 m \frac{n^2}{2} \\ ~~~=~~~~\\ 3 m n + 2 m n^2 \\ ~~~\approx~~~~\lt 3 m n {\rm ~is~of~lower~order} \gt \\ 2 m n^2 \end{array} \end{equation*}
###### Homework3.2.6.2.

Analyze the cost of the MGS algorithm in Figure 3.2.4.2 (right) assuming that $A \in \C^{m \times n}\text{.}$

Solution

During the $k$th iteration ($0 \leq k \lt n$), $A_0$ has $k$ columns. and $A_2$ has $n - k - 1$ columns. In each iteration

\begin{equation*} \begin{array}{|l|c|} \hline {\rm Operation} \amp {\rm Approximate~cost} \\ \amp {\rm (in~flops)} \\ \hline \rho_{11} := \| a_1 \|_2 \amp 2 m \\ a_1 := a_1 / \rho_{11} \amp m \\ \hline r_{12}^T := a_1^H A_2 \amp 2 m (n-k-1) \\ A_2 := A_2 - a_1 r_{12}^T \amp 2 m (n-k-1) \\ \hline \end{array} \end{equation*}

Thus, the total cost is (approximately)

\begin{equation*} \begin{array}{l} \sum_{k=0}^{n-1} \left[ 2 m (n-k-1) + 2m (n-k-1) + 2 m + m \right] \\ ~~~=~~~~\\ \sum_{k=0}^{n-1} \left[ 3 m + 4 m (n-k-1) \right] \\ ~~~=~~~~\\ 3 m n + 4 m \sum_{k=0}^{n-1} (n-k-1) \\ ~~~=~~~~ \lt {\rm Substitute~} j = (n-k-1) \gt \\ 3 m n + 4 m \sum_{j=0}^{n-1} j \\ ~~~\approx~~~~\lt \sum_{j=0}^{n-1} j = n (n-1 )/2 \approx n^2 / 2 \gt \\ 3 m n + 4 m \frac{n^2}{2} \\ ~~~=~~~~\\ 3 m n + 2 m n^2 \\ ~~~\approx~~~~\lt 3 m n {\rm ~is~of~lower~order} \gt \\ 2 m n^2 \end{array} \end{equation*}
###### Homework3.2.6.3.

Which algorithm requires more flops?

Solution

They require the approximately same number of flops.

A more careful analysis shows that, in exact arithmetic, they perform exactly the same computations, but in a different order. Hence the number of flops is exactly the same.