PrecomputedMatrix.h
Go to the documentation of this file.
1 //===========================================================================
2 /*!
3  *
4  *
5  * \brief Precomputed version of a matrix for quadratic programming
6  *
7  *
8  * \par
9  *
10  *
11  *
12  * \author T. Glasmachers
13  * \date 2007-2012
14  *
15  *
16  * \par Copyright 1995-2017 Shark Development Team
17  *
18  * <BR><HR>
19  * This file is part of Shark.
20  * <http://shark-ml.org/>
21  *
22  * Shark is free software: you can redistribute it and/or modify
23  * it under the terms of the GNU Lesser General Public License as published
24  * by the Free Software Foundation, either version 3 of the License, or
25  * (at your option) any later version.
26  *
27  * Shark is distributed in the hope that it will be useful,
28  * but WITHOUT ANY WARRANTY; without even the implied warranty of
29  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30  * GNU Lesser General Public License for more details.
31  *
32  * You should have received a copy of the GNU Lesser General Public License
33  * along with Shark. If not, see <http://www.gnu.org/licenses/>.
34  *
35  */
36 //===========================================================================
37 
38 
39 #ifndef SHARK_LINALG_PRECOMPUTEDMATRIX_H
40 #define SHARK_LINALG_PRECOMPUTEDMATRIX_H
41 
42 #include <shark/Data/Dataset.h>
43 #include <shark/LinAlg/Base.h>
44 
45 #include <vector>
46 #include <cmath>
47 
48 
49 namespace shark {
50 
51 ///
52 /// \brief Precomputed version of a matrix for quadratic programming
53 ///
54 /// \par
55 /// The PrecomputedMatrix class computes all pairs of kernel
56 /// evaluations in its constructor and stores them im memory.
57 /// This proceeding is only viable if the number of examples
58 /// does not exceed, say, about 10000. In this case the memory
59 /// demand is already \f$ 4 \cdot 10000^2 \approx 400\text{MB} \f$,
60 /// growing quadratically.
61 ///
62 /// \par
63 /// Use of this class may be beneficial for certain model
64 /// selection strategies, in particular if the kernel is
65 /// fixed and the regularization parameter is varied.
66 ///
67 /// \par
68 /// Use of this class may, in certain situations, even mean a
69 /// loss is speed, compared to CachedMatrix. This is the case
70 /// in particular if the solution of the quadratic program is
71 /// sparse, in which case most entries of the matrix do not
72 /// need to be computed at all, and the problem is "simple"
73 /// enough such that the solver's shrinking heuristic is not
74 /// mislead.
75 ///
76 template <class Matrix>
77 class PrecomputedMatrix
78 {
79 public:
80  typedef typename Matrix::QpFloatType QpFloatType;
81 
82  /// Constructor
83  /// \param base matrix to be precomputed
84  PrecomputedMatrix(Matrix* base)
85  : matrix(base->size(), base->size())
86  {
87  base->matrix(matrix);
88  }
89 
90  /// \brief Computes the i-th row of the kernel matrix.
91  ///
92  ///The entries start,...,end of the i-th row are computed and stored in storage.
93  ///There must be enough room for this operation preallocated.
94  void row(std::size_t k, std::size_t start,std::size_t end, QpFloatType* storage) const{
95  for(std::size_t j = start; j < end; j++){
96  storage[j-start] = matrix(k, j);
97  }
98  }
99 
100 
101  /// \brief Return a subset of a matrix row
102  ///
103  /// \par
104  /// This method returns an array with at least
105  /// the entries in the interval [begin, end[ filled in.
106  ///
107  /// \param k matrix row
108  /// \param begin first column to be filled in
109  /// \param end last column to be filled in +1
110  QpFloatType* row(std::size_t k, std::size_t begin, std::size_t end)
111  {
112  return &matrix(k, begin);
113  }
114 
115  /// return a single matrix entry
116  QpFloatType operator () (std::size_t i, std::size_t j) const
117  { return entry(i, j); }
118 
119  /// return a single matrix entry
120  QpFloatType entry(std::size_t i, std::size_t j) const
121  {
122  return matrix(i, j);
123  }
124 
125  /// swap two variables
126  void flipColumnsAndRows(std::size_t i, std::size_t j)
127  {
128  matrix.swap_rows(i, j);
129  matrix.swap_columns(i, j);
130  }
131 
132  /// return the size of the quadratic matrix
133  std::size_t size() const
134  { return matrix.size2(); }
135 
136  /// for compatibility with CachedMatrix
137  std::size_t getMaxCacheSize()
138  { return matrix.size1() * matrix.size2(); }
139 
140  /// for compatibility with CachedMatrix
141  std::size_t getCacheSize() const
142  { return getMaxCacheSize(); }
143 
144  /// for compatibility with CachedMatrix
145  std::size_t getCacheRowSize(std::size_t k) const
146  { return matrix.size2(); }
147 
148  /// for compatibility with CachedMatrix
149  bool isCached(std::size_t){
150  return true;
151  }
152  /// for compatibility with CachedMatrix
153  void setMaxCachedIndex(std::size_t n){}
154 
155  /// for compatibility with CachedMatrix
156  void clear()
157  { }
158 
159 protected:
160  /// container for precomputed values
161  blas::matrix<QpFloatType> matrix;
162 };
163 
164 }
165 #endif