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

[Charles R Harris]

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.

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