Consider the LU decomposition of an upper Hessenberg (no, it's not a place in Germany) matrix, defined on the facing page, assuming that no pivoting is needed: A = LU.
(a) Provide an efficient algorithm for this LU decomposition (do not worry about questions of memory access and vectorization).
(b) What is the sparsity structure of the resulting matrix L (i.e., where are its nonzeros)?
(c) How many operations (to a leading order) does it take to solve a linear system Ax = b, where A is upper Hessenberg?
(d) Suppose now that partial pivoting is applied. What are the sparsity patterns of the factors of A?