[SciPy-dev] Why does orth use svd instead of QR ?

[Charles R Harris]

On Fri, Feb 5, 2010 at 12:47 AM, Charles R Harris <charlesr.harris at gmail.com
> wrote:

>
>
> On Fri, Feb 5, 2010 at 12:18 AM, David Cournapeau <david at silveregg.co.jp>wrote:
>
>> Charles R Harris wrote:
>> >
>> >
>> > On Thu, Feb 4, 2010 at 8:45 PM, David Cournapeau <david at silveregg.co.jp
>> > <mailto:david at silveregg.co.jp>> wrote:
>> >
>> >     Hi,
>> >
>> >     I wanted to know if there was a rationale for using svd to
>> >     orthonormalize the columns of a matrix (in scipy.linalg). QR-based
>> >     methods are likely to be much faster, and I thought this was the
>> >     standard, numerically-stable method to orthonormalize a basis ? If
>> the
>> >     reason is to deal with rank-deficient matrices, maybe we could add
>> an
>> >     option to choose between them ?
>> >
>> >
>> > QR with column rotation would deal with rank-deficient matrices and
>> > routines for that are available in LAPACK
>> > <http://netlib.org/lapack/lug/node42.html>. The SVD was probably used
>> > because it was available. The diagonal elements of the R matrix can
>> > somewhat take the place of the singular values when column rotation is
>> used.
>>
>> So would be it ok to use this column-rotated QR in place of svd for
>> every case in orth ? I would have to check that QR with column rotation
>> is still significantly faster than svd, but I would surprised if if were
>> not the case. QR has also the advantage of being implemented in PLASMA
>> already contrary to eigen/svd solvers,
>>
>>
> I don't know how the two methods compare in practice. SVD algorithms
> generally use iterated QR reductions in their implementation, so QR
> reductions can't be worse numerically. But the SVD probably provides a
> better metric for rank determination. A google search turns up some
> literature on the subject that I can't access from home.
>
>
OK, here's a good
reference<http://www.math.sjsu.edu/%7Efoster/rank/rank_revealing_s.pdf>.
A quick look seems to indicate that the  SVD is the way to go.

Chuck
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20100205/76b38e9b/attachment.html>