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

[Charles R Harris]

On Fri, Feb 5, 2010 at 1:29 AM, David Cournapeau <david@silveregg.co.jp>wrote:

> Charles R Harris wrote:
> >
> >
> > On Fri, Feb 5, 2010 at 12:47 AM, Charles R Harris
> > <charlesr.harris@gmail.com <mailto:charlesr.harris@gmail.com>> wrote:
> >
> >
> >
> >     On Fri, Feb 5, 2010 at 12:18 AM, David Cournapeau
> >     <david@silveregg.co.jp <mailto:david@silveregg.co.jp>> wrote:
> >
> >         Charles R Harris wrote:
> >          >
> >          >
> >          > On Thu, Feb 4, 2010 at 8:45 PM, David Cournapeau
> >         <david@silveregg.co.jp <mailto:david@silveregg.co.jp>
> >          > <mailto:david@silveregg.co.jp
> >         <mailto:david@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.
>
> AFAIK, SVD is indeed the way to go, but do we really need this for the
> orth function ? I am wrong to think that orthonormalizing a matrix of
> linearly independent vectors is the most common usage for orth ? The
> difference in terms of speed is really significant (for example, svd of
> a 2000x100 matrix takes ~1.9 second vs 0.1 s for QR).
>
>
This looks a bit like sorting: quicksort is almost always fastest, but no
quarantee. The other methods are safer but slower. Maybe the way to go is
use a keyword to choose between methods.

Chuck
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.scipy.org/pipermail/scipy-dev/attachments/20100205/f056c0a7/attachment.html