10ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Ceres Solver - A fast non-linear least squares minimizer 20ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Copyright 2012 Google Inc. All rights reserved. 30ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// http://code.google.com/p/ceres-solver/ 40ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 50ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Redistribution and use in source and binary forms, with or without 60ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// modification, are permitted provided that the following conditions are met: 70ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 80ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// * Redistributions of source code must retain the above copyright notice, 90ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// this list of conditions and the following disclaimer. 100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// * Redistributions in binary form must reproduce the above copyright notice, 110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// this list of conditions and the following disclaimer in the documentation 120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// and/or other materials provided with the distribution. 130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// * Neither the name of Google Inc. nor the names of its contributors may be 140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// used to endorse or promote products derived from this software without 150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// specific prior written permission. 160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// POSSIBILITY OF SUCH DAMAGE. 280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Author: strandmark@google.com (Petter Strandmark) 300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#ifndef CERES_INTERNAL_CXSPARSE_H_ 320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#define CERES_INTERNAL_CXSPARSE_H_ 330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 3479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez// This include must come before any #ifndef check on Ceres compile options. 3579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez#include "ceres/internal/port.h" 3679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#ifndef CERES_NO_CXSPARSE 380ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 391d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling#include <vector> 400ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "cs.h" 410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 420ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongnamespace ceres { 430ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongnamespace internal { 440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongclass CompressedRowSparseMatrix; 460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongclass TripletSparseMatrix; 470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 480ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// This object provides access to solving linear systems using Cholesky 490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// factorization with a known symbolic factorization. This features does not 500ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// explicity exist in CXSparse. The methods in the class are nonstatic because 510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// the class manages internal scratch space. 520ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongclass CXSparse { 530ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong public: 540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong CXSparse(); 550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong ~CXSparse(); 560ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Solves a symmetric linear system A * x = b using Cholesky factorization. 580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // A - The system matrix. 590ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // symbolic_factorization - The symbolic factorization of A. This is obtained 600ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // from AnalyzeCholesky. 610ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // b - The right hand size of the linear equation. This 620ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // array will also recieve the solution. 630ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Returns false if Cholesky factorization of A fails. 640ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong bool SolveCholesky(cs_di* A, cs_dis* symbolic_factorization, double* b); 650ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 660ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Creates a sparse matrix from a compressed-column form. No memory is 670ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // allocated or copied; the structure A is filled out with info from the 680ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // argument. 690ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong cs_di CreateSparseMatrixTransposeView(CompressedRowSparseMatrix* A); 700ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 710ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Creates a new matrix from a triplet form. Deallocate the returned matrix 720ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // with Free. May return NULL if the compression or allocation fails. 730ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong cs_di* CreateSparseMatrix(TripletSparseMatrix* A); 740ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 751d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // B = A' 761d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 771d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // The returned matrix should be deallocated with Free when not used 781d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // anymore. 791d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling cs_di* TransposeMatrix(cs_di* A); 801d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 811d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // C = A * B 821d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 831d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // The returned matrix should be deallocated with Free when not used 841d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // anymore. 851d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling cs_di* MatrixMatrixMultiply(cs_di* A, cs_di* B); 861d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 870ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Computes a symbolic factorization of A that can be used in SolveCholesky. 881d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 890ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // The returned matrix should be deallocated with Free when not used anymore. 900ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong cs_dis* AnalyzeCholesky(cs_di* A); 910ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 921d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Computes a symbolic factorization of A that can be used in 931d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // SolveCholesky, but does not compute a fill-reducing ordering. 941d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 951d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // The returned matrix should be deallocated with Free when not used anymore. 961d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling cs_dis* AnalyzeCholeskyWithNaturalOrdering(cs_di* A); 971d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 981d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Computes a symbolic factorization of A that can be used in 991d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // SolveCholesky. The difference from AnalyzeCholesky is that this 1001d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // function first detects the block sparsity of the matrix using 1011d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // information about the row and column blocks and uses this block 1021d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // sparse matrix to find a fill-reducing ordering. This ordering is 1031d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // then used to find a symbolic factorization. This can result in a 1041d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // significant performance improvement AnalyzeCholesky on block 1051d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // sparse matrices. 1061d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // 1071d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // The returned matrix should be deallocated with Free when not used 1081d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // anymore. 1091d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling cs_dis* BlockAnalyzeCholesky(cs_di* A, 1101d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const vector<int>& row_blocks, 1111d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const vector<int>& col_blocks); 1121d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1131d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Compute an fill-reducing approximate minimum degree ordering of 1141d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // the matrix A. ordering should be non-NULL and should point to 1151d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // enough memory to hold the ordering for the rows of A. 1161d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling void ApproximateMinimumDegreeOrdering(cs_di* A, int* ordering); 1171d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 1181d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling void Free(cs_di* sparse_matrix); 1191d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling void Free(cs_dis* symbolic_factorization); 1200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong private: 1220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Cached scratch space 1230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong CS_ENTRY* scratch_; 1240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int scratch_size_; 1250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong}; 1260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} // namespace internal 1280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} // namespace ceres 1290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 130399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger#else // CERES_NO_CXSPARSE 131399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger 132399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettingertypedef void cs_dis; 133399f7d09e0c45af54b77b4ab9508d6f23759b927Scott Ettinger 13479397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandezclass CXSparse { 13579397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez public: 13679397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez void Free(void*) {}; 13779397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez 13879397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez}; 1390ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#endif // CERES_NO_CXSPARSE 1400ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#endif // CERES_INTERNAL_CXSPARSE_H_ 142