Rohan Anil Releases Tutorial For Batched QR Factorization GPU Challenge

Here is a tutorial for uninitiated for QR for those wanting to enter the competition.

All you need to know is a little bit of algebra. Here @ means matrix multiplication.

Let A be a 3 x 3 matrix and task is given A can you find Q and R. A special property of Q is that Q @ Q.T = I and R is a upper triangular matrix:

A find Q and R.

Q @ R = A

[ [0, 1, 0], [ [2, 3, 4], [ [0, 5, 6], [1, 0, 0], @ [0, 5, 6], = [2, 3, 4], [0, 0, 1] ] [0, 0, 7] ] [0, 0, 7] ]

The R matrix has a special property:

[ [2, 3, 4], [0, 5, 6], [0, 0, 7] ]

We are generally fine with any R matrix with this structure, see the zeros on the lower triangle.

[ [0, 5, 6], A = [2, 3, 4], [0, 0, 7] ]

First column of A:

[ [0], x = [2], [0] ]

Householder matrix:

[ [0, 1, 0], H = [1, 0, 0], [0, 0, 1] ]

Now compute Hx:

[ [0, 1, 0], [ [0], H x = [1, 0, 0], @ [2], [0, 0, 1] ] [0] ]

[ [2], = [0], [0] ]

Now how do we get H? Well it turns out these are called reflectors. The householder reflectors. Think of putting a mirror on your vector.