Re: Mahout vectors/matrices/solvers on spark

[Dmitriy Lyubimov <dl...@gmail.com>]

On Wed, Jun 19, 2013 at 12:20 AM, Ted Dunning <te...@gmail.com> wrote:

>
> As far as in-memory solvers, we have:
>
> 1) LR decomposition (tested and kinda fast)
>
> 2) Cholesky decomposition (tested)
>
> 3) SVD (tested)
>

Ted,
so we don't have an eigensolver for the in-core Matrix?

I understand that svd can be solved with an eigen decomposition but not the
other way around, right?

Re: Mahout vectors/matrices/solvers on spark

[Dmitriy Lyubimov <dl...@gmail.com>]

that has occurred to me too. we are not inferring any aggregations really
here. it may turn out that its use beneficial with bigger volumes and real
I/O though. hard to tell. anyway i will probably keep both as an option.


On Tue, Jul 9, 2013 at 7:51 AM, Ted Dunning <te...@gmail.com> wrote:

> Also, it is likely that the combiner has little effect.  This means that
> you are essentially using a vector to serialized single elements.
>
> Sent from my iPhone
>
> On Jul 8, 2013, at 23:13, Dmitriy Lyubimov <dl...@gmail.com> wrote:
>
> > yes that's my working hypothesis. Serializing and combining
> > RandomAccessSparseVectors is slower than elementwise messages.
> >
> >
> > On Mon, Jul 8, 2013 at 11:00 PM, Ted Dunning <te...@gmail.com>
> wrote:
> >
> >> It is common for double serialization to creep into the systems as well.
> >> My guess however is that the primitive serialization is just much faster
> >> than the vector serialization.
> >>
> >> Sent from my iPhone
> >>
> >> On Jul 8, 2013, at 22:55, Dmitriy Lyubimov <dl...@gmail.com> wrote:
> >>
> >>> yes, but it is just a test and I am trying to interpolate results that
> i
> >>> see to bigger volume. sort of. To get some taste of the programming
> model
> >>> performance.
> >>>
> >>> I do get cpu-bound behavior and i hit spark cache 100% of the time. so
> i
> >>> theory, since i am not having spills and i am not doing sorts, it
> should
> >> be
> >>> fairly fast.
> >>>
> >>> I have two algorithms. One just sends elementwise messages to the
> vertex
> >>> representing a row it should be in. Another one is using the same set
> of
> >>> initial messages but also uses Bagel combiners which, the way i
> >> understand
> >>> it, apply combining of elements to form partial vectors before shipping
> >> it
> >>> off to remote vertex paritition. Reasoning here apparently since
> elements
> >>> are combined, there's fewer io. Well, perhaps not in this case so much,
> >>> since we are not really doing any sort of information aggregation. On
> >>> single spark node setup i of course don't have actual io, so it should
> >>> approach speed of in-core copy-by-serialization.
> >>>
> >>> What i am seeing is that elementwise messages work almost two times
> >> faster
> >>> in cpu bound behavior than the version with combiners. it would seem
> the
> >>> culprit is that VectorWritable serialization and then deserialization
> of
> >>> vectorized fragments is considerably slower than serialization of
> >>> elementwise messages containing only primitive types there (target row,
> >>> index, value), even that the latter is significantly larger amount of
> >>> objects as well as data.
> >>>
> >>> Still though, i am trying to convince myself that even using combiners
> >>> should be ok compared to shuffle and sort overhead. But i think in
> >> reality
> >>> it still looks a bit slower than i expected. well i guess i should not
> be
> >>> lazy and benchmark it against Mahout MR-based transpose as well as
> >> spark's
> >>> version of RDD shuffle-and-sort.
> >>>
> >>> anyway, map-only tasks on spark distributed matrices are lightning fast
> >> but
> >>> Bagel serialze/deserialize scatter/gather seems to be much slower than
> >> just
> >>> map-only processing. Perhaps I am doing it wrong somehow.
> >>>
> >>>
> >>> On Mon, Jul 8, 2013 at 10:22 PM, Ted Dunning <te...@gmail.com>
> >> wrote:
> >>>
> >>>> Transpose of that small a matrix should happen in memory.
> >>>>
> >>>> Sent from my iPhone
> >>>>
> >>>> On Jul 8, 2013, at 17:26, Dmitriy Lyubimov <dl...@gmail.com> wrote:
> >>>>
> >>>>> Anybody knows how good (or bad) our performance on matrix transpose?
> >> how
> >>>>> long will it take to transpose a 10M non-zeros with Mahout (if i
> wanted
> >>>> to
> >>>>> setup fully distributed but single node MR cluster?)
> >>>>>
> >>>>> Trying to figure if the numbers i see with Bagel-based Mahout matrix
> >>>>> transposition are any good.
> >>
>

