[
https://issues.apache.org/jira/browse/MAHOUT-672?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13022377#comment-13022377
]
Jake Mannix commented on MAHOUT-672:
------------------------------------
What flag? Doing (A'A)x vs. (A)x is pretty fundamental to the algorithm. Why
would you prefer to switch choices of which to do based on class type? I can
see how it would make the logic *inside* of something like LanczosSolver
simpler (you just always do "times(vector)", instead of "if symmetric, do
times(), else do timesSquared()"), but if you *really* want to do it generally,
what you want is a mini MapReduce paradigm: define a method which takes a pair
of functions:
Vector DistributedRowMatrix#mapRowsWithCombiner(Vector input,
Function<Vector, Vector> rowMapper, Function<Vector, Vector> resultReducer) {
// for each row, emit Vectors: rowMapper.apply(input, row)
// combine/reduce: for each intermediateOutputRow, output <-
resultReducer.apply(intermediateOutputRow, output)
return output;
}
But I'm not sure this has the right level of generality (too general? Not
general enough?).
I'm definitely not convinced that overloading times() to mean many different
things is really wise. Having it mean (A)x vs. (A + lambda I)x could totally
be fine, however. It's defining the matrix to have a extremely compressed way
of showing it's diagonal.
> 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
>
> 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
