/usr/include/ColPack/HessianRecovery.h is in libcolpack-dev 1.0.10-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 | /************************************************************************************
Copyright (C) 2005-2008 Assefaw H. Gebremedhin, Arijit Tarafdar, Duc Nguyen,
Alex Pothen
This file is part of ColPack.
ColPack is free software: you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published
by the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
ColPack is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public License
along with ColPack. If not, see <http://www.gnu.org/licenses/>.
************************************************************************************/
#ifndef HESSIANRECOVERY_H
#define HESSIANRECOVERY_H
using namespace std;
namespace ColPack
{
/** @ingroup group5
* @brief class HessianRecovery in @link group5@endlink.
*/
class HessianRecovery : public RecoveryCore
{
public: //DOCUMENTED
/// A routine for recovering a Hessian from a star-coloring based compressed representation.
/**
Parameter:
- Input:
- *g: GraphColoringInterface object, providing the coloring information
- dp2_CompressedMatrix: The compressed matrix that contains all computed values
- uip2_HessianSparsityPattern.
- Output:
- dp3_HessianValue
Precondition:
- Star coloring routine has been called.
- uip2_HessianSparsityPattern: The Hessian matrix must be stored in compressed sparse rows format
- dp3_HessianValue is just a pointer pointing to a 2D matrix (no memory allocated yet). This matrix will be created (memory will be allocated) by this routine and the pointer will be assigned to dp3_HessianValue
Postcondition:
- dp3_HessianValue points to a 2d matrix contains the numerical values of the Hessian. Row Compressed Format is used
The memory allocated for this output vector is managed by ColPack. The memory will be deallocated when this function is called again or when the Recovery ojbect is deallocated.
Return value: size of (*dp3_HessianValue) array
About input parameters:
- This routine doesn't need to take (star) coloring result m_vi_VertexColors of the Hessian as another paramenter because that information is known already (because of the 1st precondition). The cologin result can be retrieved from the first parameter "GraphColoringInterface* g"
Row Compressed Format for dp3_HessianValue:
- This is a 2D matrix of doubles.
- The first element of each row will specify the number of non-zeros in the Hessian => Value of the first element + 1 will be the length of that row.
- The value of each element after the 1st element is the value of the non-zero in the Hessian. The value of dp3_HessianValue[col][row] is the value of element [col][uip2_HessianSparsityPattern[col][row]] in the real (uncompressed) Hessian
- An example of compressed sparse rows format:
- Uncompressed matrix: <br>
1 .5 0 <br>
.5 2 3 <br>
0 3 -.5 <br>
- Corresponding uip2_HessianSparsityPattern: <br>
2 0 1 <br>
3 0 1 2 <br>
2 1 2 <br>
- Corresponding dp3_HessianValue: <br>
2 1 .5 <br>
3 .5 2 3 <br>
2 3 -.5 <br>
Algorithm: optimized version of the algorithm in Figure 2, pg 8, "Efficient Computation of Sparse Hessians using Coloring and Automatic Differentiation" paper.
The complexity of this routine is O(|E|) versus O(|E|*average distance-1 neighbour) for DirectRecover1
- Do (column-)color statistic for each row, i.e., see how many elements in that row has color 0, color 1 ...
Results are stored in map<int,int>* colorStatistic. colorStatistic[0] is (column-)color statistic for row 0
If row 0 has 5 columns with color 3 => colorStatistic[0][3] = 5;
- Allocate memory for *dp3_HessianValue
- (Main part) Recover the values of non-zero entries in the Hessian:
For each row, for each entry, see how many entries in that row have the same color by checking colorStatistic[row][column-color of the entry].
If colorStatistic[#][#] == 1 => This entry has unique color (in this row). H[j,i] = B[j,color[hi]]
else H[j,i] = B[i,color[hj]]
Each non-zero value of the Hessian will be recovered from left to right, top to bottom
Note: column-color of entry [row 5][column 3] is m_vi_VertexColors[column 3]
*/
int DirectRecover_RowCompressedFormat(GraphColoringInterface* g, double** dp2_CompressedMatrix, unsigned int ** uip2_HessianSparsityPattern, double*** dp3_HessianValue);
/// Same as DirectRecover_RowCompressedFormat(), except that the output is NOT managed by ColPack
/** Notes:
- The output is NOT managed by ColPack. Therefore, the user should free the output manually using free() (NOT delete) function when it is no longer needed.
*/
int DirectRecover_RowCompressedFormat_unmanaged(GraphColoringInterface* g, double** dp2_CompressedMatrix, unsigned int ** uip2_HessianSparsityPattern, double*** dp3_HessianValue);
/// Same as DirectRecover_RowCompressedFormat_unmanaged(), except that memory allocation for output vector(s) is done by user.
/** Notes:
- This function will assume the user has properly allocate memory output vector(s).
No checking will be done so if you got a SEGMENTATION FAULT in this function, you should check and see if you have allocated memory properly for the output vector(s).
(*dp3_HessianValue) should have the same structure as uip2_HessianSparsityPattern
*/
int DirectRecover_RowCompressedFormat_usermem(GraphColoringInterface* g, double** dp2_CompressedMatrix, unsigned int ** uip2_HessianSparsityPattern, double*** dp3_HessianValue);
/// A routine for recovering a Hessian from a star-coloring based compressed representation.
/**
Precondition:
- (*uip2_RowIndex), (*uip2_ColumnIndex), and (*dp2_JacobianValue) are equal to NULL, i.e. no memory has been allocated for these 3 vectors yet
Return value: size of (*uip2_RowIndex) array
Return by recovery routine: three vectors in "Coordinate Format" (zero-based indexing)
http://www.intel.com/software/products/mkl/docs/webhelp/appendices/mkl_appA_SMSF.html#mkl_appA_SMSF_5
- unsigned int** uip2_RowIndex
- unsigned int** uip2_ColumnIndex
- double** dp2_JacobianValue // corresponding non-zero values
NOTE: Since we are returning a symmetric matrix, only the upper triangle are stored.
The memory allocated for these 3 output vectors are managed by ColPack. The memory will be deallocated when this function is called again or when the Recovery ojbect is deallocated.
//*/
int DirectRecover_CoordinateFormat(GraphColoringInterface* g, double** dp2_CompressedMatrix, unsigned int ** uip2_HessianSparsityPattern, unsigned int** uip2_RowIndex, unsigned int** uip2_ColumnIndex, double** dp2_HessianValue);
// int DirectRecover_CoordinateFormat_OMP(GraphColoringInterface* g, double** dp2_CompressedMatrix, unsigned int ** uip2_HessianSparsityPattern, unsigned int** uip2_RowIndex, unsigned int** uip2_ColumnIndex, double** dp2_HessianValue);
/// Same as DirectRecover_CoordinateFormat(), except that the output is NOT managed by ColPack
/** Notes:
- The output is NOT managed by ColPack. Therefore, the user should free the output manually using free() (NOT delete) function when it is no longer needed.
*/
int DirectRecover_CoordinateFormat_unmanaged(GraphColoringInterface* g, double** dp2_CompressedMatrix, unsigned int ** uip2_HessianSparsityPattern, unsigned int** uip2_RowIndex, unsigned int** uip2_ColumnIndex, double** dp2_HessianValue);
// int DirectRecover_CoordinateFormat_unmanaged_OMP(GraphColoringInterface* g, double** dp2_CompressedMatrix, unsigned int ** uip2_HessianSparsityPattern, unsigned int** uip2_RowIndex, unsigned int** uip2_ColumnIndex, double** dp2_HessianValue);
/// Same as DirectRecover_CoordinateFormat_unmanaged(), except that memory allocation for output vector(s) is done by user. (OpenMP enabled)
/** Notes:
- This function will assume the user has properly allocate memory output vector(s).
No checking will be done so if you got a SEGMENTATION FAULT in this function, you should check and see if you have allocated memory properly for the output vector(s).
*/
// int DirectRecover_CoordinateFormat_usermem_serial(GraphColoringInterface* g, double** dp2_CompressedMatrix, unsigned int ** uip2_HessianSparsityPattern, unsigned int** uip2_RowIndex, unsigned int** uip2_ColumnIndex, double** dp2_HessianValue);
int DirectRecover_CoordinateFormat_usermem(GraphColoringInterface* g, double** dp2_CompressedMatrix, unsigned int ** uip2_HessianSparsityPattern, unsigned int** uip2_RowIndex, unsigned int** uip2_ColumnIndex, double** dp2_HessianValue);
//int DirectRecover_CoordinateFormat_usermem_OMP(GraphColoringInterface* g, double** dp2_CompressedMatrix, unsigned int ** uip2_HessianSparsityPattern, unsigned int** uip2_RowIndex, unsigned int** uip2_ColumnIndex, double** dp2_HessianValue);
/// A routine for recovering a Hessian from a star-coloring based compressed representation.
/**
Precondition:
- (*uip2_RowIndex), (*uip2_ColumnIndex), and (*dp2_JacobianValue) are equal to NULL, i.e. no memory has been allocated for these 3 vectors yet
Return value: size of (*uip2_RowIndex) array
Return by recovery routine: three vectors in "Storage Formats for the Direct Sparse Solvers" (zero-based indexing)
http://software.intel.com/sites/products/documentation/hpc/mkl/webhelp/appendices/mkl_appA_SMSF.html#mkl_appA_SMSF_1
- unsigned int** uip2_RowIndex
- unsigned int** uip2_ColumnIndex
- double** dp2_JacobianValue // corresponding non-zero values
NOTE: Since we are returning a symmetric matrix, according to format, only the upper triangle are stored.
The memory allocated for these 3 output vectors are managed by ColPack. The memory will be deallocated when this function is called again or when the Recovery ojbect is deallocated.
*/
int DirectRecover_SparseSolversFormat(GraphColoringInterface* g, double** dp2_CompressedMatrix, unsigned int ** uip2_HessianSparsityPattern, unsigned int** uip2_RowIndex, unsigned int** uip2_ColumnIndex, double** dp2_HessianValue);
/// Same as DirectRecover_SparseSolversFormat(), except that the output is NOT managed by ColPack
/**
About input parameters:
- numOfNonZerosInHessianValue: the size of (*uip2_ColumnIndex) and (*dp2_HessianValue) arrays.
The value of numOfNonZerosInHessianValue will be calculated if not provided (i.e. <1).
Notes:
- The output is NOT managed by ColPack. Therefore, the user should free the output manually using free() (NOT delete) function when it is no longer needed.
*/
int DirectRecover_SparseSolversFormat_unmanaged(GraphColoringInterface* g, double** dp2_CompressedMatrix, unsigned int ** uip2_HessianSparsityPattern, unsigned int** uip2_RowIndex, unsigned int** uip2_ColumnIndex, double** dp2_HessianValue, unsigned int numOfNonZerosInHessianValue = 0);
/// Same as DirectRecover_SparseSolversFormat_unmanaged(), except that memory allocation for output vector(s) is done by user.
/**
About input parameters:
- numOfNonZerosInHessianValue: the size of (*uip2_ColumnIndex) and (*dp2_HessianValue) arrays.
Notes:
- This function will assume the user has properly allocate memory output vector(s).
No checking will be done so if you got a SEGMENTATION FAULT in this function, you should check and see if you have allocated memory properly for the output vector(s).
*/
int DirectRecover_SparseSolversFormat_usermem(GraphColoringInterface* g, double** dp2_CompressedMatrix, unsigned int ** uip2_HessianSparsityPattern, unsigned int** uip2_RowIndex, unsigned int** uip2_ColumnIndex, double** dp2_HessianValue, unsigned int numOfNonZerosInHessianValue);
/// A routine for recovering a Hessian from a acyclic-coloring based compressed representation.
/**
Parameter:
- Input:
- *g: GraphColoringInterface object, providing the coloring information
- dp2_CompressedMatrix: The compressed matrix that contains all computed values
- uip2_HessianSparsityPattern.
- Output:
- dp3_HessianValue
Precondition:
- Acyclic coloring routine has been called.
- uip2_HessianSparsityPattern: The Hessian matrix must be stored in compressed sparse rows format
- dp3_HessianValue is just a pointer pointing to a 2D matrix (no memory allocated yet). This matrix will be created (memory will be allocated) by IndirectRecover2() and the pointer will be assigned to dp3_HessianValue
Postcondition:
- dp3_HessianValue points to a 2d matrix contains the numerical values of the Hessian. Row Compressed Format is used
The memory allocated for this output vector is managed by ColPack. The memory will be deallocated when this function is called again or when the Recovery ojbect is deallocated.
Return value: size of (*dp3_HessianValue) array
About input parameters:
- This routine doesn't need to take (acyclic) coloring result m_vi_VertexColors of the Hessian as another paramenter because that information is known already (because of the 1st precondition).
Row Compressed Format for dp3_HessianValue: see DirectRecover2()
Algorithm: created by Assefaw, 1st implemented by Arijit Tarafdar. This function is just a modification of Arijit's implementation
*/
int IndirectRecover_RowCompressedFormat(GraphColoringInterface* g, double** dp2_CompressedMatrix, unsigned int ** uip2_HessianSparsityPattern, double*** dp3_HessianValue);
/// Same as IndirectRecover_RowCompressedFormat(), except that the output is NOT managed by ColPack
/** Notes:
- The output is NOT managed by ColPack. Therefore, the user should free the output manually using free() (NOT delete) function when it is no longer needed.
*/
int IndirectRecover_RowCompressedFormat_unmanaged(GraphColoringInterface* g, double** dp2_CompressedMatrix, unsigned int ** uip2_HessianSparsityPattern, double*** dp3_HessianValue);
/// Same as IndirectRecover_RowCompressedFormat_unmanaged(), except that memory allocation for output vector(s) is done by user.
/** Notes:
- This function will assume the user has properly allocate memory output vector(s).
No checking will be done so if you got a SEGMENTATION FAULT in this function, you should check and see if you have allocated memory properly for the output vector(s).
*/
int IndirectRecover_RowCompressedFormat_usermem(GraphColoringInterface* g, double** dp2_CompressedMatrix, unsigned int ** uip2_HessianSparsityPattern, double*** dp3_HessianValue);
/// A routine for recovering a Hessian from a acyclic-coloring based compressed representation.
/**
Precondition:
- (*uip2_RowIndex), (*uip2_ColumnIndex), and (*dp2_JacobianValue) are equal to NULL, i.e. no memory has been allocated for these 3 vectors yet
Return value: size of (*uip2_RowIndex) array
Return by recovery routine: three vectors in "Coordinate Format" (zero-based indexing)
http://www.intel.com/software/products/mkl/docs/webhelp/appendices/mkl_appA_SMSF.html#mkl_appA_SMSF_5
- unsigned int** uip2_RowIndex
- unsigned int** uip2_ColumnIndex
- double** dp2_JacobianValue // corresponding non-zero values
NOTE: Since we are returning a symmetric matrix, only the upper triangle are stored.
The memory allocated for these 3 output vectors are managed by ColPack. The memory will be deallocated when this function is called again or when the Recovery ojbect is deallocated.
//*/
int IndirectRecover_CoordinateFormat(GraphColoringInterface* g, double** dp2_CompressedMatrix, unsigned int ** uip2_HessianSparsityPattern, unsigned int** uip2_RowIndex, unsigned int** uip2_ColumnIndex, double** dp2_HessianValue);
/// Same as IndirectRecover_CoordinateFormat(), except that the output is NOT managed by ColPack
/** Notes:
- The output is NOT managed by ColPack. Therefore, the user should free the output manually using free() (NOT delete) function when it is no longer needed.
*/
int IndirectRecover_CoordinateFormat_unmanaged(GraphColoringInterface* g, double** dp2_CompressedMatrix, unsigned int ** uip2_HessianSparsityPattern, unsigned int** uip2_RowIndex, unsigned int** uip2_ColumnIndex, double** dp2_HessianValue);
/// Same as IndirectRecover_CoordinateFormat_unmanaged(), except that memory allocation for output vector(s) is done by user.
/** Notes:
- This function will assume the user has properly allocate memory output vector(s).
No checking will be done so if you got a SEGMENTATION FAULT in this function, you should check and see if you have allocated memory properly for the output vector(s).
*/
int IndirectRecover_CoordinateFormat_usermem(GraphColoringInterface* g, double** dp2_CompressedMatrix, unsigned int ** uip2_HessianSparsityPattern, unsigned int** uip2_RowIndex, unsigned int** uip2_ColumnIndex, double** dp2_HessianValue);
/// A routine for recovering a Hessian from a acyclic-coloring based compressed representation.
/**
Precondition:
- (*uip2_RowIndex), (*uip2_ColumnIndex), and (*dp2_JacobianValue) are equal to NULL, i.e. no memory has been allocated for these 3 vectors yet
Return value: size of (*uip2_RowIndex) array
Return by recovery routine: three vectors in "Storage Formats for the Direct Sparse Solvers" (zero-based indexing)
http://software.intel.com/sites/products/documentation/hpc/mkl/webhelp/appendices/mkl_appA_SMSF.html#mkl_appA_SMSF_1
- unsigned int** uip2_RowIndex
- unsigned int** uip2_ColumnIndex
- double** dp2_JacobianValue // corresponding non-zero values
NOTE: Since we are returning a symmetric matrix, according to format, only the upper triangle are stored.
The memory allocated for these 3 output vectors are managed by ColPack. The memory will be deallocated when this function is called again or when the Recovery ojbect is deallocated.
*/
int IndirectRecover_SparseSolversFormat(GraphColoringInterface* g, double** dp2_CompressedMatrix, unsigned int ** uip2_HessianSparsityPattern, unsigned int** uip2_RowIndex, unsigned int** uip2_ColumnIndex, double** dp2_HessianValue);
/// Same as IndirectRecover_SparseSolversFormat(), except that the output is NOT managed by ColPack
/**
About input parameters:
- numOfNonZerosInHessianValue: the size of (*uip2_ColumnIndex) and (*dp2_HessianValue) arrays.
The value of numOfNonZerosInHessianValue will be calculated if not provided (i.e. <1).
Notes:
- The output is NOT managed by ColPack. Therefore, the user should free the output manually using free() (NOT delete) function when it is no longer needed.
*/
int IndirectRecover_SparseSolversFormat_unmanaged(GraphColoringInterface* g, double** dp2_CompressedMatrix, unsigned int ** uip2_HessianSparsityPattern, unsigned int** uip2_RowIndex, unsigned int** uip2_ColumnIndex, double** dp2_HessianValue, unsigned int numOfNonZerosInHessianValue = 0);
/// Same as IndirectRecover_SparseSolversFormat_unmanaged(), except that memory allocation for output vector(s) is done by user.
/**
About input parameters:
- numOfNonZerosInHessianValue: the size of (*uip2_ColumnIndex) and (*dp2_HessianValue) arrays.
Notes:
- This function will assume the user has properly allocate memory output vector(s).
No checking will be done so if you got a SEGMENTATION FAULT in this function, you should check and see if you have allocated memory properly for the output vector(s).
*/
int IndirectRecover_SparseSolversFormat_usermem(GraphColoringInterface* g, double** dp2_CompressedMatrix, unsigned int ** uip2_HessianSparsityPattern, unsigned int** uip2_RowIndex, unsigned int** uip2_ColumnIndex, double** dp2_HessianValue, unsigned int numOfNonZerosInHessianValue);
private:
int DirectRecover_CoordinateFormat_vectors(GraphColoringInterface* g, double** dp2_CompressedMatrix, unsigned int ** uip2_HessianSparsityPattern, vector<unsigned int> &RowIndex, vector<unsigned int> &ColumnIndex, vector<double> &HessianValue);
// int DirectRecover_CoordinateFormat_vectors_OMP(GraphColoringInterface* g, double** dp2_CompressedMatrix, unsigned int ** uip2_HessianSparsityPattern, vector<unsigned int> &RowIndex, vector<unsigned int> &ColumnIndex, vector<double> &HessianValue);
int IndirectRecover_CoordinateFormat_vectors(GraphColoringInterface* g, double** dp2_CompressedMatrix, unsigned int ** uip2_HessianSparsityPattern, vector<unsigned int> &RowIndex, vector<unsigned int> &ColumnIndex, vector<double> &HessianValue);
};
}
#endif
|