Re: Mahout vectors/matrices/solvers on spark

[Ted Dunning <te...@gmail.com>]

Also, it is likely that the combiner has little effect.  This means that you are essentially using a vector to serialized single elements.  

Sent from my iPhone

On Jul 8, 2013, at 23:13, Dmitriy Lyubimov <dl...@gmail.com> wrote:

> yes that's my working hypothesis. Serializing and combining
> RandomAccessSparseVectors is slower than elementwise messages.
> 
> 
> On Mon, Jul 8, 2013 at 11:00 PM, Ted Dunning <te...@gmail.com> wrote:
> 
>> It is common for double serialization to creep into the systems as well.
>> My guess however is that the primitive serialization is just much faster
>> than the vector serialization.
>> 
>> Sent from my iPhone
>> 
>> On Jul 8, 2013, at 22:55, Dmitriy Lyubimov <dl...@gmail.com> wrote:
>> 
>>> yes, but it is just a test and I am trying to interpolate results that i
>>> see to bigger volume. sort of. To get some taste of the programming model
>>> performance.
>>> 
>>> I do get cpu-bound behavior and i hit spark cache 100% of the time. so i
>>> theory, since i am not having spills and i am not doing sorts, it should
>> be
>>> fairly fast.
>>> 
>>> I have two algorithms. One just sends elementwise messages to the vertex
>>> representing a row it should be in. Another one is using the same set of
>>> initial messages but also uses Bagel combiners which, the way i
>> understand
>>> it, apply combining of elements to form partial vectors before shipping
>> it
>>> off to remote vertex paritition. Reasoning here apparently since elements
>>> are combined, there's fewer io. Well, perhaps not in this case so much,
>>> since we are not really doing any sort of information aggregation. On
>>> single spark node setup i of course don't have actual io, so it should
>>> approach speed of in-core copy-by-serialization.
>>> 
>>> What i am seeing is that elementwise messages work almost two times
>> faster
>>> in cpu bound behavior than the version with combiners. it would seem the
>>> culprit is that VectorWritable serialization and then deserialization of
>>> vectorized fragments is considerably slower than serialization of
>>> elementwise messages containing only primitive types there (target row,
>>> index, value), even that the latter is significantly larger amount of
>>> objects as well as data.
>>> 
>>> Still though, i am trying to convince myself that even using combiners
>>> should be ok compared to shuffle and sort overhead. But i think in
>> reality
>>> it still looks a bit slower than i expected. well i guess i should not be
>>> lazy and benchmark it against Mahout MR-based transpose as well as
>> spark's
>>> version of RDD shuffle-and-sort.
>>> 
>>> anyway, map-only tasks on spark distributed matrices are lightning fast
>> but
>>> Bagel serialze/deserialize scatter/gather seems to be much slower than
>> just
>>> map-only processing. Perhaps I am doing it wrong somehow.
>>> 
>>> 
>>> On Mon, Jul 8, 2013 at 10:22 PM, Ted Dunning <te...@gmail.com>
>> wrote:
>>> 
>>>> Transpose of that small a matrix should happen in memory.
>>>> 
>>>> Sent from my iPhone
>>>> 
>>>> On Jul 8, 2013, at 17:26, Dmitriy Lyubimov <dl...@gmail.com> wrote:
>>>> 
>>>>> Anybody knows how good (or bad) our performance on matrix transpose?
>> how
>>>>> long will it take to transpose a 10M non-zeros with Mahout (if i wanted
>>>> to
>>>>> setup fully distributed but single node MR cluster?)
>>>>> 
>>>>> Trying to figure if the numbers i see with Bagel-based Mahout matrix
>>>>> transposition are any good.
>> 

Re: Mahout vectors/matrices/solvers on spark

[Dmitriy Lyubimov <dl...@gmail.com>]

yes that's my working hypothesis. Serializing and combining
RandomAccessSparseVectors is slower than elementwise messages.


On Mon, Jul 8, 2013 at 11:00 PM, Ted Dunning <te...@gmail.com> wrote:

