et
𝐴
be an
𝑚
×
𝑛
matrix. Determine the exact numbers of floating point additions, subtractions, multiplications, and divisions involved in computing the factorization
𝐴
=
𝑄
𝑅
by Algorithm
1
0
.
1

(
Trefethen
)
.
Algorithm
1
0
.
1
.
Householder QR Factorization
|
)
|
𝑣
𝑘
|
|
2
|
𝐴
𝑘
:
𝑚
,
𝑘
:
𝑛
=
𝐴
𝑘
:
𝑚
,
𝑘
:
𝑛
-
2
𝑣
𝑘
(
𝑣
𝑘
*
*
𝐴
𝑘
:
𝑚
,
𝑘
:
𝑛
)

Algorithm 10.1. Householder QR Factorization
for k=1 to n
x = Ak:m,k
Uk =
Uk vk/lvk/2
Ak:m.k:n = Ak:m.k:n -

Question

et 
𝐴
 ﻿be an 
𝑚
×
𝑛
 ﻿matrix. Determine the exact numbers of floating point additions, subtractions, multiplications, and divisions involved in computing the factorization 
𝐴
=
𝑄
𝑅
 ﻿by Algorithm 
1
0
.
1
 
(
Trefethen
)
.
Algorithm 
1
0
.
1
.
 ﻿Householder QR Factorization
|
)
|
𝑣
𝑘
|
|
2
|
𝐴
𝑘
:
𝑚
,
𝑘
:
𝑛
=
𝐴
𝑘
:
𝑚
,
𝑘
:
𝑛
-
2
𝑣
𝑘
(
𝑣
𝑘
*
*
𝐴
𝑘
:
𝑚
,
𝑘
:
𝑛
)

Algorithm 10.1. Householder QR Factorization
for k=1 to n
x = Ak:m,k
Uk =
Uk vk/lvk/2
Ak:m.k:n = Ak:m.k:n -

Accepted Answer

⚹ To determine the exact numbers of floating point additions, subtractions, multiplications, and divisions involved in computing the factorization $A = QR$ by Algorithm 10.1 (Householder QR Factorization), we need to analyze each step of the algorithm. ⚹ ⚹ The algorithm is as follows: ⚹ 1. ⚹ for $k = 1$ to $n$ ⚹ 2. ⚹ $x = A_{k:m,k}$ ⚹ 3. ⚹ $v_k = - ext{sign}(x_1) \|x\|_2 e_1 + x$ ⚹ 4. ⚹ $v_k = v_k / \|v_k\|_2$ ⚹ 5. ⚹ $A_{k:m,k:n} = A_{k:m,k:n} - 2v_k(v_k^* A_{k:m,k:n})$ ⚹ ⚹ Let's break down the floating point operations (FLOPs) for each step: ⚹ ‖ ▪ ⋮ Step 2: $x = A_{k:m,k}$ ‖ ‖ ▪ ⋮ This step involves copying a subvector of $A$. No floating point operations are involved. ‖ ‖ ▪ ⋮ Step 3: $v_k = - ext{sign}(x_1) \|x\|_2 e_1 + x$ ‖ ‖ ▪ ⋮ - Calculating $\|x\|_2$ involves $m-k+1$ multiplications and $m-k$ additions. ‖ ‖ ▪ ⋮ - Multiplying by $- ext{sign}(x_1)$ involves $1$ multiplication. ‖ ‖ ▪ ⋮ - Adding $x$ to the scaled $e_1$ involves $m-k+1$ additions. ‖ ‖ ▪ ⋮ Step 4: $v_k = v_k / \|v_k\|_2$ ‖ ‖ ▪ ⋮ - Normalizing $v_k$ involves $m-k+1$ divisions. ‖ ‖ ▪ ⋮ Step 5: $A_{k:m,k:n} = A_{k:m,k:n} - 2v_k(v_k^* A_{k:m,k:n})$ ‖ ‖ ▪ ⋮ - Calculating $v_k^* A_{k:m,k:n}$ involves $(m-k+1)(n-k+1)$ multiplications and $(m-k)(n-k+1)$ additions. ‖ ‖ ▪ ⋮ - Scaling by $2v_k$ involves $(m-k+1)(n-k+1)$ multiplications. ‖ ‖ ▪ ⋮ - Subtracting the result from $A_{k:m,k:n}$ involves $(m-k+1)(n-k+1)$ subtractions. ‖ ⚹ Summarizing the total FLOPs for each iteration of $k$: ⚹ ‖ ▪ ⋮ Additions: $(m-k)(n-k+1) + (m-k+1) + (m-k+1)(n-k+1)$ ‖ ‖ ▪ ⋮ Subtractions: $(m-k+1)(n-k+1)$ ‖ ‖ ▪ ⋮ Multiplications: $(m-k+1) + (m-k+1)(n-k+1) + (m-k+1)(n-k+1)$ ‖ ‖ ▪ ⋮ Divisions: $m-k+1$ ‖ ⚹ To get the total number of floating point operations, sum these over all iterations of $k$ from $1$ to $n$. ⚹ ⚹ This provides a detailed breakdown of the floating point operations involved in the Householder QR Factorization algorithm. ⚹

Sia