Any utility to solve the matrix inversion in Map/Reduce Way

[Colin Wang <co...@gmail.com>]

Hi All,

I want to solve the matrix inversion, of course, big size, in Map/Reduce
way.
I don't know if Mahout offers this kind of utility. Could you please give
me some tips?

Thank you,
Colin

Re: Any utility to solve the matrix inversion in Map/Reduce Way

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

This is a relatively small matrix.  You can decompose a matrix like that,
at least approximately in a pretty short time.  With stock R (has no BLAS
acceleration), it takes 9ms to decompose a 100 x 100 dense matrix and 6.2
seconds to decompose a 1K x 1K dense matrix.  Since this is so fast, there
is little point in using Hadoop for this.

HPC guys pretty much never invert a matrix larger than 10x10 unless it is
diagonal or other special form.

Even if you think you need an inverse, usually all you need to do is
multiply by the inverse which is better done using a decomposed form
instead of a real inverse.  Matrix libraries will often cheat a bit and
substitute a matrix object that is really a decomposition when you ask for
an inverse.  Unless you look at the elements of the matrix, they can leave
it at that and you get speed and a warm feeling that you have an inverse
matrix.

One of the major reasons for avoiding the inverse at the size that you are
talking about is that using the inverse directly will probably cause you to
have a large loss of precision.

On Mon, Jan 21, 2013 at 1:12 AM, Colin Wang <colin.bin.wang.mahout@gmail.com
> wrote:

> Hi Koobas,
>
> I am trying on dense matrix in Hadoop, thousand times thousand square size.
> How do HPC guys to solve this problem? Any references?
>
> Thank you,
> Colin
>
> On Mon, Jan 21, 2013 at 11:49 AM, Koobas <ko...@gmail.com> wrote:
>
> > Colin,
> > I am more of an HPC guys.
> > I am a Mahout noob myself.
> > Are we talking about a dense matrix?
> > What size?
> >
> >
> > On Sun, Jan 20, 2013 at 9:34 PM, Colin Wang <
> > colin.bin.wang.mahout@gmail.com
> > > wrote:
> >
> > > Hi Koobas,
> > >
> > > I want the first one. Do you have any suggestions?
> > >
> > > Thank you,
> > > Colin
> > > On Fri, Jan 18, 2013 at 12:49 PM, Koobas <ko...@gmail.com> wrote:
> > >
> > > > Martix inversion
> > >
> >
>

Re: Any utility to solve the matrix inversion in Map/Reduce Way

[Koobas <ko...@gmail.com>]

This is a standard problem in dense linear algebra.
The most established package to solve this problem is LAPACK.
There are newer packages, but this is a good reference point.
You first factor the matrix, DGETRF for a general matrix,
DSYTRF for a symmetric matrix, DPOTRF for a symmetric positive definite
matrix.
Then you call one of the functions: DGETRI, DSYTRI, DPOTRI, to do the rest.
DPOTRI is just a call to DTRTRI (inverse of the triangular factor),
and DLAUUM (triangular matrix multiply).

If you are on a multicore, MKL has that routine decently optimized.
If you are adventurous, you can try an academic package, such as PLASMA.
(May beat MKL on matrix inversion, but still requires MKL for BLAS.)
If you're going for the kill (performance-wise), you can try GPU
acceleration with MAGMA.
My guess is that MAGMA will invert a 20K x 20K matrix for you in the matter
of seconds.


On Mon, Jan 21, 2013 at 1:12 AM, Colin Wang <colin.bin.wang.mahout@gmail.com
> wrote:

> Hi Koobas,
>
> I am trying on dense matrix in Hadoop, thousand times thousand square size.
> How do HPC guys to solve this problem? Any references?
>
> Thank you,
> Colin
>
> On Mon, Jan 21, 2013 at 11:49 AM, Koobas <ko...@gmail.com> wrote:
>
> > Colin,
> > I am more of an HPC guys.
> > I am a Mahout noob myself.
> > Are we talking about a dense matrix?
> > What size?
> >
> >
> > On Sun, Jan 20, 2013 at 9:34 PM, Colin Wang <
> > colin.bin.wang.mahout@gmail.com
> > > wrote:
> >
> > > Hi Koobas,
> > >
> > > I want the first one. Do you have any suggestions?
> > >
> > > Thank you,
> > > Colin
> > > On Fri, Jan 18, 2013 at 12:49 PM, Koobas <ko...@gmail.com> wrote:
> > >
> > > > Martix inversion
> > >
> >
>

Re: Any utility to solve the matrix inversion in Map/Reduce Way

[Colin Wang <co...@gmail.com>]

Hi Koobas,

I am trying on dense matrix in Hadoop, thousand times thousand square size.
How do HPC guys to solve this problem? Any references?

Thank you,
Colin

On Mon, Jan 21, 2013 at 11:49 AM, Koobas <ko...@gmail.com> wrote:

> Colin,
> I am more of an HPC guys.
> I am a Mahout noob myself.
> Are we talking about a dense matrix?
> What size?
>
>
> On Sun, Jan 20, 2013 at 9:34 PM, Colin Wang <
> colin.bin.wang.mahout@gmail.com
> > wrote:
>
> > Hi Koobas,
> >
> > I want the first one. Do you have any suggestions?
> >
> > Thank you,
> > Colin
> > On Fri, Jan 18, 2013 at 12:49 PM, Koobas <ko...@gmail.com> wrote:
> >
> > > Martix inversion
> >
>