> It is common for double serialization to creep into the systems as well.
>  My guess however is that the primitive serialization is just much faster
> than the vector serialization.
>
> Sent from my iPhone
>
> On Jul 8, 2013, at 22:55, Dmitriy Lyubimov <dl...@gmail.com> wrote:
>
> > yes, but it is just a test and I am trying to interpolate results that i
> > see to bigger volume. sort of. To get some taste of the programming model
> > performance.
> >
> > I do get cpu-bound behavior and i hit spark cache 100% of the time. so i
> > theory, since i am not having spills and i am not doing sorts, it should
> be
> > fairly fast.
> >
> > I have two algorithms. One just sends elementwise messages to the vertex
> > representing a row it should be in. Another one is using the same set of
> > initial messages but also uses Bagel combiners which, the way i
> understand
> > it, apply combining of elements to form partial vectors before shipping
> it
> > off to remote vertex paritition. Reasoning here apparently since elements
> > are combined, there's fewer io. Well, perhaps not in this case so much,
> > since we are not really doing any sort of information aggregation. On
> > single spark node setup i of course don't have actual io, so it should
> > approach speed of in-core copy-by-serialization.
> >
> > What i am seeing is that elementwise messages work almost two times
> faster
> > in cpu bound behavior than the version with combiners. it would seem the
> > culprit is that VectorWritable serialization and then deserialization of
> > vectorized fragments is considerably slower than serialization of
> > elementwise messages containing only primitive types there (target row,
> > index, value), even that the latter is significantly larger amount of
> > objects as well as data.
> >
> > Still though, i am trying to convince myself that even using combiners
> > should be ok compared to shuffle and sort overhead. But i think in
> reality
> > it still looks a bit slower than i expected. well i guess i should not be
> > lazy and benchmark it against Mahout MR-based transpose as well as
> spark's
> > version of RDD shuffle-and-sort.
> >
> > anyway, map-only tasks on spark distributed matrices are lightning fast
> but
> > Bagel serialze/deserialize scatter/gather seems to be much slower than
> just
> > map-only processing. Perhaps I am doing it wrong somehow.
> >
> >
> > On Mon, Jul 8, 2013 at 10:22 PM, Ted Dunning <te...@gmail.com>
> wrote:
> >
> >> Transpose of that small a matrix should happen in memory.
> >>
> >> Sent from my iPhone
> >>
> >> On Jul 8, 2013, at 17:26, Dmitriy Lyubimov <dl...@gmail.com> wrote:
> >>
> >>> Anybody knows how good (or bad) our performance on matrix transpose?
> how
> >>> long will it take to transpose a 10M non-zeros with Mahout (if i wanted
> >> to
> >>> setup fully distributed but single node MR cluster?)
> >>>
> >>> Trying to figure if the numbers i see with Bagel-based Mahout matrix
> >>> transposition are any good.
> >>
>

Re: Mahout vectors/matrices/solvers on spark

[Ted Dunning <te...@gmail.com>]

It is common for double serialization to creep into the systems as well.  My guess however is that the primitive serialization is just much faster than the vector serialization.  

Sent from my iPhone

On Jul 8, 2013, at 22:55, Dmitriy Lyubimov <dl...@gmail.com> wrote:

> yes, but it is just a test and I am trying to interpolate results that i
> see to bigger volume. sort of. To get some taste of the programming model
> performance.
> 
> I do get cpu-bound behavior and i hit spark cache 100% of the time. so i
> theory, since i am not having spills and i am not doing sorts, it should be
> fairly fast.
> 
> I have two algorithms. One just sends elementwise messages to the vertex
> representing a row it should be in. Another one is using the same set of
> initial messages but also uses Bagel combiners which, the way i understand
> it, apply combining of elements to form partial vectors before shipping it
> off to remote vertex paritition. Reasoning here apparently since elements
> are combined, there's fewer io. Well, perhaps not in this case so much,
> since we are not really doing any sort of information aggregation. On
> single spark node setup i of course don't have actual io, so it should
> approach speed of in-core copy-by-serialization.
> 
> What i am seeing is that elementwise messages work almost two times faster
> in cpu bound behavior than the version with combiners. it would seem the
> culprit is that VectorWritable serialization and then deserialization of
> vectorized fragments is considerably slower than serialization of
> elementwise messages containing only primitive types there (target row,
> index, value), even that the latter is significantly larger amount of
> objects as well as data.
> 
> Still though, i am trying to convince myself that even using combiners
> should be ok compared to shuffle and sort overhead. But i think in reality
> it still looks a bit slower than i expected. well i guess i should not be
> lazy and benchmark it against Mahout MR-based transpose as well as spark's
> version of RDD shuffle-and-sort.
> 
> anyway, map-only tasks on spark distributed matrices are lightning fast but
> Bagel serialze/deserialize scatter/gather seems to be much slower than just
> map-only processing. Perhaps I am doing it wrong somehow.
> 
> 
> On Mon, Jul 8, 2013 at 10:22 PM, Ted Dunning <te...@gmail.com> wrote:
> 
>> Transpose of that small a matrix should happen in memory.
>> 
>> Sent from my iPhone
>> 
>> On Jul 8, 2013, at 17:26, Dmitriy Lyubimov <dl...@gmail.com> wrote:
>> 
>>> Anybody knows how good (or bad) our performance on matrix transpose? how
>>> long will it take to transpose a 10M non-zeros with Mahout (if i wanted
>> to
>>> setup fully distributed but single node MR cluster?)
>>> 
>>> Trying to figure if the numbers i see with Bagel-based Mahout matrix
>>> transposition are any good.
>> 

