3. The algorithm below is used to construct the LU factorization of A ∈ Rn×n. LU algorithm 1.3
1. 2. 3. 4. 5. 6.
case where A is an upper Hessenberg matrix.
(a) Modify line 3 in the above algorithm, so that only non-zero entries are used in the cal-
culation. Write down the corresponding pseudo-code and give reasons for your changes.
(b) Explain why the (n − k) × (n − k) outer product arising in the update step in line 4 has
L=I,U=A fork=1:n−1
L(k+1:n,k) = U(k+1:n,k)/U(k,k)
U(k+1:n, k+1:n) = U(k+1:n, k+1:n)−L(k+1:n, k)U(k, k+1:n) end
U = triu(U)
Given the matrix structures described in Q2, we wish to adapt the above algorithm to the
the block structure
−rk − O
where rk is generally a dense row of size n−k and O ∈ R(n−k−1)×(n−k). Hence, modify line 4 to ensure least computational complexity in the update. Write down the corresponding pseudo-code.
(c) What is the complexity of your modified LU algorithm? What is the resulting com- plexity of solving a linear system with upper Hessenberg matrix A?
(d) Write a function file hesslusolve.m for solving a linear system Ax = b, where A is upper Hessenberg. Your input should be a matrix A and the vector b, while the output should be the solution vector x.
Full marks will be awarded for this part if the following recommendations are observed:
i. Your file should follow the outline of the function lusolve.m derived in the lab, namely, it should contain the following:
• a main function hesslusolve;
• a local function hessludecomp containing the implementation of the modified
LU algorithm derived above;
• local functions forwardsub, backwardsub, modified as necessary to take into account the structures of the matrices arising in the decomposition;
• any other local functions you may need;
• comments describing the actions of each function, including a description of
their input and output.
ii. You should check that your file runs on some input of your choice. You should also check that the result is correct.
[26]