[SciPy-Dev] QR decomposition with pivoting (rank revealing QR factorization)

[Ralf Gommers]

On Thu, Jul 21, 2011 at 12:35 AM, Collin Stocks <collinstocks at gmail.com>wrote:

> List,
>
> FYI, my diff can be visualized quite nicely here:
> https://github.com/collinstocks/scipy/compare/master...qr-with-pivoting
>
> Please let me know if there is anything else I should do, or please
> comment on the changes I have made. Once I have some more feedback, I
> will file a pull request.
>
> I made one comment on github, other than that the qr changes look pretty
good to me from a quick glance.

Cheers,
Ralf




> ---------- Forwarded message ----------
> From: Collin Stocks <collinstocks at gmail.com>
> To: scipy-dev at scipy.org
> Date: Wed, 20 Jul 2011 16:27:34 -0400
> Subject: Re: QR decomposition with pivoting (rank revealing QR
> factorization)
> Hi list,
>
> I'm really sorry for not replying directly to the thread before. I
> thought if I changed the subject, that it would behave properly and
> attach my post to the existing thread. Obviously, I was wrong. I have
> reproduced the post here. This is the one that should be replied to, not
> the other.
>
> ---------------------------------------------------------------------
>
> Hi Martin,
>
> I can change the keyword to 'pivoting' without any trouble. I don't
> happen to know anything about reflectors, so I can't really help you
> there at the moment, but perhaps if you gave me more information, I
> could incorporate that into my patch (I'm not certain if doing so would
> be a good idea or not -- please comment).
>
> I'm glad to hear that you think it should be a keyword, as that's what
> I've already done! What do you think about the 'economic' mode, though?
> That is also independent of whether or not finding Q is done.
>
> -- Collin
>
> > Hi List,
> > Hi Collin,
> >
> > coincidentally, I've been working on the same problem,
> > and so I also want to share my two cents:
> >
> > > I have added a boolean keyword argument called 'pivoted' which
> > causes
> > > qr() to perform QR decomposition with pivoting (rank revealing QR
> >
> > I would prefer the keyword "pivoting", since this is how it is usually
> > called.
> >
> > > factorization). Ultimately, 'mode' should probably be used to flag
> > > whether or not this sort of decomposition should be done,
> >
> > I think a keyword is a much better choice. Mode decides whether
> > the second step of finding Q is done or not, which, in principle,
> > has nothing to do with pivoting or not.
> >
> > On the other hand, I opt for a new mode, which I would call
> > "reflectors",
> > which returns the reflectors of Q calculated in the first step of
> > the factorization, some people out there (me) need that result.
> >
> > Greetings
> >
> > Martin
>
>
> ---------- Forwarded message ----------
> From: Collin Stocks <collinstocks at gmail.com>
> To: scipy-dev at scipy.org
> Date: Tue, 19 Jul 2011 23:16:26 -0400
> Subject: QR decomposition with pivoting (rank revealing QR factorization)
> SciPy Development Team,
>
> I would like to bring your attention to a patch I have submitted to
> SciPy involving the scipy.linalg.qr() function. The relevant ticket
> number is #1473, found at http://projects.scipy.org/scipy/ticket/1473.
>
> I have added a boolean keyword argument called 'pivoted' which causes
> qr() to perform QR decomposition with pivoting (rank revealing QR
> factorization). Ultimately, 'mode' should probably be used to flag
> whether or not this sort of decomposition should be done, but for
> backwards-compatibility sake, I have added the functionality through the
> use of a new keyword.
>
> I have also created a bunch of new tests to test this functionality of
> qr(). I believe that these tests are as comprehensive as the existing
> tests for the same function.
>
> I hope that this is able to make it into the next release of SciPy. The
> patch I have created should be sufficient to add the requested feature.
>
> Rationale:
> QR decomposition with pivoting is a necessary feature in order to write
> a numpy implementation of the MatLab stepwisefit() function from the
> statistics toolbox which matches the original as closely as possible.
> ``scikits.statsmodels'' has expressed interest in such a function, and I
> have implemented one using cvxopt.lapack.geqp3() for the qr
> decomposition with pivoting. However, this is slow due to copying
> between numpy arrays and cvxopt matrices, and for some reason leads to a
> massive memory leak. In some circumstances, it even seems to lead to a
> segmentation fault. This is clearly unacceptable. A better solution
> would seem to be to add this functionality directly to SciPy.
>
> Sincerely,
> Collin Stocks
>
> _______________________________________________
> SciPy-Dev mailing list
> SciPy-Dev at scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20110721/5a04bd19/attachment.html>