Re: Mahout vectors/matrices/solvers on spark

[Dmitriy Lyubimov <dl...@gmail.com>]

yes, but it is just a test and I am trying to interpolate results that i
see to bigger volume. sort of. To get some taste of the programming model
performance.

I do get cpu-bound behavior and i hit spark cache 100% of the time. so i
theory, since i am not having spills and i am not doing sorts, it should be
fairly fast.

I have two algorithms. One just sends elementwise messages to the vertex
representing a row it should be in. Another one is using the same set of
initial messages but also uses Bagel combiners which, the way i understand
it, apply combining of elements to form partial vectors before shipping it
off to remote vertex paritition. Reasoning here apparently since elements
are combined, there's fewer io. Well, perhaps not in this case so much,
since we are not really doing any sort of information aggregation. On
single spark node setup i of course don't have actual io, so it should
approach speed of in-core copy-by-serialization.

What i am seeing is that elementwise messages work almost two times faster
in cpu bound behavior than the version with combiners. it would seem the
culprit is that VectorWritable serialization and then deserialization of
vectorized fragments is considerably slower than serialization of
elementwise messages containing only primitive types there (target row,
index, value), even that the latter is significantly larger amount of
objects as well as data.

Still though, i am trying to convince myself that even using combiners
should be ok compared to shuffle and sort overhead. But i think in reality
it still looks a bit slower than i expected. well i guess i should not be
lazy and benchmark it against Mahout MR-based transpose as well as spark's
version of RDD shuffle-and-sort.

anyway, map-only tasks on spark distributed matrices are lightning fast but
Bagel serialze/deserialize scatter/gather seems to be much slower than just
map-only processing. Perhaps I am doing it wrong somehow.


On Mon, Jul 8, 2013 at 10:22 PM, Ted Dunning <te...@gmail.com> wrote:

> Transpose of that small a matrix should happen in memory.
>
> Sent from my iPhone
>
> On Jul 8, 2013, at 17:26, Dmitriy Lyubimov <dl...@gmail.com> wrote:
>
> > Anybody knows how good (or bad) our performance on matrix transpose? how
> > long will it take to transpose a 10M non-zeros with Mahout (if i wanted
> to
> > setup fully distributed but single node MR cluster?)
> >
> > Trying to figure if the numbers i see with Bagel-based Mahout matrix
> > transposition are any good.
>

Re: Mahout vectors/matrices/solvers on spark

[Ted Dunning <te...@gmail.com>]

Transpose of that small a matrix should happen in memory. 

Sent from my iPhone

On Jul 8, 2013, at 17:26, Dmitriy Lyubimov <dl...@gmail.com> wrote:

> Anybody knows how good (or bad) our performance on matrix transpose? how
> long will it take to transpose a 10M non-zeros with Mahout (if i wanted to
> setup fully distributed but single node MR cluster?)
> 
> Trying to figure if the numbers i see with Bagel-based Mahout matrix
> transposition are any good.

Re: Mahout vectors/matrices/solvers on spark

[Dmitriy Lyubimov <dl...@gmail.com>]

Anybody knows how good (or bad) our performance on matrix transpose? how
long will it take to transpose a 10M non-zeros with Mahout (if i wanted to
setup fully distributed but single node MR cluster?)

Trying to figure if the numbers i see with Bagel-based Mahout matrix
transposition are any good.

Re: Mahout vectors/matrices/solvers on spark

[Dmitriy Lyubimov <dl...@gmail.com>]

On Fri, Jul 5, 2013 at 1:40 AM, Nick Pentreath <ni...@gmail.com>wrote:

> Hi Dmitry
>
>
> You can take a look at using the update "magic" method which is similar
> to apply but handles assignment.
>
>
>
> If you want to keep the := as assignment I think you could do
>
>
> def :=(value: Double) = update ...
>


>
> (I don't have my laptop around at the moment so can't check this works).
>
>
> Also you can take a dig into the Breeze code which has a pretty similar
> DSL to what you're trying to put together, for examples of how David has
> done it - ignoring the code that is related to all the


As far as i can tell by either documentation or code, Breeze does not
implement single element assignment thru := operator (as in A(5,2) := 3.0),
but thru  update(row,col) method only. (I studied and tried breeze's linalg
package quite a bit).