Re: Any utility to solve the matrix inversion in Map/Reduce Way

[Koobas <ko...@gmail.com>]

Colin,
I am more of an HPC guys.
I am a Mahout noob myself.
Are we talking about a dense matrix?
What size?


On Sun, Jan 20, 2013 at 9:34 PM, Colin Wang <colin.bin.wang.mahout@gmail.com
> wrote:

> Hi Koobas,
>
> I want the first one. Do you have any suggestions?
>
> Thank you,
> Colin
> On Fri, Jan 18, 2013 at 12:49 PM, Koobas <ko...@gmail.com> wrote:
>
> > Martix inversion
>

Re: Any utility to solve the matrix inversion in Map/Reduce Way

[Colin Wang <co...@gmail.com>]

Hi Koobas,

I want the first one. Do you have any suggestions?

Thank you,
Colin
On Fri, Jan 18, 2013 at 12:49 PM, Koobas <ko...@gmail.com> wrote:

> Martix inversion

Re: Any utility to solve the matrix inversion in Map/Reduce Way

[Colin Wang <co...@gmail.com>]

Hi Sean,

I start to realize that the full inverse may not be realistic.
Matrix decomposition may be a better idea.
But I want to have a try and to show it as negative example in Map/Reduce.

Thank you,
Colin
On Fri, Jan 18, 2013 at 8:10 PM, Sean Owen <sr...@gmail.com> wrote:

> And, do you really need an inverse, or pseudo-inverse?
> But, no, there are really no direct utilities for this. But we could
> probably tell you how to do it efficiently, as long as you don't
> actually mean a full inverse.
>

Re: Any utility to solve the matrix inversion in Map/Reduce Way

[Sean Owen <sr...@gmail.com>]

And, do you really need an inverse, or pseudo-inverse?
But, no, there are really no direct utilities for this. But we could
probably tell you how to do it efficiently, as long as you don't
actually mean a full inverse.

On Fri, Jan 18, 2013 at 11:58 AM, Ted Dunning <te...@gmail.com> wrote:
> Left unsaid in this comment is the fact that matrix inversion of any
> sizable matrix is almost always a mistake because it is (a) inaccurate, (b)
> slow.
>
> In scalable numerics it is also commonly true that the only really scalable
> problems are sparse.  The reason for that is that systems whose cost grows
> with O(n^2) cannot be scaled to arbitrary size n.  Sparse systems with only
> k items on average per row can often be handled with o(n) complexity which
> a requirement for a practical system.
>
> On Thu, Jan 17, 2013 at 8:49 PM, Koobas <ko...@gmail.com> wrote:
>
>> Martix inversion, as in explicitly computing the inverse,
>> e.g. computing variance / covariance,
>> or matrix inversion, as in solving a linear system of equations?
>>
>>
>> On Thu, Jan 17, 2013 at 7:49 PM, Colin Wang <
>> colin.bin.wang.mahout@gmail.com
>> > wrote:
>>
>> > Hi All,
>> >
>> > I want to solve the matrix inversion, of course, big size, in Map/Reduce
>> > way.
>> > I don't know if Mahout offers this kind of utility. Could you please give
>> > me some tips?
>> >
>> > Thank you,
>> > Colin
>> >
>>

Re: Any utility to solve the matrix inversion in Map/Reduce Way

[Colin Wang <co...@gmail.com>]

Hi Ted,

Thank you for the valuable experience.

Colin
On Fri, Jan 18, 2013 at 7:58 PM, Ted Dunning <te...@gmail.com> wrote:

> h O(n^2) cannot be scaled to arbitrary size n.  Sparse systems with only
> k items on average per row can often be handled with o(n) com
>

Re: Any utility to solve the matrix inversion in Map/Reduce Way

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

Left unsaid in this comment is the fact that matrix inversion of any
sizable matrix is almost always a mistake because it is (a) inaccurate, (b)
slow.

In scalable numerics it is also commonly true that the only really scalable
problems are sparse.  The reason for that is that systems whose cost grows
with O(n^2) cannot be scaled to arbitrary size n.  Sparse systems with only
k items on average per row can often be handled with o(n) complexity which
a requirement for a practical system.

On Thu, Jan 17, 2013 at 8:49 PM, Koobas <ko...@gmail.com> wrote:

> Martix inversion, as in explicitly computing the inverse,
> e.g. computing variance / covariance,
> or matrix inversion, as in solving a linear system of equations?
>
>
> On Thu, Jan 17, 2013 at 7:49 PM, Colin Wang <
> colin.bin.wang.mahout@gmail.com
> > wrote:
>
> > Hi All,
> >
> > I want to solve the matrix inversion, of course, big size, in Map/Reduce
> > way.
> > I don't know if Mahout offers this kind of utility. Could you please give
> > me some tips?
> >
> > Thank you,
> > Colin
> >
>

Re: Any utility to solve the matrix inversion in Map/Reduce Way

[Koobas <ko...@gmail.com>]

Martix inversion, as in explicitly computing the inverse,
e.g. computing variance / covariance,
or matrix inversion, as in solving a linear system of equations?


On Thu, Jan 17, 2013 at 7:49 PM, Colin Wang <colin.bin.wang.mahout@gmail.com
> wrote:

> Hi All,
>
> I want to solve the matrix inversion, of course, big size, in Map/Reduce
> way.
> I don't know if Mahout offers this kind of utility. Could you please give
> me some tips?
>
> Thank you,
> Colin
>