Accessing matrix elements of class BlockSparseMatrix in SchurComplementSolver

[Diego Coelho]

The question is pretty simple: Can I access matrix elements of class BlockSparseMatrix as I access CompressedRowSparseMatrix?

I came across this class in method SchurComplementSolver::SolveImpl in schur_complement_solver.cc. I checked block_sparse_matrix.h and .cc as well block_structure.h and .cc for more info. I checked out methods RightMultiply and LeftMultiply to have an idea how to access, but it seems to be a bit complex to read.

[Sameer Agarwal]

you can but the layout is more complex. The multiply methods are perhaps the best way to understand the layout. 

what are you trying to do?

On Fri, Jun 17, 2016 at 12:43 PM Diego Coelho <diegof...@gmail.com> wrote:

The question is pretty simple: Can I access matrix elements of class BlockSparseMatrix as I access CompressedRowSparseMatrix?

I came across this class in method SchurComplementSolver::SolveImpl in schur_complement_solver.cc. I checked block_sparse_matrix.h and .cc as well block_structure.h and .cc for more info. I checked out methods RightMultiply and LeftMultiply to have an idea how to access, but it seems to be a bit complex to read.

--
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/895a282f-c61c-4d4e-b6cd-117fd34a540b%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Diego Coelho]

Hi Sammer,

Thanks again. I want to perform 3 different things (one is already done):

(1) Perform matrix-vector operation (which is already implemented by RightMultiply);

(2) Extract the diagonal elements and recondition the matrix ith that. (basically it is use Jacobi preconditoner);

(3) Take the infinity matrix norm (the element with largest magnitude).

If there is a way to access all elements and know their corresponding column and row, that would solve all my problems.

[Sameer Agarwal]

have a look at 

https://github.com/ceres-solver/ceres-solver/blob/master/internal/ceres/block_sparse_matrix.cc#L130

the functions for computing the norm of each column and the one to scale the columns.

Ceres already applies jacobi preconditioning to the jacobian before working with it and these two functions are used for doing that.

Sameer

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/f89c32ac-6970-41e2-8de0-0e491cac3082%40googlegroups.com.

[Diego Coelho]

Hi Sameer,

I want to apply the preconditioner to the normal equation matrix (Hessian), ie.,  J^T*J, not only the Jacobian J. Is there any function for that?

[Sameer Agarwal]

Diego,

Construct a preconditioner and pass it to the CGNR solver and it will do the needful. You can look at the BlockJacobi preconditioner to see how it is done.

Sameer

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/ffced616-6093-4691-be47-daca5c1ad7ec%40googlegroups.com.

[Diego Coelho]

Hi Sameer,

Many thanks. By the way, the matrix J^T*J used on the DENSE_SCHUR option is symmetric. Is ceres storing just half of it or all elements? I went trough the method BlockSparseMatrix::SquaredColumnNorm that you mentioned and I had the impression that ceres tore the whole matrix.

[Sameer Agarwal]

Diego,

On Mon, Jun 20, 2016 at 11:06 AM Diego Coelho <diegof...@gmail.com> wrote:

Hi Sameer,

Many thanks. By the way, the matrix J^T*J used on the DENSE_SCHUR option is symmetric. Is ceres storing just half of it or all elements?

The matrix stored in dense_schur is not J^T J. It is a schur complement and yes only half of it is solved.

Sameer

 

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/743066cd-fefe-48e1-995c-8c33abcdf724%40googlegroups.com.

[Diego Coelho]

Thanks again Sameer. Do you mind if I ask where ceres store J^T*J (if it does) for the DENSE_SCHUR method?

[Sameer Agarwal]

Diego,

We do not store J^TJ for computing the schur complement for DENSE_SCHUR. It is computed implicitly in the process of computing the schur complement.

If you tell me in some more detail as to what is it that you are trying to do, I maybe able to help you better.

Sameer

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/071952c5-4150-431b-881f-f441dfefe0d6%40googlegroups.com.

[Diego Coelho]

Hi Sameer,

Sure. What I am trying to do is approximate the solution of the normal equations without performing any matrix inversion (it is a competing method for CGNR). Suppose we have the normal equations, i.e., the Hessian (H = J^T*J) and the independent part (v = -J^T*f). Any positive symmetric definite matrix whose eigenvalues are in (0,1] can be approximated by a series of the form inv(H) = a0*I+a1*H+a2*H^2+a3*H^3+... where a0, a1, a2, a3 ... are real coefficients and are determined by the size of the series that we use for the approximation. Therefore, the solution of the system H*x = v, which is x = inv(H)*v can be approximated by (a0*I+a1*H+a2*H^2+a3*H^3+...)*v = a0*v+a1*H*v+a2*H^2*v+a3*H^3*v+... which requires only matrix-vector operations, and none matrix-matrix operation.

I understand that It is a competing method for CGNR. The point is for performing that I need the Hessian matrix H to make its eigenvalues be in (0,1] (that is why I need the preconditioning I mentioned in the last messages). I want to see how it performs for 3D reconstruction problems through the application to BA.

Best,

D. 

[Sameer Agarwal]

so are you implementing a new solver, or a new preconditioner?

if it is just a new solver, then consider just modifying the cgnr solver in ceres.

https://github.com/ceres-solver/ceres-solver/blob/master/internal/ceres/cgnr_solver.cc

Sameer

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/6277f6ec-3adb-400a-8d87-e4cd02af40a6%40googlegroups.com.

[Diego Coelho]

Hi Sameer,

It is kind of a new solver, because it is a new way of solving the normal equations. And it also requires a precondition matrix (could be Jacobi) to reduce the eigenvalue spread of Hessian matrix.

[Sameer Agarwal]

so right now the CGNR solver is configured to work  is to use the compressed row block sparse matrices.

their structure is laid out in block_structure.cc/h and then in block_sparse_matrix.h.

if your preconditioner construction can work on block sparse matrices, then I recommend implementing a new preconditioner type, or just landing your code inside the block_jacobi_preconditioner.cc 

Sameer

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/9ea0b561-50a7-4012-a46e-c2f6fbf861b6%40googlegroups.com.