[
https://issues.apache.org/jira/browse/MAHOUT-672?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13069994#comment-13069994
]
Jonathan Traupman commented on MAHOUT-672:
------------------------------------------
Yes, it is a big a patch...wasn't always this way. Here's a brief summary of
this came to be the monster it is:
- originally, this was just an implementation of a conjugate gradient solver
for linear systems that worked with either normal or distributed matrices.
- Ted mentioned that he had some mostly completed LSMR code that did very
similar stuff and asked if I could integrate it with this patch, which I did.
- a long discussion between Ted, Jake and me ensued about how a lot of
algorithms (e.g. CG, LSMR, Lanczos SVD) all used the same concept of a matrix
that could be multiplied by a vector but that didn't need row-wise or
element-wise access to the data in the matrix. After much back and forth, we
settled on the name "LinearOperator."
The LinearOperator stuff is disruptive to the code base, but it does provide
some nice functionality, too. For example, you can implement things like
preconditioners, diagonal offsets (e.g. ridge regression) and other
transformations to the data efficiently using linear operators without needing
to either actually modify your underlying data set or add the functionality to
the specific algorithm you're using. This was the original motivation behind
it, since I had included a diagonal offset option for low-rank matrices in my
CG code but that wasn't in Ted's LSMR implementation. We decided that it might
be better to put this in some common place that all similar algorithms could
use for free. Since all matrices are linear operators, but the converse isn't
true, it was decided that Matrix should be a subclass of LinearOperator, not
the other way around.
One thing I'm not 100% comfortable with is the parallel interface and class
hierarchies (i.e. LinearOperator, Matrix vs. AbstractLinearOperator,
AbstractMatrix). I'd like to see the interfaces go away in favor of abstract
classes, but I don't recall us reaching any consensus on this.
I have some time to work on this stuff now (after a long busy spell), so if you
can send me specific issues (e.g. the DistributedRowMatrix stuff you mentioned)
I'll try to take a look at it.
> Implementation of Conjugate Gradient for solving large linear systems
> ---------------------------------------------------------------------
>
> Key: MAHOUT-672
> URL: https://issues.apache.org/jira/browse/MAHOUT-672
> Project: Mahout
> Issue Type: New Feature
> Components: Math
> Affects Versions: 0.5
> Reporter: Jonathan Traupman
> Priority: Minor
> Fix For: 0.6
>
> Attachments: 0001-MAHOUT-672-LSMR-iterative-linear-solver.patch,
> 0001-MAHOUT-672-LSMR-iterative-linear-solver.patch, MAHOUT-672.patch,
> MAHOUT-672.patch
>
> Original Estimate: 48h
> Remaining Estimate: 48h
>
> This patch contains an implementation of conjugate gradient, an iterative
> algorithm for solving large linear systems. In particular, it is well suited
> for large sparse systems where a traditional QR or Cholesky decomposition is
> infeasible. Conjugate gradient only works for matrices that are square,
> symmetric, and positive definite (basically the same types where Cholesky
> decomposition is applicable). Systems like these commonly occur in statistics
> and machine learning problems (e.g. regression).
> Both a standard (in memory) solver and a distributed hadoop-based solver
> (basically the standard solver run using a DistributedRowMatrix a la
> DistributedLanczosSolver) are included.
> There is already a version of this algorithm in taste package, but it doesn't
> operate on standard mahout matrix/vector objects, nor does it implement a
> distributed version. I believe this implementation will be more generically
> useful to the community than the specialized one in taste.
> This implementation solves the following types of systems:
> Ax = b, where A is square, symmetric, and positive definite
> A'Ax = b where A is arbitrary but A'A is positive definite. Directly solving
> this system is more efficient than computing A'A explicitly then solving.
> (A + lambda * I)x = b and (A'A + lambda * I)x = b, for systems where A or A'A
> is singular and/or not full rank. This occurs commonly if A is large and
> sparse. Solving a system of this form is used, for example, in ridge
> regression.
> In addition to the normal conjugate gradient solver, this implementation also
> handles preconditioning, and has a sample Jacobi preconditioner included as
> an example. More work will be needed to build more advanced preconditioners
> if desired.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