update() method in Mahout is actually replaced by safe set(r,c) or unsafe
setQuick(r,c), so i don't see a point to implement yet another method
(although update() is more in line with scala conventions, much as set() is
with java's)


operators and specializing for Int, Double and Float, the core DSL is
> fairly compact I think.
>
>
> N
>
> —
> Sent from Mailbox for iPhone
>
> On Fri, Jul 5, 2013 at 10:16 AM, Dmitriy Lyubimov <dl...@gmail.com>
> wrote:
>
> > For anyone good at scala DSLs, the following is the puzzle i can't seem
> to
> > figure at the moment.
> > I mentioned  before that I implemented assignment notations to a row or a
> > block, e.g. for a row vector : A(5,::) := (1,2,3)
> > what it really translates into in this particular case is
> > A.viewRow(5).assign(new Vector(new double[]{1,2,3}))
> > One thing i can't quite figure for in-core matrix DSL is how to translate
> > element assignments such as
> > A(5,5) := 2.0
> > into A.setQuick(5,5,2.0)
> > while still having
> > val k = A(5,5)
> > translating into
> > val k = A.getQuick(5,5).
> > it could be implemented with a "elementView" analogue but would require
> the
> > element view object creation  -- which is, first,  a big no-no (too
> > expensive) for a simple solitary element assignment (or read-out)
> > operation, and secondly, reading the element such as A(5,5) * 2.0 would
> > also involve view element object creation with implicit conversion to
> > Double whereas it is not even needed at all in this case.
> > at this point i have only a very obvious apply(Double,Double):Double =
> > m.getQuick(...), i.e. only element reads are supported with that syntax.
> > I am guessing Jake, if anyone, might have an idea here... thanks.
> > On Thu, Jul 4, 2013 at 11:23 PM, Dmitriy Lyubimov <dl...@gmail.com>
> wrote:
> >> FWIW, Givens streaming qr will be a bit more economical on memory than
> >> Householder's since it doesn't need the full buffer to compute R and
> >> doesn't need to keep entire original matrix around.
> >>
> >>
> >> On Thu, Jul 4, 2013 at 11:15 PM, Dmitriy Lyubimov <dlieu.7@gmail.com
> >wrote:
> >>
> >>> Ted,
> >>>
> >>> would it make sense to port parts of QR in-core row-wise Givens solver
> >>> out of SSVD to work on any Matrix? I know givens method is advertised
> as
> >>> stable but not sure if it is the fastest accepted one. I guess they
> are all
> >>> about the same.
> >>>
> >>> If yes, i will need also to port the UpperTriangular matrix to adhere
> to
> >>> all the bells and wistles, and also have some sort of RowShift matrix
> (a
> >>> much simpler analogue of Pivoted matrix for row-rolled buffers). would
> that
> >>> make sense?
> >>>
> >>> thanks.
> >>> -D
> >>>
> >>>
> >>
>

Re: Mahout vectors/matrices/solvers on spark

[Nick Pentreath <ni...@gmail.com>]

Hi Dmitry


​You can take a look at using the update "magic" method which is similar to apply but handles assignment. 



​If you want to keep the := as assignment I think you could do 


def :=(value: Double) = update ...


(I don't have my laptop around at the moment so can't check this works).


Also you can take a dig into the Breeze code which has a pretty similar DSL to what you're trying to put together, for examples of how David has done it - ignoring the code that is related to all the operators and specializing for Int, Double and Float, the core DSL is fairly compact I think.


N 

—
Sent from Mailbox for iPhone

On Fri, Jul 5, 2013 at 10:16 AM, Dmitriy Lyubimov <dl...@gmail.com>
wrote:

> For anyone good at scala DSLs, the following is the puzzle i can't seem to
> figure at the moment.
> I mentioned  before that I implemented assignment notations to a row or a
> block, e.g. for a row vector : A(5,::) := (1,2,3)
> what it really translates into in this particular case is
> A.viewRow(5).assign(new Vector(new double[]{1,2,3}))
> One thing i can't quite figure for in-core matrix DSL is how to translate
> element assignments such as
> A(5,5) := 2.0
> into A.setQuick(5,5,2.0)
> while still having
> val k = A(5,5)
> translating into
> val k = A.getQuick(5,5).
> it could be implemented with a "elementView" analogue but would require the
> element view object creation  -- which is, first,  a big no-no (too
> expensive) for a simple solitary element assignment (or read-out)
> operation, and secondly, reading the element such as A(5,5) * 2.0 would
> also involve view element object creation with implicit conversion to
> Double whereas it is not even needed at all in this case.
> at this point i have only a very obvious apply(Double,Double):Double =
> m.getQuick(...), i.e. only element reads are supported with that syntax.
> I am guessing Jake, if anyone, might have an idea here... thanks.
> On Thu, Jul 4, 2013 at 11:23 PM, Dmitriy Lyubimov <dl...@gmail.com> wrote:
>> FWIW, Givens streaming qr will be a bit more economical on memory than
>> Householder's since it doesn't need the full buffer to compute R and
>> doesn't need to keep entire original matrix around.
>>
>>
>> On Thu, Jul 4, 2013 at 11:15 PM, Dmitriy Lyubimov <dl...@gmail.com>wrote:
>>
>>> Ted,
>>>
>>> would it make sense to port parts of QR in-core row-wise Givens solver
>>> out of SSVD to work on any Matrix? I know givens method is advertised as
>>> stable but not sure if it is the fastest accepted one. I guess they are all
>>> about the same.
>>>
>>> If yes, i will need also to port the UpperTriangular matrix to adhere to
>>> all the bells and wistles, and also have some sort of RowShift matrix (a
>>> much simpler analogue of Pivoted matrix for row-rolled buffers). would that
>>> make sense?
>>>
>>> thanks.
>>> -D
>>>
>>>
>>

Re: Mahout vectors/matrices/solvers on spark

[Ted Dunning <te...@gmail.com>]

On Fri, Jul 5, 2013 at 1:25 AM, Jake Mannix <ja...@gmail.com> wrote:

> > at this point i have only a very obvious apply(Double,Double):Double =
> > m.getQuick(...), i.e. only element reads are supported with that syntax.
> >
> > I am guessing Jake, if anyone, might have an idea here... thanks.
> >
>
> Hmmm... right off the top of my head, no.  But my play-DSL is pretty
> free of operators, as that level of scala cleverness worries me a little,
> when it comes to making sure we're sticking to efficient operations
> under the hood.


I don't know how to make something like that work without some pretty
clever lazy evaluation juju.

Re: Mahout vectors/matrices/solvers on spark

[Jake Mannix <ja...@gmail.com>]

On Fri, Jul 5, 2013 at 1:15 AM, Dmitriy Lyubimov <dl...@gmail.com> wrote:

> For anyone good at scala DSLs, the following is the puzzle i can't seem to
> figure at the moment.
>
> I mentioned  before that I implemented assignment notations to a row or a
> block, e.g. for a row vector : A(5,::) := (1,2,3)
>
> what it really translates into in this particular case is
>
> A.viewRow(5).assign(new Vector(new double[]{1,2,3}))
>
>
> One thing i can't quite figure for in-core matrix DSL is how to translate
> element assignments such as
>
> A(5,5) := 2.0
>
> into A.setQuick(5,5,2.0)
>
> while still having
>
> val k = A(5,5)
>
> translating into
> val k = A.getQuick(5,5).
>
>
> it could be implemented with a "elementView" analogue but would require the
> element view object creation  -- which is, first,  a big no-no (too
> expensive) for a simple solitary element assignment (or read-out)
> operation, and secondly, reading the element such as A(5,5) * 2.0 would
> also involve view element object creation with implicit conversion to
> Double whereas it is not even needed at all in this case.
>
> at this point i have only a very obvious apply(Double,Double):Double =
> m.getQuick(...), i.e. only element reads are supported with that syntax.
>
> I am guessing Jake, if anyone, might have an idea here... thanks.
>

Hmmm... right off the top of my head, no.  But my play-DSL is pretty
free of operators, as that level of scala cleverness worries me a little,
when it comes to making sure we're sticking to efficient operations
under the hood.


>
>
>
> On Thu, Jul 4, 2013 at 11:23 PM, Dmitriy Lyubimov <dl...@gmail.com>
> wrote:
>
> > FWIW, Givens streaming qr will be a bit more economical on memory than
> > Householder's since it doesn't need the full buffer to compute R and
> > doesn't need to keep entire original matrix around.
> >
> >
> > On Thu, Jul 4, 2013 at 11:15 PM, Dmitriy Lyubimov <dlieu.7@gmail.com
> >wrote:
> >
> >> Ted,
> >>
> >> would it make sense to port parts of QR in-core row-wise Givens solver
> >> out of SSVD to work on any Matrix? I know givens method is advertised as
> >> stable but not sure if it is the fastest accepted one. I guess they are
> all
> >> about the same.
> >>
> >> If yes, i will need also to port the UpperTriangular matrix to adhere to
> >> all the bells and wistles, and also have some sort of RowShift matrix (a
> >> much simpler analogue of Pivoted matrix for row-rolled buffers). would
> that
> >> make sense?
> >>
> >> thanks.
> >> -D
> >>
> >>
> >
>



-- 

  -jake

Re: Mahout vectors/matrices/solvers on spark

[Dmitriy Lyubimov <dl...@gmail.com>]

For anyone good at scala DSLs, the following is the puzzle i can't seem to
figure at the moment.

I mentioned  before that I implemented assignment notations to a row or a
block, e.g. for a row vector : A(5,::) := (1,2,3)

what it really translates into in this particular case is

A.viewRow(5).assign(new Vector(new double[]{1,2,3}))


One thing i can't quite figure for in-core matrix DSL is how to translate
element assignments such as

A(5,5) := 2.0

into A.setQuick(5,5,2.0)

while still having

val k = A(5,5)

translating into
val k = A.getQuick(5,5).


it could be implemented with a "elementView" analogue but would require the
element view object creation  -- which is, first,  a big no-no (too
expensive) for a simple solitary element assignment (or read-out)
operation, and secondly, reading the element such as A(5,5) * 2.0 would
also involve view element object creation with implicit conversion to
Double whereas it is not even needed at all in this case.

at this point i have only a very obvious apply(Double,Double):Double =
m.getQuick(...), i.e. only element reads are supported with that syntax.

I am guessing Jake, if anyone, might have an idea here... thanks.



On Thu, Jul 4, 2013 at 11:23 PM, Dmitriy Lyubimov <dl...@gmail.com> wrote:

> FWIW, Givens streaming qr will be a bit more economical on memory than
> Householder's since it doesn't need the full buffer to compute R and
> doesn't need to keep entire original matrix around.
>
>
> On Thu, Jul 4, 2013 at 11:15 PM, Dmitriy Lyubimov <dl...@gmail.com>wrote:
>
>> Ted,
>>
>> would it make sense to port parts of QR in-core row-wise Givens solver
>> out of SSVD to work on any Matrix? I know givens method is advertised as
>> stable but not sure if it is the fastest accepted one. I guess they are all
>> about the same.
>>
>> If yes, i will need also to port the UpperTriangular matrix to adhere to
>> all the bells and wistles, and also have some sort of RowShift matrix (a
>> much simpler analogue of Pivoted matrix for row-rolled buffers). would that
>> make sense?
>>
>> thanks.
>> -D
>>
>>
>

Re: Mahout vectors/matrices/solvers on spark

[Dmitriy Lyubimov <dl...@gmail.com>]

FWIW, Givens streaming qr will be a bit more economical on memory than
Householder's since it doesn't need the full buffer to compute R and
doesn't need to keep entire original matrix around.


On Thu, Jul 4, 2013 at 11:15 PM, Dmitriy Lyubimov <dl...@gmail.com> wrote:

> Ted,
>
> would it make sense to port parts of QR in-core row-wise Givens solver out
> of SSVD to work on any Matrix? I know givens method is advertised as stable
> but not sure if it is the fastest accepted one. I guess they are all about
> the same.
>
> If yes, i will need also to port the UpperTriangular matrix to adhere to
> all the bells and wistles, and also have some sort of RowShift matrix (a
> much simpler analogue of Pivoted matrix for row-rolled buffers). would that
> make sense?
>
> thanks.
> -D
>
>

Re: Mahout vectors/matrices/solvers on spark

[Dmitriy Lyubimov <dl...@gmail.com>]

Ted,

would it make sense to port parts of QR in-core row-wise Givens solver out
of SSVD to work on any Matrix? I know givens method is advertised as stable
but not sure if it is the fastest accepted one. I guess they are all about
the same.

If yes, i will need also to port the UpperTriangular matrix to adhere to
all the bells and wistles, and also have some sort of RowShift matrix (a
much simpler analogue of Pivoted matrix for row-rolled buffers). would that
make sense?

thanks.
-D

Re: Mahout vectors/matrices/solvers on spark

[Ted Dunning <te...@gmail.com>]

This is pretty exciting!

Thanks Dmitriy.


On Wed, Jul 3, 2013 at 10:12 PM, Dmitriy Lyubimov <dl...@gmail.com> wrote:

> Excellent!
>
> so I guess SSVD can be divorced from apache-math solver then.
>
> Actually it all shaping up surprisingly well, with scala DSL for both
> in-core and mahout DRMS and spark solvers. I haven't been able to pay as
> much attention to this as i hoped due to being pretty sick last month. But
> even with very few time, I think DRM+DSL drivers and in-core scala DSL for
> this might earn much easier acceptance for in-core and distributed linear
> algebra in Mahout. Not to mention memory-cached DRM spark representation is
> a door to iterative solvers. It's been coming together quite nicely and
> in-core eigen decomposition makes it a really rounded offer. (i of course
> was after eigen for the spark version of SSVD/PCA).
>
> I guess i will report back when i get basic Bagel-based primitives working
> for DRMs.
>
>
> On Wed, Jul 3, 2013 at 8:53 PM, Ted Dunning <te...@gmail.com> wrote:
>
> > On Wed, Jul 3, 2013 at 6:25 PM, Dmitriy Lyubimov <dl...@gmail.com>
> > wrote:
> >
> > > On Wed, Jun 19, 2013 at 12:20 AM, Ted Dunning <te...@gmail.com>
> > > wrote:
> > >
> > > >
> > > > As far as in-memory solvers, we have:
> > > >
> > > > 1) LR decomposition (tested and kinda fast)
> > > >
> > > > 2) Cholesky decomposition (tested)
> > > >
> > > > 3) SVD (tested)
> > > >
> > >
> > > Ted,
> > > so we don't have an eigensolver for the in-core Matrix?
> > >
> >
> > Yes.  We do.
> >
> > See org.apache.mahout.math.solver.EigenDecomposition
> >
> > Looking at the history, I am slightly surprised to see that I was the one
> > who copied it from JAMA, replacing the Colt version and adding tests.
> >
> >
> > > I understand that svd can be solved with an eigen decomposition but not
> > the
> > > other way around, right?
> > >
> >
> > Well, the eigen decomposition of the normal matrix can give the SVD, but
> > this is often not recommended due to poor conditioning.  In fact, the
> eigen
> > decomposition of any positive definite matrix is the same as the SVD.
> >
> > Where eigen values are complex, it is common to decompose to a block
> > diagonal form where real values are on the diagonal and complex
> > eigen-values are represented as 2x2 blocks.  Our decomposition does this.
> >
>

