Re: [petsc-users] Parallel QR decomposition

[Jed Brown]

David Sommer  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

Re: [petsc-users] Parallel QR decomposition

[David Sommer]

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
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, 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

Re: [petsc-users] Parallel QR decomposition

[Smith, Barry F.]

  For what purpose do you need a QR? We may have suggestions if we know how you 
want to use it.

   Barry


> On Jul 19, 2018, at 6:51 AM, David Sommer  wrote:
> 
> 
> Hi,
> 
> i was wondering if there is an implementation of parallel qr decomposition in 
> PETSc. I was looking at 
> http://www.mcs.anl.gov/petsc/documentation/linearsolvertable.html
> but all i found was this non-parallel MATLAB-Solver. Am i searching in the 
> wrong place?
> 
> Best regards,
> 
> David Sommer 
> 

Re: [petsc-users] Parallel QR decomposition

[David Sommer]

Thanks a lot.

Am Do., 19. Juli 2018 um 14:07 Uhr schrieb Matthew Knepley <
knep...@gmail.com>:

> On Thu, Jul 19, 2018 at 7:51 AM David Sommer 
> wrote:
>
>>
>> Hi,
>>
>> i was wondering if there is an implementation of parallel qr
>> decomposition in PETSc. I was looking at
>> http://www.mcs.anl.gov/petsc/documentation/linearsolvertable.html
>> but all i found was this non-parallel MATLAB-Solver. Am i searching in
>> the wrong place?
>>
>
> No. There is a TSQR in SLEPc which we will someday absorb, and you can use
> Elemental for
> general parallel QR.
>
>   Thanks,
>
> Matt
>
>
>> Best regards,
>>
>> David Sommer
>> 
>>
>
>
> --
> What most experimenters take for granted before they begin their
> experiments is infinitely more interesting than any results to which their
> experiments lead.
> -- Norbert Wiener
>
> https://www.cse.buffalo.edu/~knepley/ 
>

Re: [petsc-users] Parallel QR decomposition

[Matthew Knepley]

On Thu, Jul 19, 2018 at 7:51 AM David Sommer 
wrote:

>
> Hi,
>
> i was wondering if there is an implementation of parallel qr decomposition
> in PETSc. I was looking at
> http://www.mcs.anl.gov/petsc/documentation/linearsolvertable.html
> but all i found was this non-parallel MATLAB-Solver. Am i searching in the
> wrong place?
>

No. There is a TSQR in SLEPc which we will someday absorb, and you can use
Elemental for
general parallel QR.

  Thanks,

Matt


> Best regards,
>
> David Sommer
> 
>


-- 
What most experimenters take for granted before they begin their
experiments is infinitely more interesting than any results to which their
experiments lead.
-- Norbert Wiener

https://www.cse.buffalo.edu/~knepley/ 

[petsc-users] Parallel QR decomposition

[David Sommer]

Hi,

i was wondering if there is an implementation of parallel qr decomposition
in PETSc. I was looking at
http://www.mcs.anl.gov/petsc/documentation/linearsolvertable.html
but all i found was this non-parallel MATLAB-Solver. Am i searching in the
wrong place?

Best regards,

David Sommer