Skip to main content

Unit 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.