6. By factoring $A$ into $LU$, the LU decomposition allows solving $A\mathbf{x} = \mathbf{b}$ by first solving $L\mathbf{y} = \mathbf{b}$, followed by $U\mathbf{x} = \mathbf{y}$, each requiring only a single triangular solve. Thus, computing $A = LU$ is crucial in large-scale computer engineering applications.

(a) (10%) Give the complexity of the classic LU decomposition, shown in Algorithm 1.

Algorithm 1: LU Decomposition Without Pivoting
Require: Matrix A in R^(n x n)
Ensure: Lower triangular matrix L, Upper triangular matrix U such that A = LU
1:  Initialize L <- I_n, U <- 0_(n x n)
2:  for k = 1 to n do
3:      for j = k to n do                      // Compute k-th row of U
4:          U[k,j] <- A[k,j] - sum_{s=1}^{k-1} L[k,s] * U[s,j]
5:      end for
6:      for i = k+1 to n do                    // Compute k-th column of L
7:          L[i,k] <- (1 / U[k,k]) * (A[i,k] - sum_{s=1}^{k-1} L[i,s] * U[s,k])
8:      end for
9:  end for
10: return (L, U)

(b) (10%) An improvement of (a) based on the block matrix multiplication is shown in Algorithm 2. Give the complexity of the speed-improved LU decomposition.

Algorithm 2: Speed-Improved Block LU Decomposition
Require: Matrix A in R^(n x n), n is a power of 2
Ensure: Matrices L, U with A = LU
1:  function SPEEDIMPROVEDBLOCKLU(A)
2:      n <- size of A
3:      if n = 1 then
4:          return ([1], [A11])
5:      end if
6:      Partition A into blocks: A = [[A11, A12], [A21, A22]]
7:      (L11, U11) <- SPEEDIMPROVEDBLOCKLU(A11)
8:      U12 <- SISOLVE(L11, A12, lower)
9:      L21 <- SISOLVE(U11, A21, upper)
10:     S <- A22 - SIMULTIPLY(L21, U12)
11:     (L22, U22) <- SPEEDIMPROVEDBLOCKLU(S)
12:     Construct: L = [[L11, 0], [L21, L22]],  U = [[U11, U12], [0, U22]]
13:     return (L, U)
14: end function

function SISOLVE(T, B, type)
2:      if n = 1 then
3:          return B / T
4:      end if
5:      Partition T, B into blocks: T = [[T11, T12], [T21, T22]], B = [B1; B2]
6:      if type = lower then
7:          X1 <- SISOLVE(T11, B1)
8:          X2 <- SISOLVE(T22, B2 - T21*X1)
9:      else
10:         X2 <- SISOLVE(T22, B2)
11:         X1 <- SISOLVE(T11, B1 - T12*X2)
12:     end if
13:     return [X1; X2]
14: end function

function SIMULTIPLY(A, B)
2:      if n = 1 then
3:          return A * B
4:      end if
5:      Partition A, B into: A = [[A11, A12], [A21, A22]], B = [[B11, B12], [B21, B22]]
6:      M1 <- (A11 + A22)(B11 + B22)
7:      M2 <- (A21 + A22) B11
8:      M3 <- A11 (B12 - B22)
9:      M4 <- A22 (B21 - B11)
10:     M5 <- (A11 + A12) B22
11:     M6 <- (A21 - A11)(B11 + B12)
12:     M7 <- (A12 - A22)(B21 + B22)
13:     C11 <- M1 + M4 - M5 + M7
14:     C12 <- M3 + M5
15:     C21 <- M2 + M4
16:     C22 <- M1 - M2 + M3 + M6
17:     C <- [[C11, C12], [C21, C22]]
18:     return C
19: end function

(c) (10%) Given $A = \begin{bmatrix}4 & 3 \\ 6 & 3\end{bmatrix}$, compute the LU decomposition $A = LU$ using the speed-improved LU decomposition method in (b). (Note: List the key intermediate results from Algorithm 2 to receive full credit.)