topic updating a QR decomposition in Intel® oneAPI Math Kernel Library

updating a QR decomposition

Azua_Garcia__Giovann — Sun, 18 Mar 2012 21:02:23 GMT

Hello,

I currently use the function LAPACKE_dgeqrf to compute the full QR decomposition of a matrix A, and this is done as part of an iterative algorithm that keeps appending new rows to A in every iteration.

Is there a function (or combination of functions) in MKL that will allow me to update the previously computed QR factorization whenever I update A with a new row rather than building QR it from scratch each time?

I could not figure out from the manual what the right function would be ...

Many thanks in advance,
Best regards,
Giovanni

updating a QR decomposition

Victor_K_Intel1 — Thu, 22 Mar 2012 07:51:52 GMT

Hi Giovanni,

I try to guess what you need and below is my understanding.
So, you do
A=Q*R

A1=(R )
(a1)
A1=Q1*R2

A2=(R2)
(a2)
A2=Q2*R3
...

At each step the matrix is appened from below with one additional line. Applying QR factorization we get a new upper triangular matrix and repeat the process again and again.
I guess you are looking for the function to make a QR factorization of matrices that appear at each step - upper triangular matrices appended from below with one additional row, right?

Unfortunately, there is no special functionality in MKL LAPACK to solve this task.
However, you canwrite the code based on rotations (combination of DROTMG and DROTM) that will get you the result. The idea is simple - elements of the last row should be anihilated one after each other.First, the element in the first column should be zeroed by applying rotations to the first row and the last row. Second, the element in the second column to be zeroed by applying rotation to the second and the last row, and so on.
I'm affraid the code won't be very fast, though.

WBR
Victor

updating a QR decomposition

Azua_Garcia__Giovann — Tue, 27 Mar 2012 10:55:20 GMT

Hi Victor,

Yes indeed that's what I need to do. The algorithm for this same idea is described in the paper below, section 2.3.1:
http://eprints.ma.man.ac.uk/1192/01/covered/MIMS_ep2008_111.pdf

It will definitely beat recomputing the full QR from scratch each time which is what I am doing now. Do you know of any third party implementation of this algorithm "Add one row" using givens rotations in C or Fortran?

Many thanks in advance,
Best regards,
Giovanni