Re: Mahout vectors/matrices/solvers on spark

[Dmitriy Lyubimov <dl...@gmail.com>]

Excellent!

so I guess SSVD can be divorced from apache-math solver then.

Actually it all shaping up surprisingly well, with scala DSL for both
in-core and mahout DRMS and spark solvers. I haven't been able to pay as
much attention to this as i hoped due to being pretty sick last month. But
even with very few time, I think DRM+DSL drivers and in-core scala DSL for
this might earn much easier acceptance for in-core and distributed linear
algebra in Mahout. Not to mention memory-cached DRM spark representation is
a door to iterative solvers. It's been coming together quite nicely and
in-core eigen decomposition makes it a really rounded offer. (i of course
was after eigen for the spark version of SSVD/PCA).

I guess i will report back when i get basic Bagel-based primitives working
for DRMs.


On Wed, Jul 3, 2013 at 8:53 PM, Ted Dunning <te...@gmail.com> wrote:

> On Wed, Jul 3, 2013 at 6:25 PM, Dmitriy Lyubimov <dl...@gmail.com>
> wrote:
>
> > On Wed, Jun 19, 2013 at 12:20 AM, Ted Dunning <te...@gmail.com>
> > wrote:
> >
> > >
> > > As far as in-memory solvers, we have:
> > >
> > > 1) LR decomposition (tested and kinda fast)
> > >
> > > 2) Cholesky decomposition (tested)
> > >
> > > 3) SVD (tested)
> > >
> >
> > Ted,
> > so we don't have an eigensolver for the in-core Matrix?
> >
>
> Yes.  We do.
>
> See org.apache.mahout.math.solver.EigenDecomposition
>
> Looking at the history, I am slightly surprised to see that I was the one
> who copied it from JAMA, replacing the Colt version and adding tests.
>
>
> > I understand that svd can be solved with an eigen decomposition but not
> the
> > other way around, right?
> >
>
> Well, the eigen decomposition of the normal matrix can give the SVD, but
> this is often not recommended due to poor conditioning.  In fact, the eigen
> decomposition of any positive definite matrix is the same as the SVD.
>
> Where eigen values are complex, it is common to decompose to a block
> diagonal form where real values are on the diagonal and complex
> eigen-values are represented as 2x2 blocks.  Our decomposition does this.
>

