nalgebra icon indicating copy to clipboard operation
nalgebra copied to clipboard

Change the QR implementation, inspired by LAPACK

Open jannschu opened this issue 5 years ago • 1 comments

I ported some ideas from LAPACK's QR implementation, more specifically from ?ORG2R.

As a result I could increase all epsilons in the test by two order of magnitudes. Also the full computation of the Q matrix is now supported, not only the first min(n, m) columns. I added a new method q_columns for this. The current q() method stayed the same.

The main difference in the implementation seems to be that LAPACK applies the scaling of the Householder vectors at a different point in the code.

Breaking changes

  • The internal representation has changed (is exposed by hidden method qr_internal)
  • For some inputs some column signs flipped of R and Q.
  • Some allocations were added, can be found when searching for work. This resulted in additional allocator bounds. See discussion below.

Things to discuss

  • Currently q_tr_mul borrows self mutably due to an implementation detail although the struct's state will only be changed temporarily inside the method. Ideas to resolve this:
    • Keep as is
    • Use interior mutability
    • Allocate
    • Change affected gerc and gemv call (possible performance penalty)
  • This would be a good occasion to implement #672 for QR
  • The additional work allocations could be done only once by storing a suitable vector in the struct and sharing it. This will result in &mut self or interior mutability.

jannschu avatar May 09 '20 15:05 jannschu