New Matrix decomposition methods

Hi,

Is there any plan to add QR decomposition with column pivoting? As far my understanding goes, currently QR factorization is implemented by householder reflection method.

Hi!

Nobody is currently working on this, but adding a QR decomposition with column pivoting would be a great contribution.

O. K. Let me take that up. As I am new, it might take some time. Thanks for the understanding.

Great! Let me know if you have some difficulties. Take your time, there is no rush :wink:

During initial exploration of the QR decomposition code, I understand that reflection_axis_mut function in householder.rs file is the function that does the householder vector computation. Let me explain what I have understood so far,

  1. Computing the norm of the column(which is to be reflected)
  2. compute it’s square root
  3. get the first element of the column
  4. Multiply with square root of the norm
  5. ?? What is the factor computation?: Not able to follow after that.

In addition: What the PermutationSequence::idenitty_generic(nrows) does? It return some weird values:

Permutation matrix: PermutationSequence { len: 0, ipiv: Matrix { data: VecStorage { data: [(140671690439512, 140671690439512), (2, 2), (2, 2), (2, 2), (2, 2)], nrows: Dynamic { value: 5 }, ncols: U1 } }

And I have a doubt as well, currently column.vget_unchecked() always picks the first value in the column. Doesn’t have to pick the diagonal element in that column?
May these be trivial, but as a beginner I am trying to understand. Thanks.

Just Pivoting column with largest value result in similar but not identical result as Octave’s qr. Following is the comparison of results:

Octave:
octave:38> [Q, R, P] = qr(a)
Q =

-0.363803 -0.263542 0.170182 -0.877058
0.606339 -0.734152 -0.292713 -0.087706
-0.606339 -0.225893 -0.741995 0.175412
-0.363803 -0.583557 0.578620 0.438529

R =

-8.24621 -0.48507 3.15296 -2.54662
0.00000 -3.12485 -1.12946 -0.56473
0.00000 0.00000 -0.88495 -0.44247
0.00000 0.00000 0.00000 0.00000

P =

Permutation Matrix

0 0 0 1
0 0 1 0
1 0 0 0
0 1 0 0

nalgebra QR:

q: 

  ┌                                                 ┐
  │  0.36380327   0.4495138 -0.27811676   -0.766965 │
  │ -0.60633904  0.46905798  0.59949684  -0.2300894 │
  │  0.60633904   0.5276902  0.37700298    0.460179 │
  │  0.36380342 -0.54723424  0.64893997 -0.38348228 │
  └                                                 ┘




r: 

  ┌                                                                     ┐
  │         8.246211      -0.97014254       -3.1529627        2.5466237 │
  │                0        3.0097878        0.9772042       0.48860192 │
  │                0                0        1.0506645        0.5253323 │
  │                0                0                0 0.00000014901161 │
  └                                                                     ┘




p: 
PermutationSequence { len: 3, ipiv: Matrix { data: VecStorage { data: [(0, 2), (1, 3), (2, 3), (0, 0)], nrows: Dynamic { value: 4 }, ncols: U1 } } }

Applying the permutations in the specified order, P is identical to that of Octave result. However, the Q and R are not identical. If you could glean some insight where I am wrong that would be of great help.

Thanks.

Finally, I think understood why column.vget_unchecked(): because of row omission at each iteration. Now, I submitted a pull request for QRP: QR with column pivoting along with a test. This is my first contribution ever in a collaborative project and I thank @sebcrozet for his support and encouragement. Hope to contribute more in the coming days. All in all it was a good learning experience.