[petsc-users] Parallel QR decomposition

[Jed Brown]

David Sommer <david97sommer at gmail.com> writes:

> Hi,
>
> sorry i haven't answered in a while.
>>>  i was wondering if there is an implementation of parallel qr
> decomposition in PETSc.
>>  For what purpose do you need a QR? We may have suggestions if we know
> how you want to use it.
> I found an interesting algorithm for radial basis function interpolation.
> It mitigates the ill-conditioning that arises from making radial basis
> functions increasingly flat. The paper can be found at
> https://amath.colorado.edu/faculty/fornberg/Docs/SISCmanuscript.pdf
> The algorithm defines a Matrix C that is rectangular (more columns than
> rows). Then a QR Decomposition of C is computed. It looks like this:
> C = Q [R1 R2]
> with R1 being rectangular and R2 being stacked on it horizontally. What i
> want to compute in the end is:
> R_1^{-1} R_2

Is R_1 square?  What is a typical shape for C?

> Which isn't that hard to compute once R is known, as this is just backward
> substitution. Anyway i still need to do a full QR decomposition (Even
> though i don't actually need Q, it would be easy to calculate from R, 

That is usually not stable.  You usually want the Q as produced by QR,
preferably the elementary reflector representation.

> so i don't think there is any shortcut to Q, except that i don't have
> to store Q).  What i was thinking of as a possible solution is to
> parallelize Givens rotations by leveraging the fact that it only has
> local row-wise data dependencies in each step.
>
> Best regards
>
> David Sommer