1 // Ceres Solver - A fast non-linear least squares minimizer
2 // Copyright 2015 Google Inc. All rights reserved.
3 // http://ceres-solver.org/
4 //
5 // Redistribution and use in source and binary forms, with or without
6 // modification, are permitted provided that the following conditions are met:
7 //
8 // * Redistributions of source code must retain the above copyright notice,
9 //   this list of conditions and the following disclaimer.
10 // * Redistributions in binary form must reproduce the above copyright notice,
11 //   this list of conditions and the following disclaimer in the documentation
12 //   and/or other materials provided with the distribution.
13 // * Neither the name of Google Inc. nor the names of its contributors may be
14 //   used to endorse or promote products derived from this software without
15 //   specific prior written permission.
16 //
17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
21 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27 // POSSIBILITY OF SUCH DAMAGE.
28 //
29 // Author: strandmark@google.com (Petter Strandmark)
30 
31 #ifndef CERES_INTERNAL_CXSPARSE_H_
32 #define CERES_INTERNAL_CXSPARSE_H_
33 
34 // This include must come before any #ifndef check on Ceres compile options.
35 #include "ceres/internal/port.h"
36 
37 #ifndef CERES_NO_CXSPARSE
38 
39 #include <memory>
40 #include <string>
41 #include <vector>
42 
43 #include "ceres/linear_solver.h"
44 #include "ceres/sparse_cholesky.h"
45 #include "cs.h"
46 
47 namespace ceres {
48 namespace internal {
49 
50 class CompressedRowSparseMatrix;
51 class TripletSparseMatrix;
52 
53 // This object provides access to solving linear systems using Cholesky
54 // factorization with a known symbolic factorization. This features does not
55 // explicitly exist in CXSparse. The methods in the class are nonstatic because
56 // the class manages internal scratch space.
57 class CXSparse {
58  public:
59   CXSparse();
60   ~CXSparse();
61 
62   // Solve the system lhs * solution = rhs in place by using an
63   // approximate minimum degree fill reducing ordering.
64   bool SolveCholesky(cs_di* lhs, double* rhs_and_solution);
65 
66   // Solves a linear system given its symbolic and numeric factorization.
67   void Solve(cs_dis* symbolic_factor,
68              csn* numeric_factor,
69              double* rhs_and_solution);
70 
71   // Compute the numeric Cholesky factorization of A, given its
72   // symbolic factorization.
73   //
74   // Caller owns the result.
75   csn* Cholesky(cs_di* A, cs_dis* symbolic_factor);
76 
77   // Creates a sparse matrix from a compressed-column form. No memory is
78   // allocated or copied; the structure A is filled out with info from the
79   // argument.
80   cs_di CreateSparseMatrixTransposeView(CompressedRowSparseMatrix* A);
81 
82   // Creates a new matrix from a triplet form. Deallocate the returned matrix
83   // with Free. May return NULL if the compression or allocation fails.
84   cs_di* CreateSparseMatrix(TripletSparseMatrix* A);
85 
86   // B = A'
87   //
88   // The returned matrix should be deallocated with Free when not used
89   // anymore.
90   cs_di* TransposeMatrix(cs_di* A);
91 
92   // C = A * B
93   //
94   // The returned matrix should be deallocated with Free when not used
95   // anymore.
96   cs_di* MatrixMatrixMultiply(cs_di* A, cs_di* B);
97 
98   // Computes a symbolic factorization of A that can be used in SolveCholesky.
99   //
100   // The returned matrix should be deallocated with Free when not used anymore.
101   cs_dis* AnalyzeCholesky(cs_di* A);
102 
103   // Computes a symbolic factorization of A that can be used in
104   // SolveCholesky, but does not compute a fill-reducing ordering.
105   //
106   // The returned matrix should be deallocated with Free when not used anymore.
107   cs_dis* AnalyzeCholeskyWithNaturalOrdering(cs_di* A);
108 
109   // Computes a symbolic factorization of A that can be used in
110   // SolveCholesky. The difference from AnalyzeCholesky is that this
111   // function first detects the block sparsity of the matrix using
112   // information about the row and column blocks and uses this block
113   // sparse matrix to find a fill-reducing ordering. This ordering is
114   // then used to find a symbolic factorization. This can result in a
115   // significant performance improvement AnalyzeCholesky on block
116   // sparse matrices.
117   //
118   // The returned matrix should be deallocated with Free when not used
119   // anymore.
120   cs_dis* BlockAnalyzeCholesky(cs_di* A,
121                                const std::vector<int>& row_blocks,
122                                const std::vector<int>& col_blocks);
123 
124   // Compute an fill-reducing approximate minimum degree ordering of
125   // the matrix A. ordering should be non-NULL and should point to
126   // enough memory to hold the ordering for the rows of A.
127   void ApproximateMinimumDegreeOrdering(cs_di* A, int* ordering);
128 
129   void Free(cs_di* sparse_matrix);
130   void Free(cs_dis* symbolic_factorization);
131   void Free(csn* numeric_factorization);
132 
133  private:
134   // Cached scratch space
135   CS_ENTRY* scratch_;
136   int scratch_size_;
137 };
138 
139 // An implementation of SparseCholesky interface using the CXSparse
140 // library.
141 class CXSparseCholesky : public SparseCholesky {
142  public:
143   // Factory
144   static std::unique_ptr<SparseCholesky> Create(OrderingType ordering_type);
145 
146   // SparseCholesky interface.
147   virtual ~CXSparseCholesky();
148   CompressedRowSparseMatrix::StorageType StorageType() const final;
149   LinearSolverTerminationType Factorize(CompressedRowSparseMatrix* lhs,
150                                         std::string* message) final;
151   LinearSolverTerminationType Solve(const double* rhs,
152                                     double* solution,
153                                     std::string* message) final;
154 
155  private:
156   CXSparseCholesky(const OrderingType ordering_type);
157   void FreeSymbolicFactorization();
158   void FreeNumericFactorization();
159 
160   const OrderingType ordering_type_;
161   CXSparse cs_;
162   cs_dis* symbolic_factor_;
163   csn* numeric_factor_;
164 };
165 
166 }  // namespace internal
167 }  // namespace ceres
168 
169 #else
170 
171 typedef void cs_dis;
172 
173 class CXSparse {
174  public:
Free(void * arg)175   void Free(void* arg) {}
176 };
177 #endif  // CERES_NO_CXSPARSE
178 
179 #endif  // CERES_INTERNAL_CXSPARSE_H_
180