[General boards] [Winter 2019 courses] [Fall 2018 courses] [Summer 2018 courses] [Older or newer terms]

Past test question Q1


#1

Is there any way other than directly take the transpose of PA?
Because if I do it this way, I found that I have to calculate the inverse of P which is definitely not very desirable considering it is very costly.
Any clue is appreciated. Thanks!


#2

P is a permutation matrix so the inverse of P is just its transpose.

Really not sure on this
At x = b
At Pt P x = b since Pt P = I
(PA)t z = b let z = Px
(LU)t z = b
Ut Lt z = b
=> Ut c = b (1) solve for c
=> Lt z = c (2) solve for z
=> P x = z (3) solve for x

  1. is forward substitution using matrix Ut, no extra computation, when we need i j entry of Ut we just use j i entry of U. n^2/2 flops and n divisions
  2. is backward substitution using matrix Lt, same again as above n^2/2 flops and 0 divisions
  3. I think this is just n operations. If P is stored as a perm vector
    for i = 1 to n
    x[permP[i]] = z[i]
    endfor
    (if permP = [4, 3, 1, 2] and z = [40, 30, 10, 20]t then x = [10, 20, 30, 40]t )