[
https://issues.apache.org/jira/browse/MAHOUT-672?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13022396#comment-13022396
]
Jonathan Traupman commented on MAHOUT-672:
------------------------------------------
Yes, I'm talking about the logic inside of things like LanczosSolver. Ted
pointed out that we have a number of algorithms that use matrix/vector multiply
as a fundamental operation but that have special case code to handle certain
common matrix forms. It's a bit redundant to have these cases in each
algorithm. It also means that every time you create new special form matrix,
you have to modify each of these algorithms to handle that form.
I don't think we're suggesting overloading what times() means. Rather, we're
suggesting having subclasses of DistributedRowMatrix (or possibly separate
implementations of VectorIterable) for special form matrices whose internal
representations may be done in a more efficient manner. E.g. define a
"SquaredDistributedMatrix" class that represents a matrix of the form B = A'A.
All the operations, including times() mathematically mean exactly what they
should: B.times(x) means Bx. Under the hood, it will be implemented as A'(Ax)
because it's more efficient, but that implementation detail shouldn't matter or
be exposed to an algorithm that's just interested in doing a matrix/vector
multiply. Likewise for (A + lambda * I) or (A'A + lamdba * I) or (A'A + B'B) or
band-diagonal matrices. The specific implementation of the times() method takes
care of the representational details so that any algorithm that accepts one of
these matrix types can operate on any of them.
> 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
> Attachments: 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
