17 #ifndef __UT_SparseMatrix_H__
18 #define __UT_SparseMatrix_H__
30 #include <type_traits>
37 template <
typename T,
bool IsPaged>
47 inline bool operator<(
const ut_MatrixCell &o)
const
51 if (myRow == o.myRow && myCol < o.myCol)
59 static const int CELL_PAGESIZE = 1024;
60 static const int CELL_PAGEMASK = 1023;
61 static const int CELL_PAGEBITS = 10;
66 using iterator_category = std::random_access_iterator_tag;
68 using difference_type = std::ptrdiff_t;
73 { myMatrix = matrix; myPos = idx; repage(); }
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); }
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; }
92 ut_MatrixCell &
operator*()
const {
return *myData; }
93 ut_MatrixCell *operator->()
const {
return myData; }
98 { myPage = myPos >> CELL_PAGEBITS; myOffset = myPos & CELL_PAGEMASK;
100 if (myPage < myMatrix->myCellPages.entries())
101 myData = &myMatrix->myCellPages(myPage)[myOffset];
105 ut_MatrixCell *myData;
107 int myPage, myOffset;
112 static const int CELLBITS = 2;
113 static const int CELLSIZE = 1 << CELLBITS;
114 static const int CELLMASK = CELLSIZE-1;
136 int64 getMemoryUsage()
const;
137 int64 getIdealMemoryUsage()
const;
147 void init(
int rows,
int cols);
156 return getNumRows() > 5000;
160 bool addToElement(
int row,
int col,
T value);
166 int findCellFromRow(
int row)
const;
172 multVecInternal(v, result);
179 subtractMultVecInternal(v, result);
184 subtractMultVecInternalNoThread(v, result);
202 int rowstart,
int rowend,
203 int colstart,
int colend)
const;
207 int rowstart,
int rowend,
208 int colstart,
int colend)
const;
212 void getSmallSquareSubMatrix(
T submatrix[],
218 template<
typename Visitor>
221 for(
exint ci = 0; ci < myCount; ++ci)
223 ut_MatrixCell *cell = &getCell(ci);
224 visitor(cell->myRow, cell->myCol, cell->myValue);
230 void clearRowsAndColumns(
const UT_BitArray &toclear);
252 int incompleteCholeskyFactorization(
T tol=1e-5);
258 int modifiedIncompleteCholesky(
T tau = 0.97,
259 T mindiagratio = 0.25,
283 bool (*callback_func)(
void *) = 0,
284 void *callback_data = 0,
T tol2=1e-5,
285 int max_iters = -1)
const;
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);
306 void printFull(std::ostream &os) const;
309 void printSparse(std::ostream &os) const;
312 void printSparseMatlab(std::ostream &os,
316 void save(std::ostream &os) const;
327 void compile() const;
328 bool isCompiled()
const {
return myCompiledFlag; }
332 void testForNan()
const;
336 void forceCompile()
const;
339 inline ut_MatrixCell &getCell(
int idx)
const
342 return myCellPages(idx >> CELL_PAGEBITS)[idx & CELL_PAGEMASK];
354 subtractMultVecInternal,
361 void compile4() const;
366 mutable ut_MatrixCell *myCells;
368 mutable
int *my4RowOffsets;
369 mutable ut_4MatrixCell *my4Cells;
370 mutable
int my4Count;
372 mutable
bool myCompiledFlag;
373 mutable
bool myStillSortedFlag;
374 mutable
bool my4CompiledFlag;
390 template <typename T>
402 ~UT_SparseMatrixRowT();
410 bool invertdiag =
false,
417 int64 getMemoryUsage()
const;
422 return getNumRows() > 5000;
430 {
return myRowOffsets(row); }
446 fpreal64 *dotpq) const;
459 int solveLowerTriangularTransposeNegate(
UT_VectorT<T> &x,
471 const UT_SparseMatrixRowT<T> *GT, T tol2=1e-5,
472 int max_iters = -1,
int *iterout = NULL) const;
475 multVecAndDotInternal,
483 static const
exint PARALLEL_BLOCK_SIZE = 1024;
486 inline ut_MatrixCell &getCell(
int idx)
const
493 ut_MatrixCell *myCells;
511 template <
typename T,
bool colmajor = false,
bool useex
int = false>
522 void init(inttype rows,
int nzeros);
547 myRowVals(idx) =
val;
548 myColumns(idx) = col;
564 bool shouldMultiThread()
const
566 return getNumRows() > 5000;
593 fpreal64 *dotpq) const;
596 void multVecAndDotUpTo(
600 exint solverbase) const;
610 const UT_SparseMatrixRowT<T> *GT, T tol2=1e-5,
611 int max_iters = -1,
int *iterout = NULL) const;
614 void printSparseMatlab(std::ostream &os,
618 void printSparseMatrixMarket(std::ostream &os) const;
623 multVecAndDotInternal,
633 multVecAndDotUpToInternal,
640 fpreal64 *dotpq, exint solverbase,
643 static const exint PARALLEL_BLOCK_SIZE = 1024;
661 template <typename T>
677 Triplet(exint
r, exint
c, T v) : myRow(r), myCol(c), myValue(v) {}
702 return myCol < cv.
myCol;
707 UT_SparseMatrixCSRT();
710 UT_SparseMatrixCSRT(exint rows, exint columns);
714 explicit UT_SparseMatrixCSRT(
const UT_SparseMatrixCSRT &matrix);
718 void init(exint rows, exint columns);
724 void swap(UT_SparseMatrixCSRT &other);
764 T tolerance = 0, T defaultValue = 0)
const;
781 T tolerance = 0.0)
const;
788 void scale(
const T& scalar);
796 void normalizeRows(T tolerance = 1e-5);
806 T tolerance = 0, T defaultValue = 0)
const;
817 void buildDependencyLevelSet(LevelSet &levelSet,
bool buildForUpper =
false)
const;
829 bool unitDiagonal =
false, T tolerance = 1e-5,
830 bool negate =
false)
const;
842 bool unitDiagonal =
false, T tolerance = 1e-5,
843 bool negate =
false)
const;
855 bool unitDiagonal =
false, T tolerance = 1e-5,
856 bool negate =
false)
const;
868 bool unitDiagonal =
false, T tolerance = 1e-5,
869 bool negate =
false)
const;
884 int incompleteCholeskyFactorization(T tol=1e-5,
bool useModified =
false,
885 T tau = 0.97, T mindiagratio = 0.25);
897 const LevelSet &workUnits,
UT_Interrupt *boss = NULL)
const;
903 exint rowstart, exint rowend, exint colstart, exint colend)
const;
909 template <
typename CellFunction>
910 void visit(
const CellFunction& inspect,
bool serial =
false)
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);
926 template <
typename CellFunction>
929 exint idx = -1, i = rowBegin(0);
930 for (exint
row = 0;
row < myNumRows; ++
row)
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;
937 myCells.setSize(idx+1);
944 void testForNan()
const;
947 void printFull(std::ostream &os)
const;
950 void save(std::ostream &os)
const;
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; }
973 inline const exint &rowBegin(exint
row)
const {
return myRowOffsets[
row]; }
974 inline const exint &rowEnd(exint
row)
const {
return myRowOffsets[row + 1]; }
979 static const int myParallelThreshold = 1000;
982 static const int myLightRowOpSubRatio = 0;
983 static const int myLightRowOpGrainSize = 64;
987 template <
typename Body>
989 const Body &body,
bool serial =
false,
int subratio = 0,
990 int grainsize = 32, exint parallelThreshold = -1)
const {
992 if (parallelThreshold < 0)
993 parallelThreshold = myParallelThreshold;
995 if (myNumRows < parallelThreshold || serial)
1017 friend class UT_SparseMatrixBuilderT<T>;
1036 template <
typename T>
1049 void init(SparseMatrixType &matrix);
1054 void setCapacity(exint capacity);
1058 void startRow(exint
row);
1062 void addToColumn(exint col, T
value);
1069 SparseMatrixType *myMatrix;
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)
#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
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
UT_SparseMatrixRowT< fpreal64 > UT_SparseMatrixRowD
exint getNumNonZeros() const
The total number of non-zero elements in the matrix.
bool shouldMultiThread() const
GLsizei const GLfloat * value
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.
void swap(T &lhs, T &rhs)
ColumnValue(exint c, T v)
Construct a column value for the given column with value v.
class UT_API UT_SparseMatrixRowT
bool isStillSorted() const
**But if you need a result
OIIO_FORCEINLINE vbool4 operator>=(const vint4 &a, const vint4 &b)
void subtractMultVecNoThread(const UT_VectorT< T > &v, UT_VectorT< T > &result) const
UT_SparseMatrixRowT< fpreal32 > UT_SparseMatrixRowF
bool operator<(const Triplet &t) const
UT_SparseMatrixCSRT< T > & operator*=(const T &scalar)
Equivalent to A.scale(scalar)
GLsizei GLboolean transpose
void multVec(const UT_VectorT< T > &v, UT_VectorT< T > &result) const
bool operator==(const BaseDimensions< T > &a, const BaseDimensions< Y > &b)
GA_API const UT_StringHolder scale
OIIO_FORCEINLINE vbool4 operator>(const vint4 &a, const vint4 &b)
exint getNumRows() const
The number of rows in the matrix.
OIIO_FORCEINLINE const vint4 & operator+=(vint4 &a, const vint4 &b)
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.
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
Triplet()
Construct a zero triplet.
IMATH_HOSTDEVICE constexpr Quat< T > operator+(const Quat< T > &q1, const Quat< T > &q2) IMATH_NOEXCEPT
Quaterion addition.
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 >
#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.
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
UT_ValArray< T > & getRowValues()
OIIO_FORCEINLINE const vint4 & operator-=(vint4 &a, const vint4 &b)
GLenum GLenum GLsizei void * row
bool operator!=(const BaseDimensions< T > &a, const BaseDimensions< Y > &b)
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.
exint index(inttype row, int nz) const
#define THREADED_METHOD(CLASSNAME, DOMULTI, METHOD)
void UTserialFor(const Range &range, const Body &body)
bool shouldMultiThread() const
UT_Array< UT_ExintArray > LevelSet
UT_SparseMatrixCSRT< fpreal64 > UT_SparseMatrixCSRD