Uploaded image for project: 'Mahout'
  1. Mahout
  2. MAHOUT-672

Implementation of Conjugate Gradient for solving large linear systems

    Details

    • Type: New Feature
    • Status: Closed
    • Priority: Minor
    • Resolution: Fixed
    • Affects Version/s: 0.5
    • Fix Version/s: 0.6
    • Component/s: Math
    • Labels:
      None

      Description

      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.

        Attachments

        1. mahout-672-111023.patch
          58 kB
          Jonathan Traupman
        2. mahout-672.patch
          58 kB
          Jonathan Traupman
        3. 0001-MAHOUT-672-LSMR-iterative-linear-solver.patch
          24 kB
          Ted Dunning
        4. MAHOUT-672.patch
          3 kB
          Ted Dunning
        5. 0001-MAHOUT-672-LSMR-iterative-linear-solver.patch
          24 kB
          Ted Dunning

          Issue Links

            Activity

              People

              • Assignee:
                Unassigned
                Reporter:
                jtraupman Jonathan Traupman
              • Votes:
                0 Vote for this issue
                Watchers:
                0 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved:

                  Time Tracking

                  Estimated:
                  Original Estimate - 48h
                  48h
                  Remaining:
                  Remaining Estimate - 48h
                  48h
                  Logged:
                  Time Spent - Not Specified
                  Not Specified