diff options
Diffstat (limited to 'extern/ceres/internal/ceres/inner_product_computer.h')
| -rw-r--r-- | extern/ceres/internal/ceres/inner_product_computer.h | 157 |
1 files changed, 157 insertions, 0 deletions
diff --git a/extern/ceres/internal/ceres/inner_product_computer.h b/extern/ceres/internal/ceres/inner_product_computer.h new file mode 100644 index 00000000000..73073f8ad06 --- /dev/null +++ b/extern/ceres/internal/ceres/inner_product_computer.h @@ -0,0 +1,157 @@ +// Ceres Solver - A fast non-linear least squares minimizer +// Copyright 2017 Google Inc. All rights reserved. +// http://ceres-solver.org/ +// +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are met: +// +// * Redistributions of source code must retain the above copyright notice, +// this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above copyright notice, +// this list of conditions and the following disclaimer in the documentation +// and/or other materials provided with the distribution. +// * Neither the name of Google Inc. nor the names of its contributors may be +// used to endorse or promote products derived from this software without +// specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +// POSSIBILITY OF SUCH DAMAGE. +// +// Author: sameeragarwal@google.com (Sameer Agarwal) + +#ifndef CERES_INTERNAL_INNER_PRODUCT_COMPUTER_H_ +#define CERES_INTERNAL_INNER_PRODUCT_COMPUTER_H_ + +#include <memory> +#include <vector> + +#include "ceres/block_sparse_matrix.h" +#include "ceres/compressed_row_sparse_matrix.h" + +namespace ceres { +namespace internal { + +// This class is used to repeatedly compute the inner product +// +// result = m' * m +// +// where the sparsity structure of m remains constant across calls. +// +// Upon creation, the class computes and caches information needed to +// compute v, and then uses it to efficiently compute the product +// every time InnerProductComputer::Compute is called. +// +// See sparse_normal_cholesky_solver.cc for example usage. +// +// Note that the result matrix is a block upper or lower-triangular +// matrix, i.e., it will contain entries in the upper or lower +// triangular part of the matrix corresponding to the block that occur +// along its diagonal. +// +// This is not a problem as sparse linear algebra libraries can ignore +// these entries with ease and the space used is minimal/linear in the +// size of the matrices. +class InnerProductComputer { + public: + // Factory + // + // m is the input matrix + // + // Since m' * m is a symmetric matrix, we only compute half of the + // matrix and the value of storage_type which must be + // UPPER_TRIANGULAR or LOWER_TRIANGULAR determines which half is + // computed. + // + // The user must ensure that the matrix m is valid for the life time + // of this object. + static InnerProductComputer* Create( + const BlockSparseMatrix& m, + CompressedRowSparseMatrix::StorageType storage_type); + + // This factory method allows the user control over range of row + // blocks of m that should be used to compute the inner product. + // + // a = m(start_row_block : end_row_block, :); + // result = a' * a; + static InnerProductComputer* Create( + const BlockSparseMatrix& m, + int start_row_block, + int end_row_block, + CompressedRowSparseMatrix::StorageType storage_type); + + // Update result_ to be numerically equal to m' * m. + void Compute(); + + // Accessors for the result containing the inner product. + // + // Compute must be called before accessing this result for + // the first time. + const CompressedRowSparseMatrix& result() const { return *result_; } + CompressedRowSparseMatrix* mutable_result() const { return result_.get(); } + + private: + // A ProductTerm is a term in the block inner product of a matrix + // with itself. + struct ProductTerm { + ProductTerm(const int row, const int col, const int index) + : row(row), col(col), index(index) {} + + bool operator<(const ProductTerm& right) const { + if (row == right.row) { + if (col == right.col) { + return index < right.index; + } + return col < right.col; + } + return row < right.row; + } + + int row; + int col; + int index; + }; + + InnerProductComputer(const BlockSparseMatrix& m, + int start_row_block, + int end_row_block); + + void Init(CompressedRowSparseMatrix::StorageType storage_type); + + CompressedRowSparseMatrix* CreateResultMatrix( + const CompressedRowSparseMatrix::StorageType storage_type, + int num_nonzeros); + + int ComputeNonzeros(const std::vector<ProductTerm>& product_terms, + std::vector<int>* row_block_nnz); + + void ComputeOffsetsAndCreateResultMatrix( + const CompressedRowSparseMatrix::StorageType storage_type, + const std::vector<ProductTerm>& product_terms); + + const BlockSparseMatrix& m_; + const int start_row_block_; + const int end_row_block_; + std::unique_ptr<CompressedRowSparseMatrix> result_; + + // For each term in the inner product, result_offsets_ contains the + // location in the values array of the result_ matrix where it + // should be stored. + // + // This is the principal look up table that allows this class to + // compute the inner product fast. + std::vector<int> result_offsets_; +}; + +} // namespace internal +} // namespace ceres + +#endif // CERES_INTERNAL_INNER_PRODUCT_COMPUTER_H_ |