Re: Mahout vectors/matrices/solvers on spark

[Ted Dunning <te...@gmail.com>]

On Wed, Jul 3, 2013 at 6:25 PM, Dmitriy Lyubimov <dl...@gmail.com> wrote:

> On Wed, Jun 19, 2013 at 12:20 AM, Ted Dunning <te...@gmail.com>
> wrote:
>
> >
> > As far as in-memory solvers, we have:
> >
> > 1) LR decomposition (tested and kinda fast)
> >
> > 2) Cholesky decomposition (tested)
> >
> > 3) SVD (tested)
> >
>
> Ted,
> so we don't have an eigensolver for the in-core Matrix?
>

Yes.  We do.

See org.apache.mahout.math.solver.EigenDecomposition

Looking at the history, I am slightly surprised to see that I was the one
who copied it from JAMA, replacing the Colt version and adding tests.


> I understand that svd can be solved with an eigen decomposition but not the
> other way around, right?
>

Well, the eigen decomposition of the normal matrix can give the SVD, but
this is often not recommended due to poor conditioning.  In fact, the eigen
decomposition of any positive definite matrix is the same as the SVD.

Where eigen values are complex, it is common to decompose to a block
diagonal form where real values are on the diagonal and complex
eigen-values are represented as 2x2 blocks.  Our decomposition does this.