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

[Charles R Harris]

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

>
>
> 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.
>
>
I take that back. The QR algorithms are faster, but the SVD is more robust.
In practice the LAPACK QR algorithm with column pivoting works well for most
things, but there are even faster versions.

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