You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@spark.apache.org by durin <ma...@simon-schaefer.net> on 2014/09/08 06:59:18 UTC
Solving Systems of Linear Equations Using Spark?
Doing a quick Google search, it appears to me that there is a number people
who have implemented algorithms for solving systems of (sparse) linear
equations on Hadoop MapReduce.
However, I can find no such thing for Spark.
Has anyone information on whether there are attempts of creating such an
algorithm for Spark?
--
View this message in context: http://apache-spark-user-list.1001560.n3.nabble.com/Solving-Systems-of-Linear-Equations-Using-Spark-tp13674.html
Sent from the Apache Spark User List mailing list archive at Nabble.com.
---------------------------------------------------------------------
To unsubscribe, e-mail: user-unsubscribe@spark.apache.org
For additional commands, e-mail: user-help@spark.apache.org
Re: Solving Systems of Linear Equations Using Spark?
Posted by Debasish Das <de...@gmail.com>.
Yup...this can be a spark community project...I saw a PR for
that...interested users fine with lgpl/gpl code can make use of it...
On Mon, Sep 8, 2014 at 12:37 PM, Xiangrui Meng <me...@gmail.com> wrote:
> I asked Tim whether he would change the license of SuiteSparse to an
> Apache-friendly license couple months ago, but the answer was no. So I
> don't think we can use SuiteSparse in MLlib through JNI. Please feel
> free to create JIRAs for distributed linear programming and SOCP
> solvers and run the discussion there. I'm very interested since I
> don't really know how to do linear programming in a distributed way.
> -Xiangrui
>
> On Mon, Sep 8, 2014 at 7:12 AM, Debasish Das <de...@gmail.com>
> wrote:
> > Xiangrui,
> >
> > Should I open up a JIRA for this ?
> >
> > Distributed lp/socp solver through ecos/ldl/amd ?
> >
> > I can open source it with gpl license in spark code as that's what our
> legal
> > cleared (apache + gpl becomes gpl) and figure out the right way to call
> > it...ecos is gpl but we can definitely use the jni version of ldl and amd
> > which are lgpl...
> >
> > Let me know.
> >
> > Thanks.
> > Deb
> >
> > On Sep 8, 2014 7:04 AM, "Debasish Das" <de...@gmail.com> wrote:
> >>
> >> Durin,
> >>
> >> I have integrated ecos with spark which uses suitesparse under the hood
> >> for linear equation solves....I have exposed only the qp solver api in
> spark
> >> since I was comparing ip with proximal algorithms but we can expose
> >> suitesparse api as well...jni is used to load up ldl amd and ecos
> libraries.
> >>
> >> Please follow ecos section of my spark summit talk. We can discuss more
> >> but we can formulate interesting things like google's ceres solver's
> trust
> >> region formulation.
> >>
> >>
> >>
> http://spark-summit.org/2014/talk/quadratic-programing-solver-for-non-negative-matrix-factorization-with-spark
> >>
> >> Let me point you to the code so that you can take a look at it.
> >> Suitesparse (ldl and amd) is lgpl but ecos is gpl and therefore I was
> not
> >> sure how straightforward it will be to add the solver to mllib. Our
> legal
> >> was not convinced to add lgpl/gpl code in apache project.
> >>
> >> Could you also detail the usecases you are looking for ? You want a
> >> distributed lp / socp solver where each worker solves a partition of the
> >> constraint and the full objective...and you want to converge to a global
> >> solution using consensus ? Or your problem has more structure to
> partition
> >> the problem cleanly and don't need consensus step (which is what I
> >> implemented in the code)
> >>
> >> Thanks
> >> Deb
> >>
> >> On Sep 7, 2014 11:35 PM, "Xiangrui Meng" <me...@gmail.com> wrote:
> >>>
> >>> You can try LinearRegression with sparse input. It converges the least
> >>> squares solution if the linear system is over-determined, while the
> >>> convergence rate depends on the condition number. Applying standard
> >>> scaling is popular heuristic to reduce the condition number.
> >>>
> >>> If you are interested in sparse direct methods as in SuiteSparse. I'm
> >>> not aware of any effort to do so.
> >>>
> >>> -Xiangrui
> >>>
> >>> ---------------------------------------------------------------------
> >>> To unsubscribe, e-mail: user-unsubscribe@spark.apache.org
> >>> For additional commands, e-mail: user-help@spark.apache.org
> >>>
> >
>
Re: Solving Systems of Linear Equations Using Spark?
Posted by Xiangrui Meng <me...@gmail.com>.
I asked Tim whether he would change the license of SuiteSparse to an
Apache-friendly license couple months ago, but the answer was no. So I
don't think we can use SuiteSparse in MLlib through JNI. Please feel
free to create JIRAs for distributed linear programming and SOCP
solvers and run the discussion there. I'm very interested since I
don't really know how to do linear programming in a distributed way.
-Xiangrui
On Mon, Sep 8, 2014 at 7:12 AM, Debasish Das <de...@gmail.com> wrote:
> Xiangrui,
>
> Should I open up a JIRA for this ?
>
> Distributed lp/socp solver through ecos/ldl/amd ?
>
> I can open source it with gpl license in spark code as that's what our legal
> cleared (apache + gpl becomes gpl) and figure out the right way to call
> it...ecos is gpl but we can definitely use the jni version of ldl and amd
> which are lgpl...
>
> Let me know.
>
> Thanks.
> Deb
>
> On Sep 8, 2014 7:04 AM, "Debasish Das" <de...@gmail.com> wrote:
>>
>> Durin,
>>
>> I have integrated ecos with spark which uses suitesparse under the hood
>> for linear equation solves....I have exposed only the qp solver api in spark
>> since I was comparing ip with proximal algorithms but we can expose
>> suitesparse api as well...jni is used to load up ldl amd and ecos libraries.
>>
>> Please follow ecos section of my spark summit talk. We can discuss more
>> but we can formulate interesting things like google's ceres solver's trust
>> region formulation.
>>
>>
>> http://spark-summit.org/2014/talk/quadratic-programing-solver-for-non-negative-matrix-factorization-with-spark
>>
>> Let me point you to the code so that you can take a look at it.
>> Suitesparse (ldl and amd) is lgpl but ecos is gpl and therefore I was not
>> sure how straightforward it will be to add the solver to mllib. Our legal
>> was not convinced to add lgpl/gpl code in apache project.
>>
>> Could you also detail the usecases you are looking for ? You want a
>> distributed lp / socp solver where each worker solves a partition of the
>> constraint and the full objective...and you want to converge to a global
>> solution using consensus ? Or your problem has more structure to partition
>> the problem cleanly and don't need consensus step (which is what I
>> implemented in the code)
>>
>> Thanks
>> Deb
>>
>> On Sep 7, 2014 11:35 PM, "Xiangrui Meng" <me...@gmail.com> wrote:
>>>
>>> You can try LinearRegression with sparse input. It converges the least
>>> squares solution if the linear system is over-determined, while the
>>> convergence rate depends on the condition number. Applying standard
>>> scaling is popular heuristic to reduce the condition number.
>>>
>>> If you are interested in sparse direct methods as in SuiteSparse. I'm
>>> not aware of any effort to do so.
>>>
>>> -Xiangrui
>>>
>>> ---------------------------------------------------------------------
>>> To unsubscribe, e-mail: user-unsubscribe@spark.apache.org
>>> For additional commands, e-mail: user-help@spark.apache.org
>>>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: user-unsubscribe@spark.apache.org
For additional commands, e-mail: user-help@spark.apache.org
Re: Solving Systems of Linear Equations Using Spark?
Posted by Debasish Das <de...@gmail.com>.
Xiangrui,
Should I open up a JIRA for this ?
Distributed lp/socp solver through ecos/ldl/amd ?
I can open source it with gpl license in spark code as that's what our
legal cleared (apache + gpl becomes gpl) and figure out the right way to
call it...ecos is gpl but we can definitely use the jni version of ldl and
amd which are lgpl...
Let me know.
Thanks.
Deb
On Sep 8, 2014 7:04 AM, "Debasish Das" <de...@gmail.com> wrote:
> Durin,
>
> I have integrated ecos with spark which uses suitesparse under the hood
> for linear equation solves....I have exposed only the qp solver api in
> spark since I was comparing ip with proximal algorithms but we can expose
> suitesparse api as well...jni is used to load up ldl amd and ecos libraries.
>
> Please follow ecos section of my spark summit talk. We can discuss more
> but we can formulate interesting things like google's ceres solver's trust
> region formulation.
>
>
> http://spark-summit.org/2014/talk/quadratic-programing-solver-for-non-negative-matrix-factorization-with-spark
>
> Let me point you to the code so that you can take a look at it.
> Suitesparse (ldl and amd) is lgpl but ecos is gpl and therefore I was not
> sure how straightforward it will be to add the solver to mllib. Our legal
> was not convinced to add lgpl/gpl code in apache project.
>
> Could you also detail the usecases you are looking for ? You want a
> distributed lp / socp solver where each worker solves a partition of the
> constraint and the full objective...and you want to converge to a global
> solution using consensus ? Or your problem has more structure to partition
> the problem cleanly and don't need consensus step (which is what I
> implemented in the code)
>
> Thanks
> Deb
> On Sep 7, 2014 11:35 PM, "Xiangrui Meng" <me...@gmail.com> wrote:
>
>> You can try LinearRegression with sparse input. It converges the least
>> squares solution if the linear system is over-determined, while the
>> convergence rate depends on the condition number. Applying standard
>> scaling is popular heuristic to reduce the condition number.
>>
>> If you are interested in sparse direct methods as in SuiteSparse. I'm
>> not aware of any effort to do so.
>>
>> -Xiangrui
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: user-unsubscribe@spark.apache.org
>> For additional commands, e-mail: user-help@spark.apache.org
>>
>>
Re: Solving Systems of Linear Equations Using Spark?
Posted by durin <ma...@simon-schaefer.net>.
Hey Deb,
sorry for the late answer, I've been travelling and don't have much time yet
until in a few days.
To be precise, it's not me who has to solve the problem, but a person I know
well and who I'd like to help with a possibly faster method. I'll try to
state the facts as well as I know them, but forgive me if something does not
make sense.
The matrix to be solved represents a certain state in a hydrological
transport model. It usually has about 1000 rows and columns, therefore about
a million unknowns. This sparse matrix is symmetric, with values only on the
main and secondary diagonals. After solving this matrix, we get a new state
of the model.
The matrix represents a system of linear equations which are currently
solved iteratively with some defined termination criterion (usually a
difference of less than 10^-5 between two iterations).
The data is discretized using a finite difference method and is usually
solved on a single workstation using a PCG solver implemented in Fortran.
Does this help you and would your code be suited for this purpose?
Best regards,
Simon
--
View this message in context: http://apache-spark-user-list.1001560.n3.nabble.com/Solving-Systems-of-Linear-Equations-Using-Spark-tp13674p14856.html
Sent from the Apache Spark User List mailing list archive at Nabble.com.
---------------------------------------------------------------------
To unsubscribe, e-mail: user-unsubscribe@spark.apache.org
For additional commands, e-mail: user-help@spark.apache.org
Re: Solving Systems of Linear Equations Using Spark?
Posted by Debasish Das <de...@gmail.com>.
Durin,
I have integrated ecos with spark which uses suitesparse under the hood for
linear equation solves....I have exposed only the qp solver api in spark
since I was comparing ip with proximal algorithms but we can expose
suitesparse api as well...jni is used to load up ldl amd and ecos libraries.
Please follow ecos section of my spark summit talk. We can discuss more but
we can formulate interesting things like google's ceres solver's trust
region formulation.
http://spark-summit.org/2014/talk/quadratic-programing-solver-for-non-negative-matrix-factorization-with-spark
Let me point you to the code so that you can take a look at it. Suitesparse
(ldl and amd) is lgpl but ecos is gpl and therefore I was not sure how
straightforward it will be to add the solver to mllib. Our legal was not
convinced to add lgpl/gpl code in apache project.
Could you also detail the usecases you are looking for ? You want a
distributed lp / socp solver where each worker solves a partition of the
constraint and the full objective...and you want to converge to a global
solution using consensus ? Or your problem has more structure to partition
the problem cleanly and don't need consensus step (which is what I
implemented in the code)
Thanks
Deb
On Sep 7, 2014 11:35 PM, "Xiangrui Meng" <me...@gmail.com> wrote:
> You can try LinearRegression with sparse input. It converges the least
> squares solution if the linear system is over-determined, while the
> convergence rate depends on the condition number. Applying standard
> scaling is popular heuristic to reduce the condition number.
>
> If you are interested in sparse direct methods as in SuiteSparse. I'm
> not aware of any effort to do so.
>
> -Xiangrui
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: user-unsubscribe@spark.apache.org
> For additional commands, e-mail: user-help@spark.apache.org
>
>
Re: Solving Systems of Linear Equations Using Spark?
Posted by Xiangrui Meng <me...@gmail.com>.
You can try LinearRegression with sparse input. It converges the least
squares solution if the linear system is over-determined, while the
convergence rate depends on the condition number. Applying standard
scaling is popular heuristic to reduce the condition number.
If you are interested in sparse direct methods as in SuiteSparse. I'm
not aware of any effort to do so.
-Xiangrui
---------------------------------------------------------------------
To unsubscribe, e-mail: user-unsubscribe@spark.apache.org
For additional commands, e-mail: user-help@spark.apache.org
Re: Solving Systems of Linear Equations Using Spark?
Posted by jamaica <my...@gmail.com>.
I wrote some very simple 1-d laplace equation Spark solver.
For details, see here
<http://apache-spark-developers-list.1001551.n3.nabble.com/Differential-Equation-Spark-Solver-td13005.html>
.
If is there anyone who is interested in this, please let me know.
Anyway hope this can help someone.
--
View this message in context: http://apache-spark-user-list.1001560.n3.nabble.com/Solving-Systems-of-Linear-Equations-Using-Spark-tp13674p23601.html
Sent from the Apache Spark User List mailing list archive at Nabble.com.
---------------------------------------------------------------------
To unsubscribe, e-mail: user-unsubscribe@spark.apache.org
For additional commands, e-mail: user-help@spark.apache.org