HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_SparseMatrix.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: Sparse Matrix Class (C++)
7  *
8  * COMMENTS:
9  *
10  * Storage format: Co-ordinate (COO). See
11  * Y. Saad. SPARSKIT: A basic toolkit for sparse matrix computations.
12  * Research Institute for Advanced Computer Science, RIACS-90-20,
13  * 1990.
14  * for details.
15  */
16 
17 #ifndef __UT_SparseMatrix_H__
18 #define __UT_SparseMatrix_H__
19 
20 #include "UT_API.h"
21 #include "UT_IntArray.h"
22 #include "UT_Interrupt.h"
23 #include "UT_NonCopyable.h"
24 #include "UT_ParallelUtil.h"
25 #include "UT_ThreadedAlgorithm.h"
26 #include "UT_Vector.h"
27 #include "UT_VectorTypes.h"
28 
29 #include <iterator>
30 #include <type_traits>
31 
32 class UT_IStream;
33 class UT_BitArray;
34 
35 template <typename T> class UT_API UT_SparseMatrixRowT;
36 
37 template <typename T, bool IsPaged>
39 {
40  class ut_MatrixCell
41  {
42  public:
43  int myRow;
44  int myCol;
45  T myValue;
46 
47  inline bool operator<(const ut_MatrixCell &o) const
48  {
49  if (myRow < o.myRow)
50  return true;
51  if (myRow == o.myRow && myCol < o.myCol)
52  return true;
53  return false;
54  }
55  };
56 
57  // For paged matrices, store the size of each page
58  // We always allocate full pages.
59  static const int CELL_PAGESIZE = 1024;
60  static const int CELL_PAGEMASK = 1023;
61  static const int CELL_PAGEBITS = 10;
62 
63  class ut_CellIterator
64  {
65  public:
66  using iterator_category = std::random_access_iterator_tag;
67  using value_type = ut_MatrixCell;
68  using difference_type = std::ptrdiff_t;
69  using pointer = value_type*;
70  using reference = value_type&;
71 
72  ut_CellIterator(const UT_SparseMatrixT<T, IsPaged> *matrix, int idx)
73  { myMatrix = matrix; myPos = idx; repage(); }
74 
75  ut_CellIterator operator+(ptrdiff_t n) const { return ut_CellIterator(myMatrix, myPos+n); }
76  ut_CellIterator operator-(ptrdiff_t n) const { return ut_CellIterator(myMatrix, myPos-n); }
77  ut_CellIterator &operator+=(ptrdiff_t n) { myPos += n; repage(); return *this; }
78  ut_CellIterator &operator-=(ptrdiff_t n) { myPos -= n; repage(); return *this; }
79  ut_CellIterator &operator++() { myPos++; myOffset++; myData++; if (myOffset >= CELL_PAGESIZE) repage(); return *this; }
80  ut_CellIterator &operator--() { myPos--; myOffset--; myData--; if (myOffset < 0) repage(); return *this; }
81  ut_CellIterator operator++(int) { ut_CellIterator result = *this; myPos++; myOffset++; myData++; if (myOffset >= CELL_PAGESIZE) repage(); return result; }
82  ut_CellIterator operator--(int) { ut_CellIterator result = *this; myPos--; myOffset--; myData--; if (myOffset < 0) repage(); return result; }
83  int operator-(ut_CellIterator b) const { return myPos - b.myPos; }
84  ut_MatrixCell &operator[](ptrdiff_t idx) { return myMatrix->getCell(idx + myPos); }
85 
86  bool operator<(ut_CellIterator b) const { return myPos < b.myPos; }
87  bool operator>(ut_CellIterator b) const { return myPos > b.myPos; }
88  bool operator>=(ut_CellIterator b) const { return myPos >= b.myPos; }
89  bool operator==(ut_CellIterator b) const { return myPos == b.myPos; }
90  bool operator!=(ut_CellIterator b) const { return myPos != b.myPos; }
91 
92  ut_MatrixCell &operator*() const { return *myData; }
93  ut_MatrixCell *operator->() const { return myData; }
94 
95  protected:
96 
97  void repage()
98  { myPage = myPos >> CELL_PAGEBITS; myOffset = myPos & CELL_PAGEMASK;
99  myData = 0;
100  if (myPage < myMatrix->myCellPages.entries())
101  myData = &myMatrix->myCellPages(myPage)[myOffset];
102  }
103 
104  const UT_SparseMatrixT<T, IsPaged> *myMatrix;
105  ut_MatrixCell *myData;
106  ptrdiff_t myPos;
107  int myPage, myOffset;
108  };
109 
110  // For compact compiled matrix cells, specify the number of values to
111  // pack into a single cell.
112  static const int CELLBITS = 2;
113  static const int CELLSIZE = 1 << CELLBITS;
114  static const int CELLMASK = CELLSIZE-1;
115 
116  class SYS_ALIGN16 ut_4MatrixCell
117  {
118  public:
119  T myValue[CELLSIZE];
120  int myRow;
121  int myCol;
122  };
123 
124 public:
126 
127  // creates a valid 'rows' x 'cols' zero matrix
128  UT_SparseMatrixT(int rows, int cols);
130  ~UT_SparseMatrixT();
131 
132  int getNumRows() const { return myNumRows; }
133  int getNumCols() const { return myNumCols; }
134 
135  /// Return the amount of memory used by this array.
136  int64 getMemoryUsage() const;
137  int64 getIdealMemoryUsage() const;
138 
139  /// Ensures at least this number of cells are available, useful
140  /// if you can predict your size.
141  void reserve(int numcells);
142 
143  /// Shrinks the array to exactly fit the number of cells present
144  void shrinkToFit();
145 
146  // sets equal to a 'rows' x 'cols' zero matrix
147  void init(int rows, int cols);
148 
149  // Sets all entries of the matrix to zero.
150  void zero();
151 
152  // Determines if we are large enough to justify mulithreading.
153  // The 5000 was determined from experiments with UT_Vector.
154  bool shouldMultiThread() const
155  {
156  return getNumRows() > 5000;
157  }
158 
159  // does M(row,col) += value
160  bool addToElement(int row, int col, T value);
161 
162  // Returns the index of the cell for which cell->row >= row is true
163  // first. This could be myCount if row is too high.
164  // myCells[result].myRow may be strictly greater than row if it isn't
165  // present.
166  int findCellFromRow(int row) const;
167 
168  // computes M * v
169  inline void multVec(const UT_VectorT<T> &v, UT_VectorT<T> &result) const
170  {
171  compile();
172  multVecInternal(v, result);
173  }
174 
175  /// Do result = result - (M * v)
176  inline void subtractMultVec(const UT_VectorT<T> &v, UT_VectorT<T> &result) const
177  {
178  compile();
179  subtractMultVecInternal(v, result);
180  }
182  {
183  compile();
184  subtractMultVecInternalNoThread(v, result);
185  }
186 
187  // computes M^T * v
188  void transposeMultVec(const UT_VectorT<T> &v, UT_VectorT<T> &result) const;
189 
190  /// Square of L2-norm of all columns
191  /// Use to form the diagonal part of A^tA of an overdetermined system A.
192  /// Needed for both Jacobi and Gauss-Seidel iterations.
193  void allColNorm2(UT_VectorT<T> &result) const;
194 
195  /// Initializes out to a matrix where the (i,j) elements are
196  /// (rowstart+i, colstart+j) elements of this. The rowend and
197  /// colend represent the exclusive end - [rowstart,rowend) will
198  /// be extracted for numrows = rowend - rowstart
199  /// This function will compile *this, if it wasn't before the call.
200  /// The resulting matrix will be compiled (by construction).
201  void extractSubMatrix(UT_SparseMatrixT<T, IsPaged> &out,
202  int rowstart, int rowend,
203  int colstart, int colend) const;
204  /// Extract submatrix without compiling *this.
205  /// The resulting submatrix won't be compiled either.
206  void extractSubMatrixUncompiled(UT_SparseMatrixT<T, IsPaged> &out,
207  int rowstart, int rowend,
208  int colstart, int colend) const;
209 
210  // Get fixed-size square submatrix
211  // This will trigger compilation
212  void getSmallSquareSubMatrix(T submatrix[],
213  const exint indices[], const int num_indices) const;
214 
215  // For each row, column, and value call visitor(row, column, value)
216  // visitor may be called with the same (row, column) pair multiple times
217  // the sum of all the associated values is the component in the matrix for (row, column)
218  template<typename Visitor>
219  void accept(Visitor& visitor) const
220  {
221  for(exint ci = 0; ci < myCount; ++ci)
222  {
223  ut_MatrixCell *cell = &getCell(ci);
224  visitor(cell->myRow, cell->myCol, cell->myValue);
225  }
226  }
227 
228  /// Clear the rows and columns specified by the given bit field to a row
229  /// from the identity matrix
230  void clearRowsAndColumns(const UT_BitArray &toclear);
231 
232  /// Extract the diagonal vector from a matrix. This does not
233  /// require the matrix to be compiled, nor does it try to compile it.
234  /// For entries (i, j), this method will extract the entries where
235  /// (i-j == idx).
236  void extractDiagonal(UT_VectorT<T> &out, int idx = 0) const;
237 
238  /// Extract everything but the diagonal:
239  /// out(i, j) = 0, if i == j,
240  // *this(i, j), otherwise
241  void extractNondiagonal(UT_SparseMatrixT<T, IsPaged> &out) const;
242 
243  /// Incomplete Cholesky Factorization.
244  /// Does a Cholesky Factorization but does not make any elements non-zero
245  /// The result of this operation is an UPPER triangular matrix G
246  /// such that A = Gt G.
247  /// The input must be a symmetric matrix.
248  /// Note that this factorization is not always stable.
249  /// Returns 0 on success, -1 if semi-definite (diagonal contained zeros
250  /// within the given tolerance) and -2 if not positive definite (diagonal
251  /// contained negative numbers)
252  int incompleteCholeskyFactorization(T tol=1e-5);
253 
254  /// Modified Incomplete Cholesky
255  /// Same as incomplte cholesky, except attempt to account for the
256  /// discarded entries by adjusting the diagonal.
257  /// tau is a tuning constant.
258  int modifiedIncompleteCholesky(T tau = 0.97,
259  T mindiagratio = 0.25,
260  T tol=1e-5);
261 
262  /// Assumes this is a lower triangular matrix. Solves the equation
263  /// A x = b
264  /// If the diagonal of A is zero within tolerance, the corresponding
265  /// x coordinate is zero.
266  /// Returned is the number of artifical zeros places into x. 0 means
267  /// the solution encountered no singularities, 10 would mean 10
268  /// singularities.
269  int solveLowerTriangular(UT_VectorT<T> &x, const UT_VectorT<T> &b,
270  T tol=1e-5) const;
271  int solveUpperTriangular(UT_VectorT<T> &x, const UT_VectorT<T> &b,
272  T tol=1e-5) const;
273  /// Given an upper triangular matrix, solves the lower triangular
274  /// transposed of it and negates the result.
275  int solveLowerTriangularTransposeNegate(UT_VectorT<T> &x,
276  const UT_VectorT<T> &b,
277  T tol=1e-5) const;
278 
279  // Use the conjugate gradient method to solve Ax=b.
280  // NB: 'x' should be initialized with the initial estimate
281  bool solveConjugateGradient(UT_VectorT<T> &x, const UT_VectorT<T> &b,
283  bool (*callback_func)(void *) = 0,
284  void *callback_data = 0, T tol2=1e-5,
285  int max_iters = -1) const;
286 
287  /// Transposes this matrix.
288  THREADED_METHOD(UT_SparseMatrixT, shouldMultiThread(), transpose)
289  void transposePartial(const UT_JobInfo &info);
290 
291  /// Makes this a transposed copy of source. By not working
292  /// in place we can avoid a sort if the source is compiled.
293  /// If source is not compiled, we compile it.
294  void transposeCompiled(const UT_SparseMatrixT<T, IsPaged> &src);
295 
296  /// *this = -*this.
297  THREADED_METHOD(UT_SparseMatrixT, shouldMultiThread(), negate)
298  void negatePartial(const UT_JobInfo &info);
299 
300  UT_SparseMatrixT<T, IsPaged> &operator=(const UT_SparseMatrixT<T, IsPaged> &m);
301  UT_SparseMatrixT<T, IsPaged> &operator*=(T scalar);
302  UT_SparseMatrixT<T, IsPaged> &operator+=(const UT_SparseMatrixT<T, IsPaged> &m);
303 
304  // Writes out the full matrix as an Row X Column array. Likely
305  // not too useful with big matrices...
306  void printFull(std::ostream &os) const;
307 
308  // Writes out all of the non-zero elements.
309  void printSparse(std::ostream &os) const;
310 
311  // Writes out all of the non-zero elements as a Matlab "sparse" expression.
312  void printSparseMatlab(std::ostream &os,
313  const UT_String &varname) const;
314 
315  // Binary save and load of a sparse matrix
316  void save(std::ostream &os) const;
317  void load(UT_IStream &is);
318 
319  /// Reorders the cell array to be sorted by row than column.
320  /// Consolidates any duplicate entries by adding them together.
321  /// Culls any zero entries.
322  /// compile will be a no-op if the matrix's structure has not changed
323  /// since the last invocation.
324  /// While compilation is expensive, it also performs the collapse/cull
325  /// operation, so you may want to invoke it explicitly if you are
326  /// repeatedly gathering similar matrices, say with +=.
327  void compile() const;
328  bool isCompiled() const { return myCompiledFlag; }
329  bool isStillSorted() const { return myStillSortedFlag; }
330 
331  bool hasNan() const;
332  void testForNan() const;
333 
334 private:
335  /// Always recompiles the matrix regardless of the compile flag setting.
336  void forceCompile() const;
337 
338  /// Extract a cell by its index.
339  inline ut_MatrixCell &getCell(int idx) const
340  {
341  if (IsPaged)
342  return myCellPages(idx >> CELL_PAGEBITS)[idx & CELL_PAGEMASK];
343  else
344  return myCells[idx];
345  }
346 
347  THREADED_METHOD2_CONST(UT_SparseMatrixT, shouldMultiThread(),
348  multVecInternal, const UT_VectorT<T> &, v,
350  void multVecInternalPartial(const UT_VectorT<T> &v, UT_VectorT<T> &result,
351  const UT_JobInfo &info) const;
352 
353  THREADED_METHOD2_CONST(UT_SparseMatrixT, shouldMultiThread(),
354  subtractMultVecInternal,
355  const UT_VectorT<T>&, v,
356  UT_VectorT<T>&, result)
357  void subtractMultVecInternalPartial(const UT_VectorT<T>& v, UT_VectorT<T>& result,
358  const UT_JobInfo& info) const;
359 
360  /// Compile into 4-value cell data structure
361  void compile4() const;
362 
363  int myNumRows;
364  int myNumCols;
365  mutable UT_ValArray<ut_MatrixCell *> myCellPages;
366  mutable ut_MatrixCell *myCells;
367  mutable int myCount;
368  mutable int *my4RowOffsets;
369  mutable ut_4MatrixCell *my4Cells;
370  mutable int my4Count;
371  int myMaxSize;
372  mutable bool myCompiledFlag;
373  mutable bool myStillSortedFlag;
374  mutable bool my4CompiledFlag;
375 
377 };
378 
379 typedef UT_SparseMatrixT<fpreal32, false> UT_SparseMatrixF;
380 typedef UT_SparseMatrixT<fpreal64, false> UT_SparseMatrixD;
381 typedef UT_SparseMatrixT<fpreal64, false> UT_SparseMatrix;
382 
383 
384 ///
385 /// This is a highly specialized varient of the SparseMatrix
386 /// which does not let you change the number or position of cells
387 /// It has, however, compiled fixed row offsets to make it fast
388 /// to look up specific rows in the matrix.
389 ///
390 template <typename T>
392 {
393  class ut_MatrixCell
394  {
395  public:
396  int myCol;
397  T myValue;
398  };
399 
400 public:
402  ~UT_SparseMatrixRowT();
403 
404  UT_NON_COPYABLE(UT_SparseMatrixRowT)
405 
406  // Can't mix paged and non paged, and this is a non-paged algorithm
407  // Destroys the source matrix in the process as we reuse its
408  // myCells array.
409  void buildFrom(UT_SparseMatrixT<T, false> &m,
410  bool invertdiag = false,
411  T tol=1e-5f);
412 
413  int getNumRows() const { return myNumRows; }
414  int getNumCols() const { return myNumCols; }
415 
416  /// Return the amount of memory used by this array.
417  int64 getMemoryUsage() const;
418 
419  // The 5000 was determined from experiments with UT_Vector.
420  bool shouldMultiThread() const
421  {
422  return getNumRows() > 5000;
423  }
424 
425  // Returns the index of the cell for which cell->row >= row is true
426  // first. This could be myCount if row is too high.
427  // myCells[result].myRow may be strictly greater than row if it isn't
428  // present.
429  int findCellFromRow(int row) const
430  { return myRowOffsets(row); }
431 
432  // Get the inverted diagonal.
433  void getDiagonalInv(UT_VectorT<T> &out) const;
434 
435  // computes M * v
436  THREADED_METHOD2_CONST(UT_SparseMatrixRowT, shouldMultiThread(), multVec,
437  const UT_VectorT<T> &, v,
438  UT_VectorT<T> &, result)
439  void multVecPartial(const UT_VectorT<T> &v, UT_VectorT<T> &result,
440  const UT_JobInfo &info) const;
441 
442  // computes M * v and accumulates the dot product of v & result
443  void multVecAndDot(
444  const UT_VectorT<T> &v,
445  UT_VectorT<T> &result,
446  fpreal64 *dotpq) const;
447 
448  /// Assumes this is a lower triangular matrix. Solves the equation
449  /// A x = b
450  /// If the diagonal of A is zero within tolerance, the corresponding
451  /// x coordinate is zero.
452  /// Returned is the number of artifical zeros places into x. 0 means
453  /// the solution encountered no singularities, 10 would mean 10
454  /// singularities.
455  int solveUpperTriangular(UT_VectorT<T> &x, const UT_VectorT<T> &b,
456  T tol=1e-5) const;
457  /// Given an upper triangular matrix, solves the lower triangular
458  /// transposed of it and negates the result.
459  int solveLowerTriangularTransposeNegate(UT_VectorT<T> &x,
460  const UT_VectorT<T> &b,
461  T tol=1e-5) const;
462 
463  /// Solves conjugate gradient using our specialized functions.
464  /// These allow us to perform some normal and dot operations
465  /// while the cache is still hot.
466  /// This matrix is the matrix to solve. The provided GT matrix
467  /// is the upper triangular result of cholesky factoriziation.
468  /// Norm is hardcoded to 2.
469  /// If the GT matrix is null, no preconditioner will be used.
470  float solveConjugateGradient(UT_VectorT<T> &x, const UT_VectorT<T> &b,
471  const UT_SparseMatrixRowT<T> *GT, T tol2=1e-5,
472  int max_iters = -1, int *iterout = NULL) const;
473 private:
474  THREADED_METHOD3_CONST(UT_SparseMatrixRowT, shouldMultiThread(),
475  multVecAndDotInternal,
476  const UT_VectorT<T> &, v,
477  UT_VectorT<T> &, result,
478  fpreal64 *, dotpq)
479  void multVecAndDotInternalPartial(const UT_VectorT<T> &v, UT_VectorT<T> &result,
480  fpreal64 *dotpq,
481  const UT_JobInfo &info) const;
482 
483  static const exint PARALLEL_BLOCK_SIZE = 1024;
484 
485  /// Extract a cell by its index.
486  inline ut_MatrixCell &getCell(int idx) const
487  {
488  return myCells[idx];
489  }
490 
491  int myNumRows;
492  int myNumCols;
493  ut_MatrixCell *myCells;
494  int myCount;
495  UT_IntArray myRowOffsets;
496  UT_VectorT<T> myDiagonal;
497 };
498 
501 
502 
503 
504 /// This is another highly specialized varient of the SparseMatrix
505 /// which allows multithreaded addition of elements to individual rows and
506 /// supports a conjugate gradient solve. This can be useful for solvers which
507 /// need to create and solve large linear systems in parallel.
508 /// It uses the ELL format which is appropriate for matrices with a limited
509 /// but fairly consistent numer of non-zeros per row, for example the result
510 /// of discretizations across regular grids.
511 template <typename T, bool colmajor = false, bool useexint = false>
513 {
514  typedef typename std::conditional<useexint, exint, int>::type inttype;
515 
516 public:
517 
519 
520  UT_SparseMatrixELLT(inttype rows, int nzeros);
521 
522  void init(inttype rows, int nzeros);
523 
524  void zero();
525 
526  exint getNumRows() const { return myRows; }
527 
528  int getNonZerosPerRow() const { return myNonZeros; }
529 
530  const UT_ValArray<T> &getRowValues() const { return myRowVals; }
531  UT_ValArray<T> &getRowValues() { return myRowVals; }
532 
533  const UT_ValArray<inttype> &getColumns() const { return myColumns; }
534  UT_ValArray<inttype> &getColumns() { return myColumns; }
535 
536  exint index(inttype row, int nz) const
537  {
538  if (colmajor)
539  return (exint)nz * myRows + (exint)row;
540  return (exint)row * (exint)myNonZeros + (exint)nz;
541  }
542 
543  bool appendRowElement(inttype row, inttype col, T val, int &rowidx)
544  {
545  UT_ASSERT(rowidx < myNonZeros);
546  exint idx = index(row, rowidx);
547  myRowVals(idx) = val;
548  myColumns(idx) = col;
549  rowidx++;
550  return true;
551  }
552 
553  // Sort rows by column index.
554  THREADED_METHOD(UT_SparseMatrixELLT, shouldMultiThread(),
555  sortRows)
556  void sortRowsPartial(const UT_JobInfo &info);
557 
558  /// Every reference to given rows is removed from the diagonal.
559  /// Because searching the whole matrix is expensive, assumes it
560  /// is a standard fluid matrix, so for each specified row, it
561  /// looks at all columns that are not itself and removes those.
562  void removeEffectOfRows(const UT_ExintArray &rows);
563 
564  bool shouldMultiThread() const
565  {
566  return getNumRows() > 5000;
567  }
568 
569  /// Copy to the supplied SparseMatrix.
570  void copyToSparse(UT_SparseMatrixT<T, false> &A) const;
571 
572  // Extract the inverted diagonal
573  THREADED_METHOD1_CONST(UT_SparseMatrixELLT, shouldMultiThread(),
574  getDiagonalInv, UT_VectorT<T> &, out)
575 
576  /// Get the inverse of the diagonal. Required for the conjugate gradient
577  /// solve when using Jacobi pre-conditioning.
578  void getDiagonalInvPartial(UT_VectorT<T> &out,
579  const UT_JobInfo &info) const;
580 
581  // computes M * v
582  THREADED_METHOD2_CONST(UT_SparseMatrixELLT, shouldMultiThread(),
583  multVec, const UT_VectorT<T> &, v,
584  UT_VectorT<T> &, result)
585 
586  void multVecPartial(const UT_VectorT<T> &v, UT_VectorT<T> &result,
587  const UT_JobInfo &info) const;
588 
589  // computes M * v and accumulates the dot product of v & result
590  void multVecAndDot(
591  const UT_VectorT<T> &v,
592  UT_VectorT<T> &result,
593  fpreal64 *dotpq) const;
594 
595  // computes M * v and accumulates the dot product of v & result
596  void multVecAndDotUpTo(
597  const UT_VectorT<T> &v,
598  UT_VectorT<T> &result,
599  fpreal64 *dotpq,
600  exint solverbase) const;
601 
602  /// Solves conjugate gradient using our specialized functions.
603  /// These allow us to perform some normal and dot operations
604  /// while the cache is still hot.
605  /// This matrix is the matrix to solve. The provided GT matrix
606  /// is the upper triangular result of cholesky factoriziation.
607  /// Norm is hardcoded to 2.
608  /// If the GT matrix is null, no preconditioner will be used.
609  float solveConjugateGradient(UT_VectorT<T> &x, const UT_VectorT<T> &b,
610  const UT_SparseMatrixRowT<T> *GT, T tol2=1e-5,
611  int max_iters = -1, int *iterout = NULL) const;
612 
613  // Writes out all of the non-zero elements as a Matlab "sparse" expression.
614  void printSparseMatlab(std::ostream &os,
615  const UT_String &varname) const;
616 
617  // Writes out all of the non-zero elements in Matrix Market format.
618  void printSparseMatrixMarket(std::ostream &os) const;
619 
620 private:
621 
622  THREADED_METHOD3_CONST(UT_SparseMatrixELLT, shouldMultiThread(),
623  multVecAndDotInternal,
624  const UT_VectorT<T> &, v,
625  UT_VectorT<T> &, result,
626  fpreal64 *, dotpq)
627 
628  void multVecAndDotInternalPartial(const UT_VectorT<T> &v, UT_VectorT<T> &result,
629  fpreal64 *dotpq,
630  const UT_JobInfo &info) const;
631 
632  THREADED_METHOD4_CONST(UT_SparseMatrixELLT, shouldMultiThread(),
633  multVecAndDotUpToInternal,
634  const UT_VectorT<T> &, v,
635  UT_VectorT<T> &, result,
636  fpreal64 *, dotpq,
637  exint, solverbase)
638 
639  void multVecAndDotUpToInternalPartial(const UT_VectorT<T> &v, UT_VectorT<T> &result,
640  fpreal64 *dotpq, exint solverbase,
641  const UT_JobInfo &info) const;
642 
643  static const exint PARALLEL_BLOCK_SIZE = 1024;
644 
645 private:
646 
647  UT_ValArray<T> myRowVals;
648  UT_ValArray<inttype> myColumns;
649  exint myRows;
650  int myNonZeros;
651 };
652 
653 typedef UT_SparseMatrixELLT<fpreal32> UT_SparseMatrixELLF;
654 typedef UT_SparseMatrixELLT<fpreal64> UT_SparseMatrixELLD;
655 
656 template <typename T> class UT_API UT_SparseMatrixBuilderT;
657 
658 /// Sparse matrix class that uses the compressed sparse row storage scheme.
659 /// This is a general-purpose sparse matrix class that can contain an arbitrary
660 /// number of non-zero elements per row.
661 template <typename T>
663 {
664 public:
665  /// Triplet to construct matrix. Is used only for setValues and addValues
666  /// to construct the matrix.
667  struct Triplet
668  {
669  exint myRow;
670  exint myCol;
672 
673  /// Construct a zero triplet.
674  Triplet() : myRow(0), myCol(0), myValue(0) {}
675 
676  /// Construct a triplet for the given row and column with value v.
677  Triplet(exint r, exint c, T v) : myRow(r), myCol(c), myValue(v) {}
678 
679  /// Returns true if the triplet's coordinate comes before the given
680  /// triplet's coordinate.
681  inline bool operator<(const Triplet &t) const {
682  return (myRow < t.myRow || (myRow == t.myRow && myCol < t.myCol));
683  }
684  };
685 
686  /// Defines one cell in the matrix. Can also be used to directly construct
687  /// the matrix with setValuesFromRows, which is easier to multithread.
688  struct ColumnValue
689  {
690  exint myCol;
692 
693  /// Construct a zero column-value.
694  ColumnValue() : myCol(0), myValue(0) {}
695 
696  /// Construct a column value for the given column with value v.
697  ColumnValue(exint c, T v) : myCol(c), myValue(v) {}
698 
699  /// Returns true if the column-value's column comes before the given
700  /// column-value's column.
701  inline bool operator<(const ColumnValue &cv) const {
702  return myCol < cv.myCol;
703  }
704  };
705 
706  /// Constructs an uninitialized sparse matrix
707  UT_SparseMatrixCSRT();
708 
709  /// Constructs a sparse matrix initialized with the given rows and columns.
710  UT_SparseMatrixCSRT(exint rows, exint columns);
711 
712  /// Constructs a sparse matrix that is a deep copy of the given sparse
713  /// matrix.
714  explicit UT_SparseMatrixCSRT(const UT_SparseMatrixCSRT &matrix);
715 
716  /// Sets the size of the matrix with the given rows and columns and clears
717  /// the matrix.
718  void init(exint rows, exint columns);
719 
720  /// Clears all data in the matrix
721  void zero();
722 
723  /// Swaps size and data elements with the given sparse matrix.
724  void swap(UT_SparseMatrixCSRT &other);
725 
726  /// The number of rows in the matrix.
727  exint getNumRows() const { return myNumRows; }
728 
729  /// The number of columns in the matrix.
730  exint getNumCols() const { return myNumCols; }
731 
732  /// The total number of non-zero elements in the matrix.
733  exint getNumNonZeros() const { return myCells.size(); }
734 
735  /// The number of non-zero elements in the given row.
736  exint getNumCellsInRow(exint row) const { return rowEnd(row) - rowBegin(row); }
737 
738  /// Clears then fills the matrix with the given array of triplets.
739  /// This sorts the triplets array.
740  /// Triplets with the same indices will be summed together.
741  /// A cell whose value is smaller than the tolerance will be deleted.
742  void setValues(UT_Array<Triplet> &triplets, T tolerance = 0.0);
743 
744  /// Clears then fills the matrix with the given array of ColumnValue arrays.
745  /// rowValues must have the same size as the number of rows in this matrix.
746  /// This data layout makes it easier to multithread the construction of the
747  /// sparse matrix entries.
748  void setValuesFromRows(UT_Array<UT_Array<ColumnValue>> &rowValues,
749  T tolerance = 0.0);
750 
751  /// Adds the given cells to the matrix. Triplets with the same coordinates
752  /// as cells already present in the matrix will be added together.
753  /// The array of triplets will be sorted unless alreadySorted is true.
754  /// Cells whose magnitude is below the tolerance value after the addition
755  /// will be discarded
756  void addValues(UT_Array<Triplet> &triplets, bool alreadySorted = false,
757  T tolerance=1e-5);
758 
759  /// Writes the diagonal values of the matrix into the given vector
760  /// If invert is true, the values will be inverted (i.e. 1/x).
761  /// If a row diagonal's value <= tolerance, then defaultValue is placed
762  /// in its result row.
763  void extractDiagonal(UT_VectorT<T> &result, bool invert = false,
764  T tolerance = 0, T defaultValue = 0) const;
765 
766  /// Matrix-vector multiplication. Computes result = M * v.
767  void multVec(const UT_VectorT<T> &v, UT_VectorT<T> &result) const;
768 
769  /// Matrix-vector multiplication.Computes result = M * v and returns the dot
770  /// product of v and the result.
771  UT_PreciseT<T> multVecAndDot(const UT_VectorT<T> &v, UT_VectorT<T> &result) const;
772 
773  /// Matrix-vector multiplication. Computes result = y - Ax. result can refer
774  /// to the same vector as y.
775  void subtractMultVec(const UT_VectorT<T> &x, const UT_VectorT<T> &y,
776  UT_VectorT<T> &result) const;
777 
778  /// Matrix-matrix multiplication. Computes result = M * B. Resultant
779  /// elements whose values are smaller than the given tolerance are deleted.
780  void multMatrix(const UT_SparseMatrixCSRT<T> &B, UT_SparseMatrixCSRT &result,
781  T tolerance = 0.0) const;
782 
783  /// Computes the transpose of this matrix. result can refer to this matrix.
784  void transpose(UT_SparseMatrixCSRT<T> &result) const;
785 
786  /// Element-wise scalar multiplication. Every element in this matrix is
787  /// multiplied by the given scalar.
788  void scale(const T& scalar);
789 
790  /// Element-wise scalar multiplication. Every element in row i of the matrix
791  /// is multiplied by scalars[i]
792  void scaleRows(const UT_VectorT<T> &scalars);
793 
794  /// Multiples each row such that the row diagonal becomes 1. If the row
795  /// diagonal is below the tolerance, the row is unchanged.
796  void normalizeRows(T tolerance = 1e-5);
797 
798  /// Calculates the norms of each row. result must have the same size as the
799  /// number of rows in this matrix. p determines the exponent of each column.
800  /// i.e. result[i] = SUM( |Aij|^p ) for j in row(i)
801  /// If invert is true, then inverts each sum
802  /// i.e. result[i] = 1.0 / SUM( |Aij|^p ) for j in row(i)
803  /// If the row norm is smaller than the tolerance, defaultValue is
804  /// placed in its result entry instead.
805  void rowNorms(UT_VectorT<T> &result, int p = 2, bool invert = false,
806  T tolerance = 0, T defaultValue = 0) const;
807 
808  /// Analyzes the matrix and constructs a directed acyclic graph as a level
809  /// set, where each level contains rows that are independent of each other.
810  /// More specifically, level i of the levelSet contains rows that are only
811  /// dependent on rows present in levels [0, i-1].
812  /// The size of the levelSet is the number of levels.
813  /// If buildForUpper is true, this constructs a level set for the upper
814  /// triangular part of the matrix. Otherwise, this constructs a level set
815  /// for the lower triangular part of the matrix.
817  void buildDependencyLevelSet(LevelSet &levelSet, bool buildForUpper = false) const;
818 
819  /// Assumes this is a lower triangular matrix. Solves the equation Ax = b.
820  /// Values may be present in the upper triangular part of the matrix
821  /// but they will be ignored.
822  /// If unitDiagonal is true, then 1 will be used instead of the
823  /// current diagonal values.
824  /// If a diagonal of A is zero within the tolerance, 0 will be placed
825  /// in the corresponding row for x.
826  /// If negate is true, then x is negated
827  /// x can refer to the same vector as b to solve in-place.
828  void solveLowerTriangular(UT_VectorT<T> &x, const UT_VectorT<T> &b,
829  bool unitDiagonal = false, T tolerance = 1e-5,
830  bool negate = false) const;
831 
832  /// Assumes this is an upper triangular matrix. Solves the equation Ax = b.
833  /// Values may be present in the lower triangular part of the matrix
834  /// but they will be ignored.
835  /// If unitDiagonal is true, then 1 will be used instead of the
836  /// current diagonal values.
837  /// If a diagonal of A is zero within the tolerance, 0 will be placed
838  /// in the corresponding row for x.
839  /// If negate is true, then x is negated
840  /// x can refer to the same vector as b to solve in-place.
841  void solveUpperTriangular(UT_VectorT<T> &x, const UT_VectorT<T> &b,
842  bool unitDiagonal = false, T tolerance = 1e-5,
843  bool negate = false) const;
844 
845  /// Solves the lower triangular system A^T x = b.
846  /// A is assumed to be an upper triangular matrix.
847  /// Values may be present in the lower triangular part of the matrix
848  /// but they will be ignored.
849  /// If unitDiagonal is true, then 1 will be used instead of the
850  /// current diagonal values.
851  /// If a diagonal of A is zero within the tolerance, 0 will be placed
852  /// in the corresponding row for x.
853  /// If negate is true, then x is negated.
854  void solveLowerTriangularTranspose(UT_VectorT<T> &x, const UT_VectorT<T> &b,
855  bool unitDiagonal = false, T tolerance = 1e-5,
856  bool negate = false) const;
857 
858  /// Solves the upper triangular system A^T x = b.
859  /// A is assumed to be a lower triangular matrix.
860  /// Values may be present in the upper triangular part of the matrix
861  /// but they will be ignored.
862  /// If unitDiagonal is true, then 1 will be used instead of the
863  /// current diagonal values.
864  /// If a diagonal of A is zero within the tolerance, 0 will be placed
865  /// in the corresponding row for x.
866  /// If negate is true, then x is negated.
867  void solveUpperTriangularTranspose(UT_VectorT<T> &x, const UT_VectorT<T> &b,
868  bool unitDiagonal = false, T tolerance = 1e-5,
869  bool negate = false) const;
870 
871  /// Factorizes this matrix into a triangular matrix M such that M*M^T ~= A
872  /// This keeps the non-zero structure of the matrix. The matrix must be
873  /// symmetric.
874  /// This is unstable depending on the diagonal; Returns -1 if the diagonal
875  /// contains zeros within the given tolerance, and -2 if not positive
876  /// definite (diagonal has negative numbers).
877  /// Returns 0 on success.
878  /// If useModified = true, then this uses the Modified Incomplete Cholesky
879  /// Factorization, where discarded entries are accounted for by adjusting
880  /// the diagonal. tau is a tuning constant that scales the adjustment from
881  /// the missing entries. mindiagratio is the relative tolerance at which
882  /// the original diagonal will be used if the matrix becomes negative
883  /// definite as a result of the computation.
884  int incompleteCholeskyFactorization(T tol=1e-5, bool useModified = false,
885  T tau = 0.97, T mindiagratio = 0.25);
886 
887  /// Factorizes this matrix into L and U where LU approximates this matrix.
888  /// The non-zero structure of LU matches this matrix; that is, this produces
889  /// ILU(0) of this matrix. A lower triangular level set is needed for
890  /// multithreading.
891  /// e.g.
892  /// LevelSet levelSet;
893  /// A.buildDependencyLevelSet(levelSet);
894  /// A.incompleteLUFactorization(L, U, 1e-5, levelSet);
895  void incompleteLUFactorization(UT_SparseMatrixCSRT<T> &L,
896  UT_SparseMatrixCSRT<T> &U, T tolerance,
897  const LevelSet &workUnits, UT_Interrupt *boss = NULL) const;
898 
899  /// Initializes out to a matrix with size (rowend-rowstart, colend-colstart)
900  /// and fills it with the elements defined by the submatrix in rows
901  /// [rowstart, rowend), [colstart, colend).
902  void extractSubMatrix(UT_SparseMatrixCSRT<T> &out,
903  exint rowstart, exint rowend, exint colstart, exint colend) const;
904 
905  /// Calls inspect(row, col, value) on each cell. Each (row, col) is visited
906  /// exactly once. This is done in parallel over the rows by default, but can
907  /// be done serially by setting serial = true. inspect can modify the cell
908  /// values if it has the signature (exint, exint, &T).
909  template <typename CellFunction>
910  void visit(const CellFunction& inspect, bool serial = false)
911  {
912  parallelExecute(UT_BlockedRange<exint>(0, myNumRows), [this, &inspect]
913  (const UT_BlockedRange<exint> &r)
914  {
915  for (exint row = r.begin(); row < r.end(); ++row)
916  for (exint i = rowBegin(row), n = rowEnd(row); i < n; ++i)
917  inspect(row, cellColumn(i), cellValue(i));
918  }, serial, myLightRowOpSubRatio, myLightRowOpGrainSize);
919  }
920 
921  /// Condition is called for each cell exactly once. If the condition returns
922  /// true, then the cell is removed from the matrix. The function signature
923  /// of the condition should be (exint row, exint col, T value) -> bool.
924  /// condition can modify the cell vakyes if it has the signature
925  /// (exint, exint, &T)
926  template <typename CellFunction>
927  void removeIf(const CellFunction& condition)
928  {
929  exint idx = -1, i = rowBegin(0);
930  for (exint row = 0; row < myNumRows; ++row)
931  {
932  for (exint n = rowEnd(row); i < n; ++i)
933  if (!condition(row, cellColumn(i), cellValue(i)) && ++idx != i)
934  myCells[idx] = myCells[i];
935  myRowOffsets[row+1] = idx+1;
936  }
937  myCells.setSize(idx+1);
938  }
939 
940  /// Returns true if any non-zero element in this matrix has value NaN.
941  bool hasNan() const;
942 
943  /// Asserts that the matrix contains no element with value NaN.
944  void testForNan() const;
945 
946  /// Writes the full matrix, including zeros, to the given output stream.
947  void printFull(std::ostream &os) const;
948 
949  /// Serializes the matrix to the given output stream.
950  void save(std::ostream &os) const;
951 
952  /// Deserializes the matrix from the given input stream.
953  void load(UT_IStream &is);
954 
955  /// Deep copies all data from the given matrix.
957 
958  /// Equivalent to A.scale(scalar)
959  UT_SparseMatrixCSRT<T> &operator*=(const T& scalar) { scale(scalar); return *this; }
960 
961 private:
962 
963  // Helper functions to get value and column
964  inline T& cellValue(exint offset) { return myCells[offset].myValue; }
965  inline const T &cellValue(exint offset) const { return myCells[offset].myValue; }
966  inline const exint &cellColumn(exint offset) const { return myCells[offset].myCol; }
967 
968  // Helper functions to return the beginning and end indexes into myValues
969  // for the given row. This can be used to iterate over the non-zero values
970  // of a particular row.
971  // e.g. for (exint i = rowBegin(row); i < rowEnd(row); ++i)
972  // ... Do something with cellValue(i) and cellColumn(i)
973  inline const exint &rowBegin(exint row) const { return myRowOffsets[row]; }
974  inline const exint &rowEnd(exint row) const { return myRowOffsets[row + 1]; }
975 
976  // Multithreading constants
977  // If the number of rows is less than this number, all operations run
978  // serially
979  static const int myParallelThreshold = 1000;
980 
981  // The subratio and grainsize used for row operations with cheap work units
982  static const int myLightRowOpSubRatio = 0;
983  static const int myLightRowOpGrainSize = 64;
984 
985  // Executes the given body over the given range. Can force this method to
986  // run serially by setting serial = true
987  template <typename Body>
988  inline void parallelExecute(const UT_BlockedRange<exint> &range,
989  const Body &body, bool serial = false, int subratio = 0,
990  int grainsize = 32, exint parallelThreshold = -1) const {
991  // Use internal parallel threshold by default
992  if (parallelThreshold < 0)
993  parallelThreshold = myParallelThreshold;
994  // Perform serially if specified or if number of rows is below threshold
995  if (myNumRows < parallelThreshold || serial)
996  UTserialFor(range, body);
997  else
998  UTparallelFor(range, body, subratio, grainsize);
999  };
1000 
1001 private:
1002  exint myNumRows;
1003  exint myNumCols;
1004 
1005  // Stores the non-zero cells of the matrix, sorted by row and column.
1006  // Has size Nz, where Nz is the number of non-zero values.
1007  UT_Array<ColumnValue> myCells;
1008 
1009  // Stores the offset of myValues at which each row starts.
1010  // Has size myNumRows + 1.
1011  // myRowOffsets[r] is the offset of myValues where row r begins.
1012  // myRowOffsets[r + 1] - myRowOffsets[r] is the number of
1013  // non-zero values in row r.
1014  // myRowOffsets[myNumRows] has the sentinel value Nz
1015  UT_ExintArray myRowOffsets;
1016 
1017  friend class UT_SparseMatrixBuilderT<T>;
1018 };
1019 
1022 
1023 /// Simple helper class to construct a SparseMatrixCSRT. This operates on the
1024 /// matrix data in-place and is generally much more performant than constructing
1025 /// via triplets, but the builder has the limitation of only being able to add
1026 /// to rows sequentially; i.e. each call to startRow must start the construction
1027 /// of a row greater than the last, while addToColumn can be called with any
1028 /// column ordering.
1029 /// 1. UT_SparseMatrixCSRD matrix(M, N);
1030 /// 2. UT_SparseMatrixBuilderT builder(matrix);
1031 /// 3. for (exint r = startRow; r < endRow; ++r)
1032 /// 4. builder.startRow(r);
1033 /// 5. for (any column)
1034 /// 6. builder.addToColumn(column, value);
1035 /// 7. builder.finish();
1036 template <typename T>
1037 class UT_API UT_SparseMatrixBuilderT
1038 {
1039 public:
1041 
1042  /// Construct an uninitialized sparse matrix builder.
1043  UT_SparseMatrixBuilderT() : myMatrix(NULL) {}
1044 
1045  /// Construct a sparse matrix builder for the given matrix.
1046  UT_SparseMatrixBuilderT(SparseMatrixType &matrix) { init(matrix); }
1047 
1048  /// Initializes the builder to start building the given matrix
1049  void init(SparseMatrixType &matrix);
1050 
1051  /// Sets the minimum capacity of non-zero elements for the given matrix.
1052  /// This is used to preallocate memory for the matrix to avoid excessive
1053  /// reallocation as elements are added.
1054  void setCapacity(exint capacity);
1055 
1056  /// Advances the current row to the given row. The row must be greater than
1057  /// the current row.
1058  void startRow(exint row);
1059 
1060  /// Adds the given value at the given column to the current row. If a cell
1061  /// is already present for the given column, the given value is added to it.
1062  void addToColumn(exint col, T value);
1063 
1064  /// Completes the remaining rows and finalizes the matrix.
1065  void finish();
1066 
1067 private:
1068  exint myCurrentRow;
1069  SparseMatrixType *myMatrix;
1070 };
1071 
1074 
1075 #endif
int getNumRows() const
type
Definition: core.h:556
void UTparallelFor(const Range &range, const Body &body, const int subscribe_ratio=2, const int min_grain_size=1, const bool force_use_task_scope=true)
int getNumRows() const
#define THREADED_METHOD4_CONST(CLASSNAME, DOMULTI, METHOD, PARMTYPE1, PARMNAME1, PARMTYPE2, PARMNAME2, PARMTYPE3, PARMNAME3, PARMTYPE4, PARMNAME4)
exint getNumCols() const
The number of columns in the matrix.
ColumnValue()
Construct a zero column-value.
GLsizei GLenum const void * indices
Definition: glcorearb.h:406
GLenum GLint * range
Definition: glcorearb.h:1925
bool operator<(const ColumnValue &cv) const
*get result *(waiting if necessary)*A common idiom is to fire a bunch of sub tasks at the and then *wait for them to all complete We provide a helper class
Definition: thread.h:632
UT_SparseMatrixRowT< fpreal64 > UT_SparseMatrixRowD
void
Definition: png.h:1083
GLboolean invert
Definition: glcorearb.h:549
exint getNumNonZeros() const
The total number of non-zero elements in the matrix.
exint getNumRows() const
const GLdouble * v
Definition: glcorearb.h:837
bool shouldMultiThread() const
GLsizei const GLfloat * value
Definition: glcorearb.h:824
const UT_ValArray< inttype > & getColumns() const
UT_SparseMatrixCSRT< T > SparseMatrixType
IMATH_HOSTDEVICE constexpr Plane3< T > operator-(const Plane3< T > &plane) IMATH_NOEXCEPT
Reflect the pla.
Definition: ImathPlane.h:253
int64 exint
Definition: SYS_Types.h:125
void swap(T &lhs, T &rhs)
Definition: pugixml.cpp:7440
ColumnValue(exint c, T v)
Construct a column value for the given column with value v.
class UT_API UT_SparseMatrixRowT
#define UT_API
Definition: UT_API.h:14
GLint y
Definition: glcorearb.h:103
bool isStillSorted() const
**But if you need a result
Definition: thread.h:622
float fpreal32
Definition: SYS_Types.h:200
uint64 value_type
Definition: GA_PrimCompat.h:29
OIIO_FORCEINLINE vbool4 operator>=(const vint4 &a, const vint4 &b)
Definition: simd.h:4738
void subtractMultVecNoThread(const UT_VectorT< T > &v, UT_VectorT< T > &result) const
int getNumCols() const
UT_SparseMatrixRowT< fpreal32 > UT_SparseMatrixRowF
bool operator<(const Triplet &t) const
double fpreal64
Definition: SYS_Types.h:201
UT_SparseMatrixCSRT< T > & operator*=(const T &scalar)
Equivalent to A.scale(scalar)
GLsizei GLboolean transpose
Definition: glcorearb.h:832
void multVec(const UT_VectorT< T > &v, UT_VectorT< T > &result) const
bool operator==(const BaseDimensions< T > &a, const BaseDimensions< Y > &b)
Definition: Dimensions.h:137
GA_API const UT_StringHolder scale
OIIO_FORCEINLINE vbool4 operator>(const vint4 &a, const vint4 &b)
Definition: simd.h:4718
GLdouble n
Definition: glcorearb.h:2008
GLfloat f
Definition: glcorearb.h:1926
GLintptr offset
Definition: glcorearb.h:665
exint getNumRows() const
The number of rows in the matrix.
OIIO_FORCEINLINE const vint4 & operator+=(vint4 &a, const vint4 &b)
Definition: simd.h:4512
void removeIf(const CellFunction &condition)
UT_SparseMatrixBuilderT(SparseMatrixType &matrix)
Construct a sparse matrix builder for the given matrix.
const UT_ValArray< T > & getRowValues() const
typename UT_TypePromoteT< T >::PreciseType UT_PreciseT
#define UT_NON_COPYABLE(CLASS)
Define deleted copy constructor and assignment operator inside a class.
bool operator<(const GU_TetrahedronFacet &a, const GU_TetrahedronFacet &b)
IMATH_HOSTDEVICE constexpr Color4< T > operator*(S a, const Color4< T > &v) IMATH_NOEXCEPT
Reverse multiplication: S * Color4.
Definition: ImathColor.h:732
#define SYS_ALIGN16
Definition: SYS_Align.h:100
long long int64
Definition: SYS_Types.h:116
UT_SparseMatrixBuilderT< fpreal32 > UT_SparseMatrixBuilderF
void visit(const CellFunction &inspect, bool serial=false)
bool appendRowElement(inttype row, inttype col, T val, int &rowidx)
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1222
Triplet()
Construct a zero triplet.
GLint GLenum GLint x
Definition: glcorearb.h:409
IMATH_HOSTDEVICE constexpr Quat< T > operator+(const Quat< T > &q1, const Quat< T > &q2) IMATH_NOEXCEPT
Quaterion addition.
Definition: ImathQuat.h:905
GLdouble t
Definition: glad.h:2397
void subtractMultVec(const UT_VectorT< T > &v, UT_VectorT< T > &result) const
Do result = result - (M * v)
#define THREADED_METHOD2_CONST(CLASSNAME, DOMULTI, METHOD, PARMTYPE1, PARMNAME1, PARMTYPE2, PARMNAME2)
auto reserve(std::back_insert_iterator< Container > it, size_t n) -> checked_ptr< typename Container::value_type >
Definition: format.h:578
#define THREADED_METHOD1_CONST(CLASSNAME, DOMULTI, METHOD, PARMTYPE1, PARMNAME1)
Triplet(exint r, exint c, T v)
Construct a triplet for the given row and column with value v.
GLenum void ** pointer
Definition: glcorearb.h:810
exint getNumCellsInRow(exint row) const
The number of non-zero elements in the given row.
void accept(Visitor &visitor) const
UT_ValArray< inttype > & getColumns()
UT_SparseMatrixBuilderT< fpreal64 > UT_SparseMatrixBuilderD
int findCellFromRow(int row) const
LeafData & operator=(const LeafData &)=delete
GLuint index
Definition: glcorearb.h:786
GLuint GLfloat * val
Definition: glcorearb.h:1608
GLbyte GLbyte nz
Definition: glad.h:2247
UT_ValArray< T > & getRowValues()
OIIO_FORCEINLINE const vint4 & operator-=(vint4 &a, const vint4 &b)
Definition: simd.h:4539
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:156
GLenum GLenum GLsizei void * row
Definition: glad.h:5135
GLboolean r
Definition: glcorearb.h:1222
bool operator!=(const BaseDimensions< T > &a, const BaseDimensions< Y > &b)
Definition: Dimensions.h:165
UT_SparseMatrixCSRT< fpreal32 > UT_SparseMatrixCSRF
int getNonZerosPerRow() const
#define THREADED_METHOD3_CONST(CLASSNAME, DOMULTI, METHOD, PARMTYPE1, PARMNAME1, PARMTYPE2, PARMNAME2, PARMTYPE3, PARMNAME3)
that also have some descendant prim *whose name begins with which in turn has a child named baz where *the predicate and *a name There is also one special expression reference
UT_SparseMatrixBuilderT()
Construct an uninitialized sparse matrix builder.
Declare prior to use.
exint index(inttype row, int nz) const
#define THREADED_METHOD(CLASSNAME, DOMULTI, METHOD)
void UTserialFor(const Range &range, const Body &body)
bool shouldMultiThread() const
int getNumCols() const
UT_Array< UT_ExintArray > LevelSet
GLenum src
Definition: glcorearb.h:1793
UT_SparseMatrixCSRT< fpreal64 > UT_SparseMatrixCSRD