Exposing the linear solvers in the public API - ConjugateGradientsSolver - LinearSolver

[tom.ver...@gmail.com]

Dear all,

I am starting to look at Ceres and really like it so far.

One issue I am facing right now is that I am interested in using its linear solvers for a matrix-free least-squares problem but the API is a non-exposed internal one.

I have read this thread:

https://groups.google.com/forum/#!searchin/ceres-solver/ConjugateGradientsSolver/ceres-solver/rHqiNtGnroE/Ml2ilMGBpuYJ

I understand that "Ceres is not structured as a general purpose nonlinear and linear algebra library" and that "Eigen and pretty much any other linear algebra library has a perfectly capable CG implementation."

However, three reasons would make the use of the CG in ceres useful to me:

• I am planning to already use Ceres for non-linear least squares
• There are not so many nice c++ implementation of matrix-free CG out there
• Ceres and Eigen (http://eigen.tuxfamily.org/dox/group__MatrixfreeSolverExample.html) can do it but the Ceres API is simpler and sufficient for my needs. Also, I haven't tried the Eigen matrix-free CG but I don't quite get how they get away without asking for the adjoint operator

For the record, provided I copy the internal header files from Ceres in my source tree the toy example below currently work for me and looks quite nice.

#include "ceres/ceres.h"
#include "glog/logging.h"

#include "ceres/conjugate_gradients_solver.h"

struct MyLinearOperator : public ceres::internal::LinearOperator {
  virtual ~MyLinearOperator() {
  };

  // y = y + Ax;
  virtual void RightMultiply(const double* x, double* y) const {
    y[0] += x[0] + 0.1*x[1];
    y[1] += 2.0*x[1];
  };
  
  // y = y + A'x;
  virtual void LeftMultiply(const double* x, double* y) const{
    y[0] += x[0];
    y[1] +=  0.1*x[0] + 2.0*x[1];
  };

  virtual int num_rows() const{
    return 2;
  };
  
  virtual int num_cols() const{
    return 2;
  };
};

int main(int argc, char** argv) {
  google::InitGoogleLogging(argv[0]);

  ceres::internal::LinearSolver::Options options;
  options.type = ceres::CGNR;
  options.preconditioner_type = ceres::IDENTITY;
  options.max_num_iterations = 10;

  ceres::internal::LinearSolver::PerSolveOptions per_solve_options;
  per_solve_options.r_tolerance = 1e-9;

  MyLinearOperator myoperator;

  ceres::internal::ConjugateGradientsSolver solver(options);

  double b[] = { 5.0, 4.0 };
  double x[] = { -1.0, 0.0 };

  ceres::internal::LinearSolver::Summary summary =
      solver.Solve(&myoperator, b, per_solve_options, x);

  std::cout << summary.message << "\n";
  std::cout << "x : [0; 0] -> [" << x[0] << "; " << x[1] << "]\n";
  
  return 0;
}

Are there any plans to expose the linear solvers? This would avoid having to copy a bunch of internal header files, and would ease keeping track with updates from Ceres.

As a side question, as I am fairly new to this field, are there any obvious open-source library besides Eigen that I should look into for matrix-free solvers in c++?

Best wishes,

Tom

[Sameer Agarwal]

Currently there are no such plans. It will increase our API surface and expose a bunch of our internals that we do not want to maintain as a public stable dependency. 

That said, I am curious what preconditioner are planning on using in a matrix free method? for anything of reasonable size and complexity you are going to need a non-trivial preconditioner.

 

As a side question, as I am fairly new to this field, are there any obvious open-source library besides Eigen that I should look into for matrix-free solvers in c++?

Sorry, I have not kept track of things here, so I have no idea.

Sameer

 

Best wishes,

Tom

--
You received this message because you are subscribed to the Google Groups "Ceres Solver" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ceres-solver...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/ab63955f-9ed9-4e45-8f4f-82d580c4eebf%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[tom.ver...@gmail.com]

Dear Sameer,

Many thanks for the prompt reply.

I can understand that. Thank you for the clarification.

 

That said, I am curious what preconditioner are planning on using in a matrix free method? for anything of reasonable size and complexity you are going to need a non-trivial preconditioner.

Regarding preconditioner, I am not quite sure what to use yet. I mentioned that the (matrix-free) linear least-squares problem I have in mind is close to an image deconvolution problem. Not sure how important preconditioning is in such a context.

 

 

As a side question, as I am fairly new to this field, are there any obvious open-source library besides Eigen that I should look into for matrix-free solvers in c++?

Sorry, I have not kept track of things here, so I have no idea.

Ok, thanks. For the record in case someone is looking into the same question in the future (or can point me towards a good c++ library for these), I have seen that CGLS, LSQR and LSMR can be used with matrix-free linear operators. While these tools are easy to use from python

http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.linalg.lsmr.html#scipy.sparse.linalg.lsmr

http://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.lsq_linear.html#scipy.optimize.lsq_linear 

http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.linalg.LinearOperator.html#scipy.sparse.linalg.LinearOperator 

they don't seem trivial to use from C++ though.

VNL has a wrapper for LSQR which makes it easier to use from c++ but it's not actively maintained as far as I can see: http://public.kitware.com/vxl/doc/release/core/vnl/html/classvnl__lsqr.html

As suggested in this feature request, it might be interesting to have a similar wrapper in ceres: https://github.com/ceres-solver/ceres-solver/issues/171

Cheers,

Tom

[Sameer Agarwal]

Thanks Tom for the pointers. LSQR/LSMR implementations in Ceres is something I'd like to work on. 

That said, in my experience iterative methods without preconditioning usually leads to a very bad time.

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/1751ec71-0bb7-418c-a4c2-43c8ea8b102b%40googlegroups.com.

[tom.ver...@gmail.com]

On Thursday, June 30, 2016 at 4:02:21 PM UTC+1, Sameer Agarwal wrote:

Thanks Tom for the pointers. LSQR/LSMR implementations in Ceres is something I'd like to work on. 

I just remembered that 6 years ago, I was involved in an effort that lead Luis Ibanez to port LSQR from fortran to c++ for VNL. It's a much cleaner port that a standard f2c type one. I just realised that this effort wasn't backported upstream and that the resulting code was actually a standalone one. For ease of use and to increase it's visibility, I create a standalone github repo for this:

https://github.com/tvercaut/LSQR-cpp

Hopefully this can be useful to other people.

Cheers,

Tom

[Sameer Agarwal]

Thanks Tom.

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/817d1eda-dc1a-4cca-914c-55c13733daa8%40googlegroups.com.