mahout-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Dmitriy Lyubimov <dlie...@gmail.com>
Subject Re: Detecting rank-deficiency, or worse, via QR decomposition
Date Thu, 18 Jul 2013 22:35:42 GMT
On Thu, Apr 4, 2013 at 3:11 PM, Ted Dunning <ted.dunning@gmail.com> wrote:

> On Thu, Apr 4, 2013 at 4:16 PM, Koobas <koobas@gmail.com> wrote:
>
> > > The Mahout QR that I whipped up a couple of months ago is not rank
> > > revealing, but it is pretty easy to convert the Gram-Schmidt algorithm
> to
> > > be such.  The SVD we have should work just fine.
> > >
> > > Mahout QR uses Gram-Schmidt?
> > Wouldn't it be better to use Householder?
>
>
> One would think so.
>
> But the situation is that I can do Gram Schmidt from memory so I did that.
>
> And then I tested the speed and found it to be nearly 10x faster than the
> older Householder method.  At first I attributed this to the fact that my
> GS method was very vector oriented and the HH method used a lot of element
> accesses.  Accuracy seemed uniformly better as well which is another
> surprise.
>
> But then I started trying to build a HH version using vector ops and
> realized  that the likely reason for the speed is actually just due to the
> fact that the matrix is stored in row major form.  The operations in my GS
> implementation are very much row oriented.  The operations in the old HH
> implementation were very column oriented.
>
> It is hard to frame HH in a row major fashion.  I might be able to figure
> out a Given's rotation method that is row oriented.
>

Mahout SSVD already has the row-wise Givens rotation solver . I guess i can
revive that as a standalone in core solver (even row-wise streaming solver
as well) if there's interest.


>
> The payoff is that doing HH well (or Givens) should give about another 2x
> speedup.
>
> The downside is that nobody has time to fix stuff that isn't broken.
>

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message