Subsection 3.2.6 Cost of Gram-Schmidt algorithms
¶(No video for this unit.)
Homework 3.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*}
Homework 3.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*}
Homework 3.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.
