SNAP Library 6.0, Developer Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
linalg.h
Go to the documentation of this file.
1 // forward declarations
3 class TLinAlg;
4 class TLAMisc;
5 
7 // Matrix
8 class TMatrix {
9 private:
10  bool Transposed;
11 protected:
12  virtual void PMultiply(const TFltVV& B, int ColId, TFltV& Result) const = 0;
13  virtual void PMultiply(const TFltV& Vec, TFltV& Result) const = 0;
14  virtual void PMultiplyT(const TFltVV& B, int ColId, TFltV& Result) const = 0;
15  virtual void PMultiplyT(const TFltV& Vec, TFltV& Result) const = 0;
16 
17  virtual int PGetRows() const = 0;
18  virtual int PGetCols() const = 0;
19 public:
20  TMatrix(): Transposed(false) {}
21  virtual ~TMatrix() { }
22 
23  // Result = A * B(:,ColId)
24  void Multiply(const TFltVV& B, int ColId, TFltV& Result) const {
25  if (Transposed) { PMultiplyT(B, ColId, Result); }
26  else { PMultiply(B, ColId, Result); }
27  }
28  // Result = A * Vec
29  void Multiply(const TFltV& Vec, TFltV& Result) const {
30  if (Transposed) { PMultiplyT(Vec, Result); }
31  else { PMultiply(Vec, Result); }
32  }
33  // Result = A' * B(:,ColId)
34  void MultiplyT(const TFltVV& B, int ColId, TFltV& Result) const {
35  if (Transposed) { PMultiply(B, ColId, Result); }
36  else { PMultiplyT(B, ColId, Result); }
37  }
38  // Result = A' * Vec
39  void MultiplyT(const TFltV& Vec, TFltV& Result) const{
40  if (Transposed) { PMultiply(Vec, Result); }
41  else { PMultiplyT(Vec, Result); }
42  }
43 
44  // number of rows
45  int GetRows() const { return Transposed ? PGetCols() : PGetRows(); }
46  // number of columns
47  int GetCols() const { return Transposed ? PGetRows() : PGetCols(); }
48 
49  void Transpose() { Transposed = !Transposed; }
50 };
51 
53 // Sparse-Column-Matrix
54 // matrix is given with columns as sparse vectors
55 class TSparseColMatrix: public TMatrix {
56 public:
57  // number of rows and columns of matrix
58  int RowN, ColN;
59  // vector of sparse columns
61 protected:
62  // Result = A * B(:,ColId)
63  virtual void PMultiply(const TFltVV& B, int ColId, TFltV& Result) const;
64  // Result = A * Vec
65  virtual void PMultiply(const TFltV& Vec, TFltV& Result) const;
66  // Result = A' * B(:,ColId)
67  virtual void PMultiplyT(const TFltVV& B, int ColId, TFltV& Result) const;
68  // Result = A' * Vec
69  virtual void PMultiplyT(const TFltV& Vec, TFltV& Result) const;
70 
71  int PGetRows() const { return RowN; }
72  int PGetCols() const { return ColN; }
73 
74 public:
76  TSparseColMatrix(TVec<TIntFltKdV> _ColSpVV): TMatrix(), ColSpVV(_ColSpVV) {}
77  TSparseColMatrix(TVec<TIntFltKdV> _ColSpVV, const int& _RowN, const int& _ColN):
78  TMatrix(), RowN(_RowN), ColN(_ColN), ColSpVV(_ColSpVV) {}
79  // loads Matlab sparse matrix format: row, column, value.
80  // Indexes start with 1.
81  void Save(TSOut& SOut) {
82  SOut.Save(RowN); SOut.Save(ColN); ColSpVV.Save(SOut); }
83  void Load(TSIn& SIn) {
84  SIn.Load(RowN); SIn.Load(ColN); ColSpVV = TVec<TIntFltKdV>(SIn); }
85 };
86 
88 // Sparse-Row-Matrix
89 // matrix is given with rows as sparse vectors
90 class TSparseRowMatrix: public TMatrix {
91 public:
92  // number of rows and columns of matrix
93  int RowN, ColN;
94  // vector of sparse rows
96 protected:
97  // Result = A * B(:,ColId)
98  virtual void PMultiply(const TFltVV& B, int ColId, TFltV& Result) const;
99  // Result = A * Vec
100  virtual void PMultiply(const TFltV& Vec, TFltV& Result) const;
101  // Result = A' * B(:,ColId)
102  virtual void PMultiplyT(const TFltVV& B, int ColId, TFltV& Result) const;
103  // Result = A' * Vec
104  virtual void PMultiplyT(const TFltV& Vec, TFltV& Result) const;
105 
106  int PGetRows() const { return RowN; }
107  int PGetCols() const { return ColN; }
108 
109 public:
111  TSparseRowMatrix(TVec<TIntFltKdV> _RowSpVV): TMatrix(), RowSpVV(_RowSpVV) {}
112  TSparseRowMatrix(TVec<TIntFltKdV> _RowSpVV, const int& _RowN, const int& _ColN):
113  TMatrix(), RowN(_RowN), ColN(_ColN), RowSpVV(_RowSpVV) {}
114  // loads Matlab sparse matrix format: row, column, value.
115  // Indexes start with 1.
116  TSparseRowMatrix(const TStr& MatlabMatrixFNm);
117  void Save(TSOut& SOut) {
118  SOut.Save(RowN); SOut.Save(ColN); RowSpVV.Save(SOut); }
119  void Load(TSIn& SIn) {
120  SIn.Load(RowN); SIn.Load(ColN); RowSpVV = TVec<TIntFltKdV>(SIn); }
121 };
122 
124 // Full-Col-Matrix
125 // matrix is given with columns of full vectors
126 class TFullColMatrix: public TMatrix {
127 public:
128  // number of rows and columns of matrix
129  int RowN, ColN;
130  // vector of sparse columns
132 protected:
133  // Result = A * B(:,ColId)
134  virtual void PMultiply(const TFltVV& B, int ColId, TFltV& Result) const;
135  // Result = A * Vec
136  virtual void PMultiply(const TFltV& Vec, TFltV& Result) const;
137  // Result = A' * B(:,ColId)
138  virtual void PMultiplyT(const TFltVV& B, int ColId, TFltV& Result) const;
139  // Result = A' * Vec
140  virtual void PMultiplyT(const TFltV& Vec, TFltV& Result) const;
141 
142  int PGetRows() const { return RowN; }
143  int PGetCols() const { return ColN; }
144 
145 public:
147  // loads matrix saved in matlab with command:
148  // save -ascii Matrix.dat M
149  TFullColMatrix(const TStr& MatlabMatrixFNm);
150  void Save(TSOut& SOut) { ColV.Save(SOut); }
151  void Load(TSIn& SIn) { ColV.Load(SIn); }
152 };
153 
155 // Basic Linear Algebra Operations
156 class TLinAlg {
157 public:
158  // <x,y>
159  static double DotProduct(const TFltV& x, const TFltV& y);
160  // <X(:,ColIdX), Y(:,ColIdY)>
161  static double DotProduct(const TFltVV& X, int ColIdX, const TFltVV& Y, int ColIdY);
162  // <X(:,ColId), Vec>
163  static double DotProduct(const TFltVV& X, int ColId, const TFltV& Vec);
164  // sparse dot products:
165  // <x,y> where x AND y are sparse
166  static double DotProduct(const TIntFltKdV& x, const TIntFltKdV& y);
167  // <x,y> where only y is sparse
168  static double DotProduct(const TFltV& x, const TIntFltKdV& y);
169  // <X(:,ColId),y> where only y is sparse
170  static double DotProduct(const TFltVV& X, int ColId, const TIntFltKdV& y);
171 
172  // z := p * x + q * y
173  static void LinComb(const double& p, const TFltV& x,
174  const double& q, const TFltV& y, TFltV& z);
175  // z := p * x + (1 - p) * y
176  static void ConvexComb(const double& p, const TFltV& x, const TFltV& y, TFltV& z);
177 
178  // z := k * x + y
179  static void AddVec(const double& k, const TFltV& x, const TFltV& y, TFltV& z);
180  // z := k * x + y
181  static void AddVec(const double& k, const TIntFltKdV& x, const TFltV& y, TFltV& z);
182  // y := k * x + y
183  static void AddVec(const double& k, const TIntFltKdV& x, TFltV& y);
184  // Y(:,Col) += k * X(:,Col)
185  static void AddVec(double k, const TFltVV& X, int ColIdX, TFltVV& Y, int ColIdY);
186  // Result += k * X(:,Col)
187  static void AddVec(double k, const TFltVV& X, int ColId, TFltV& Result);
188  // z = x + y
189  static void AddVec(const TIntFltKdV& x, const TIntFltKdV& y, TIntFltKdV& z);
190 
191  // Result = SUM(x)
192  static double SumVec(const TFltV& x);
193  // Result = SUM(k*x + y)
194  static double SumVec(double k, const TFltV& x, const TFltV& y);
195 
196  // Result = ||x-y||^2 (Euclidian)
197  static double EuclDist2(const TFltV& x, const TFltV& y);
198  static double EuclDist2(const TFltPr& x, const TFltPr& y);
199  // Result = ||x-y|| (Euclidian)
200  static double EuclDist(const TFltV& x, const TFltV& y);
201  static double EuclDist(const TFltPr& x, const TFltPr& y);
202 
203  // ||x||^2 (Euclidian)
204  static double Norm2(const TFltV& x);
205  // ||x|| (Euclidian)
206  static double Norm(const TFltV& x);
207  // x := x / ||x||
208  static void Normalize(TFltV& x);
209 
210  // ||x||^2 (Euclidian), x is sparse
211  static double Norm2(const TIntFltKdV& x);
212  // ||x|| (Euclidian), x is sparse
213  static double Norm(const TIntFltKdV& x);
214  // x := x / ||x||, x is sparse
215  static void Normalize(TIntFltKdV& x);
216 
217  // ||X(:,ColId)||^2 (Euclidian)
218  static double Norm2(const TFltVV& X, int ColId);
219  // ||X(:,ColId)|| (Euclidian)
220  static double Norm(const TFltVV& X, int ColId);
221 
222  // L1 norm of x (Sum[|xi|, i = 1..n])
223  static double NormL1(const TFltV& x);
224  // L1 norm of k*x+y (Sum[|k*xi+yi|, i = 1..n])
225  static double NormL1(double k, const TFltV& x, const TFltV& y);
226  // L1 norm of x (Sum[|xi|, i = 1..n])
227  static double NormL1(const TIntFltKdV& x);
228  // x := x / ||x||_inf
229  static void NormalizeL1(TFltV& x);
230  // x := x / ||x||_inf
231  static void NormalizeL1(TIntFltKdV& x);
232 
233  // Linf norm of x (Max{|xi|, i = 1..n})
234  static double NormLinf(const TFltV& x);
235  // Linf norm of x (Max{|xi|, i = 1..n})
236  static double NormLinf(const TIntFltKdV& x);
237  // x := x / ||x||_inf
238  static void NormalizeLinf(TFltV& x);
239  // x := x / ||x||_inf, , x is sparse
240  static void NormalizeLinf(TIntFltKdV& x);
241 
242  // y := k * x
243  static void MultiplyScalar(const double& k, const TFltV& x, TFltV& y);
244  // y := k * x
245  static void MultiplyScalar(const double& k, const TIntFltKdV& x, TIntFltKdV& y);
246 
247  // y := A * x
248  static void Multiply(const TFltVV& A, const TFltV& x, TFltV& y);
249  // C(:, ColId) := A * x
250  static void Multiply(const TFltVV& A, const TFltV& x, TFltVV& C, int ColId);
251  // y := A * B(:, ColId)
252  static void Multiply(const TFltVV& A, const TFltVV& B, int ColId, TFltV& y);
253  // C(:, ColIdC) := A * B(:, ColIdB)
254  static void Multiply(const TFltVV& A, const TFltVV& B, int ColIdB, TFltVV& C, int ColIdC);
255 
256  // y := A' * x
257  static void MultiplyT(const TFltVV& A, const TFltV& x, TFltV& y);
258 
259  // C = A * B
260  static void Multiply(const TFltVV& A, const TFltVV& B, TFltVV& C);
261 
262  // D = alpha * A(') * B(') + beta * C(')
263  typedef enum { GEMM_NO_T = 0, GEMM_A_T = 1, GEMM_B_T = 2, GEMM_C_T = 4 } TLinAlgGemmTranspose;
264  static void Gemm(const double& Alpha, const TFltVV& A, const TFltVV& B, const double& Beta,
265  const TFltVV& C, TFltVV& D, const int& TransposeFlags);
266 
267  // B = A^(-1)
268  typedef enum { DECOMP_SVD } TLinAlgInverseType;
269  static void Inverse(const TFltVV& A, TFltVV& B, const TLinAlgInverseType& DecompType);
270  // subtypes of finding an inverse
271  static void InverseSVD(const TFltVV& A, TFltVV& B);
272 
273  // transpose matrix - B = A'
274  static void Transpose(const TFltVV& A, TFltVV& B);
275 
276  // performes Gram-Schmidt ortogonalization on elements of Q
277  static void GS(TVec<TFltV>& Q);
278  // Gram-Schmidt on columns of matrix Q
279  static void GS(TFltVV& Q);
280 
281  // rotates vector (OldX,OldY) for angle Angle (in radians!)
282  static void Rotate(const double& OldX, const double& OldY, const double& Angle, double& NewX, double& NewY);
283 
284  // checks if set of vectors is ortogonal
285  static void AssertOrtogonality(const TVec<TFltV>& Vecs, const double& Threshold);
286  static void AssertOrtogonality(const TFltVV& Vecs, const double& Threshold);
287 };
288 
290 // Numerical-Recepies-Exception
291 class TNSException : public TExcept {
292 public:
294 public:
295  TNSException(const TStr& Msg): TExcept(Msg) {}
296 };
297 
299 // Numerical-Linear-Algebra (copied from Numerical Recepies)
301 private:
302  static double sqr(double a);
303  static double sign(double a, double b);
304 
305  // Computes (a^2 + b^2)^(1/2) without
306  // destructive underflow or overflow.
307  static double pythag(double a, double b);
308 
309  //displays error message to screen
310  static void nrerror(const TStr& error_text);
311 
312 public:
313  // Householder reduction of a real, symmetric matrix a[1..n][1..n].
314  // On output, a is replaced by the orthogonal matrix Q e ecting the
315  // transformation. d[1..n] returns the diagonal elements of the
316  // tridiagonal matrix, and e[1..n] the o -diagonal elements, with
317  // e[1]=0. Several statements, as noted in comments, can be omitted
318  // if only eigenvalues are to be found, in which case a contains no
319  // useful information on output. Otherwise they are to be included.
320  static void SymetricToTridiag(TFltVV& a, int n, TFltV& d, TFltV& e);
321 
322  // QL algorithm with implicit shifts, to determine the eigenvalues
323  // and eigenvectors of a real, symmetric, tridiagonal matrix, or of
324  // a real, symmetric matrix previously reduced by tred2 x11.2. On
325  // input, d[1..n] contains the diagonal elements of the tridiagonal
326  // matrix. On output, it returns the eigenvalues. The vector e[1..n]
327  // inputs the subdiagonal elements of the tridiagonal matrix, with
328  // e[1] arbitrary. On output e is destroyed. When finding only the
329  // eigenvalues, several lines may be omitted, as noted in the comments.
330  // If the eigenvectors of a tridiagonal matrix are desired, the matrix
331  // z[1..n][1..n] is input as the identity matrix. If the eigenvectors
332  // of a matrix that has been reduced by tred2 are required, then z is
333  // input as the matrix output by tred2. In either case, the kth column
334  // of z returns the normalized eigenvector corresponding to d[k].
335  static void EigSymmetricTridiag(TFltV& d, TFltV& e, int n, TFltVV& z);
336 
337  // Given a positive-dedinite symmetric matrix A(n,n), this routine
338  // constructs its Cholesky decomposition, A = L * L^T . On input, only
339  // the upper triangle of A need be given; it is not modified. The
340  // Cholesky factor L is returned in the lower triangle of A, except for
341  // its diagonal elements which are returned in p(n).
342  static void CholeskyDecomposition(TFltVV& A, TFltV& p);
343 
344  // Solves the set of n linear equations A * x = b, where A is a
345  // positive-definite symmetric matrix. A(n,n) and p[1..n] are input
346  // as the output of the routine choldc. Only the lower triangle of A
347  // is accessed. b(n) is input as the right-hand side vector. The
348  // solution vector is returned in x(n). A and p are not modified and
349  // can be left in place for successive calls with diferent right-hand
350  // sides b. b is not modified unless you identify b and x in the calling
351  // sequence, which is allowed.
352  static void CholeskySolve(const TFltVV& A, const TFltV& p, const TFltV& b, TFltV& x);
353 
354  // Solves system of linear equations A * x = b, where A is symetric
355  // positive-definite matrix. A is first decomposed using
356  // CholeskyDecomposition and after solved using CholeskySolve. Only
357  // upper triangle of A need be given and it is not modified. However,
358  // lower triangle is modified!
359  static void SolveSymetricSystem(TFltVV& A, const TFltV& b, TFltV& x);
360 
361  // solve system A x_i = e_i for i = 1..n, where A and p are output
362  // from CholeskyDecomposition. Result is stored to upper triangule
363  // (possible since inverse of symetric matrix is also symetric! Sigh...)
364  static void InverseSubstitute(TFltVV& A, const TFltV& p);
365 
366  // Calculates inverse of symetric positiv definit matrix
367  // Matrix is given as upper triangule of A, result is stored
368  // in upper triangule of A. Lower triangule is random (actually
369  // it has part of Choleksy decompositon of A)
370  static void InverseSymetric(TFltVV& A);
371 
372  // calcualtes inverse of upper triagonal matrix A
373  // lower triangle is messed up...
374  static void InverseTriagonal(TFltVV& A);
375 
376  // Given a matrix a[1..n][1..n], this routine replaces it by the LU
377  // decomposition of a rowwise permutation of itself. a and n are input.
378  // a is output, arranged as in equation (2.3.14) above; indx[1..n] is
379  // an output vector that records the row permutation efected by the partial
380  // pivoting; d is output as +-1 depending on whether the number of row
381  // interchanges was even or odd, respectively. This routine is used in
382  // combination with lubksb to solve linear equations or invert a matrix.
383  static void LUDecomposition(TFltVV& A, TIntV& indx, double& d);
384 
385  // Solves the set of n linear equations A*X = B. Here a[1..n][1..n] is input,
386  // not as the matrix A but rather as its LU decomposition, determined by the
387  // routine ludcmp. indx[1..n] is input as the permutation vector returned by
388  // ludcmp. b[1..n] is input as the right-hand side vector B, and returns with
389  // the solution vector X. a, n, and indx are not modified by this routine and
390  // can be left in place for successive calls with diferent right-hand sides b.
391  // This routine takes into account the possibility that b will begin with many
392  // zero elements, so it is efficient for use in matrix inversion.
393  static void LUSolve(const TFltVV& A, const TIntV& indx, TFltV& b);
394 
395  // Solves system of linear equations A * x = b. A is first decomposed using
396  // LUDecomposition and after solved using LUSolve. A is modified!
397  static void SolveLinearSystem(TFltVV& A, const TFltV& b, TFltV& x);
398 };
399 
401 // Sparse-SVD
402 // Calculates singular-value-decompositon for sparse matrixes.
403 // If A is a matrix than A is decomposed to A = U S V'
404 // where S is diagonal with singular values on diagonal and U
405 // and V are ortogonal (U'*U = V'*V = I).
407 class TSparseSVD {
408 private:
409  // Result = Matrix' * Matrix * Vec(:,ColId)
410  static void MultiplyATA(const TMatrix& Matrix,
411  const TFltVV& Vec, int ColId, TFltV& Result);
412  // Result = Matrix' * Matrix * Vec
413  static void MultiplyATA(const TMatrix& Matrix,
414  const TFltV& Vec, TFltV& Result);
415 public:
416  // calculates NumEig eigen values of symetric matrix
417  // if SvdMatrixProductP than matrix Matrix'*Matrix is used
418  static void SimpleLanczos(const TMatrix& Matrix,
419  const int& NumEig, TFltV& EigValV,
420  const bool& DoLocalReortoP = false,
421  const bool& SvdMatrixProductP = false);
422  // fast, calculates NumEig largers eigen values and vectors
423  // kk should be something like 4*NumEig
424  // if SvdMatrixProductP than matrix Matrix'*Matrix is used
425  static void Lanczos(const TMatrix& Matrix,
426  int NumEig, int Iters, const TSpSVDReOrtoType& ReOrtoType,
427  TFltV& EigValV, TFltVV& EigVecVV,
428  const bool& SvdMatrixProductP = false);
429  static void Lanczos2(const TMatrix& Matrix,
430  int MaxNumEig, int MaxSecs, const TSpSVDReOrtoType& ReOrtoType,
431  TFltV& EigValV, TFltVV& EigVecVV,
432  const bool& SvdMatrixProductP = false);
433 
434  // calculates only singular values (based on SimpleLanczos)
435  static void SimpleLanczosSVD(const TMatrix& Matrix,
436  const int& CalcSV, TFltV& SngValV,
437  const bool& DoLocalReortoP = false);
438  // fast, calculates NumSV largers SV (based on Lanczos)
439  static void LanczosSVD(const TMatrix& Matrix,
440  int NumSV, int Iters, const TSpSVDReOrtoType& ReOrtoType,
441  TFltV& SgnValV, TFltVV& LeftSgnVecVV, TFltVV& RightSgnVecVV);
442 
443  // slow - ortogonal iteration
444  static void OrtoIterSVD(const TMatrix& Matrix,
445  int NumSV, int IterN, TFltV& SgnValV);
446 
447  // projects sparse vector to space spanned by columns of matrix U
448  static void Project(const TIntFltKdV& Vec, const TFltVV& U, TFltV& ProjVec);
449 };
450 
452 // Sigmoid -- made by Janez(TM)
453 // (y = 1/[1 + exp[-Ax+B]])
454 class TSigmoid {
455 private:
458 private:
459  // Evaluates how well the sigmoid function fits the data.
460  // J(A, B) = - ln prod_i P(Y = y_i | Z = z_i). The 'data' parameter
461  // should contain (z_i, y_i) pairs. Smaller J means a better fit.
462  static double EvaluateFit(const TFltIntKdV& data, const double A, const double B);
463  // Computes not only J but also its partial derivatives.
464  static void EvaluateFit(const TFltIntKdV& data, const double A,
465  const double B, double& J, double& JA, double& JB);
466  // Let J(lambda) = J(A + lambda U, B + lambda V).
467  // This function computes J and its first and second derivatives.
468  // They can be used to choose a good lambda (using Newton's method)
469  // when minimizing J. -- This method has not been tested yet.
470  static void EvaluateFit(const TFltIntKdV& data, const double A,
471  const double B, const double U, const double V, const double lambda,
472  double& J, double& JJ, double& JJJ);
473 public:
474  TSigmoid() { };
475  TSigmoid(const double& A_, const double& B_): A(A_), B(B_) { };
476  // Tries to find a pair (A, B) that minimizes J(A, B).
477  // Uses gradient descent.
478  TSigmoid(const TFltIntKdV& data);
479 
480  TSigmoid(TSIn& SIn) { A.Load(SIn); B.Load(SIn); }
481  void Load(TSIn& SIn) { A.Load(SIn); B.Load(SIn); }
482  void Save(TSOut& SOut) const {A.Save(SOut); B.Save(SOut);}
483 
484  double GetVal(const double& x) const {
485  return 1.0 / (1.0 + exp(-A * x + B)); }
486  double operator()(const double& x) const {
487  return GetVal(x); }
488 
489  void GetSigmoidAB(double& A_, double& B_) { A_=A; B_=B; }
490 };
491 
493 // Useful stuff (hopefuly)
494 class TLAMisc {
495 public:
496  // Dumps vector to file so Excel can read it
497  static void SaveCsvTFltV(const TFltV& Vec, TSOut& SOut);
498  // Dumps sparse vector to file so Matlab can read it
499  static void SaveMatlabTFltIntKdV(const TIntFltKdV& SpV, const int& ColN, TSOut& SOut);
500  // Dumps vector to file so Matlab can read it
501  static void SaveMatlabTFltV(const TFltV& m, const TStr& FName);
502  // Dumps vector to file so Matlab can read it
503  static void SaveMatlabTIntV(const TIntV& m, const TStr& FName);
504  // Dumps column ColId from m to file so Matlab can read it
505  static void SaveMatlabTFltVVCol(const TFltVV& m, int ColId, const TStr& FName);
506  // Dumps matrix to file so Matlab can read it
507  static void SaveMatlabTFltVV(const TFltVV& m, const TStr& FName);
508  // Dumps main minor rowN x colN to file so Matlab can read it
509  static void SaveMatlabTFltVVMjrSubMtrx(const TFltVV& m, int rowN, int colN, const TStr& FName);
510  // loads matlab full matrix
511  static void LoadMatlabTFltVV(const TStr& FNm, TVec<TFltV>& ColV);
512  // loads matlab full matrix
513  static void LoadMatlabTFltVV(const TStr& FNm, TFltVV& MatrixVV);
514  // prints vector to screen
515  static void PrintTFltV(const TFltV& Vec, const TStr& VecNm);
516  // print matrixt to screen
517  static void PrintTFltVV(const TFltVV& A, const TStr& MatrixNm);
518  // prints vector to screen
519  static void PrintTIntV(const TIntV& Vec, const TStr& VecNm);
520  // fills vector with random numbers
521  static void FillRnd(TFltV& Vec) { TRnd Rnd(0); FillRnd(Vec, Rnd); }
522  static void FillRnd(TFltV& Vec, TRnd& Rnd);
523  // set all components
524  static void Fill(TFltVV& M, const double& Val);
525  // sets all compnents to zero
526  static void FillZero(TFltV& Vec) { Vec.PutAll(0.0); }
527  static void FillZero(TFltVV& M) { Fill(M, 0.0); }
528  // set matrix to identity
529  static void FillIdentity(TFltVV& M);
530  static void FillIdentity(TFltVV& M, const double& Elt);
531  // sums elements in vector
532  static int SumVec(const TIntV& Vec);
533  static double SumVec(const TFltV& Vec);
534  // converts full vector to sparse
535  static void ToSpVec(const TFltV& Vec, TIntFltKdV& SpVec,
536  const double& CutWordWgtSumPrc = 0.0);
537  // converts sparse vector to full
538  static void ToVec(const TIntFltKdV& SpVec, TFltV& Vec, const int& VecLen);
539 };
540 
542 // Template-ised Sparse Operations
543 template <class TKey, class TDat>
544 class TSparseOps {
545 private:
547 public:
548  static void SparseMerge(const TKeyDatV& SrcV1, const TKeyDatV& SrcV2, TKeyDatV& DstV) {
549  DstV.Clr();
550  const int Src1Len = SrcV1.Len();
551  const int Src2Len = SrcV2.Len();
552  int Src1N = 0, Src2N = 0;
553  while (Src1N < Src1Len && Src2N < Src2Len) {
554  if (SrcV1[Src1N].Key < SrcV2[Src2N].Key) {
555  DstV.Add(SrcV1[Src1N]); Src1N++;
556  } else if (SrcV1[Src1N].Key > SrcV2[Src2N].Key) {
557  DstV.Add(SrcV2[Src2N]); Src2N++;
558  } else {
559  DstV.Add(TKeyDat<TKey, TDat>(SrcV1[Src1N].Key, SrcV1[Src1N].Dat + SrcV2[Src2N].Dat));
560  Src1N++; Src2N++;
561  }
562  }
563  while (Src1N < Src1Len) { DstV.Add(SrcV1[Src1N]); Src1N++; }
564  while (Src2N < Src2Len) { DstV.Add(SrcV2[Src2N]); Src2N++; }
565  }
566 };
567 
Definition: ds.h:346
TNSException(const TStr &Msg)
Definition: linalg.h:295
static double EuclDist(const TFltV &x, const TFltV &y)
Definition: linalg.cpp:312
double GetVal(const double &x) const
Definition: linalg.h:484
static void Transpose(const TFltVV &A, TFltVV &B)
Definition: linalg.cpp:539
int PGetCols() const
Definition: linalg.h:107
TSpSVDReOrtoType
Definition: linalg.h:406
TStr Message
Definition: linalg.h:293
TVec< TKeyDat< TKey, TDat > > TKeyDatV
Definition: linalg.h:546
static double Norm(const TFltV &x)
Definition: linalg.cpp:324
TSparseOps< TInt, TFlt > TSparseOpsIntFlt
Definition: linalg.h:568
int PGetRows() const
Definition: linalg.h:106
int PGetCols() const
Definition: linalg.h:143
virtual int PGetCols() const =0
static void AssertOrtogonality(const TVec< TFltV > &Vecs, const double &Threshold)
Definition: linalg.cpp:616
static void SaveMatlabTFltIntKdV(const TIntFltKdV &SpV, const int &ColN, TSOut &SOut)
Definition: linalg.cpp:1605
void Transpose()
Definition: linalg.h:49
TLinAlgInverseType
Definition: linalg.h:268
void Save(TSOut &SOut)
Definition: linalg.h:117
Definition: dt.h:11
static double SumVec(const TFltV &x)
Definition: linalg.cpp:279
static double sqr(double a)
Definition: linalg.cpp:647
static double EvaluateFit(const TFltIntKdV &data, const double A, const double B)
Definition: linalg.cpp:1490
virtual void PMultiplyT(const TFltVV &B, int ColId, TFltV &Result) const
Definition: linalg.cpp:27
static void GS(TVec< TFltV > &Q)
Definition: linalg.cpp:584
static void FillRnd(TFltV &Vec)
Definition: linalg.h:521
void MultiplyT(const TFltVV &B, int ColId, TFltV &Result) const
Definition: linalg.h:34
static void Lanczos(const TMatrix &Matrix, int NumEig, int Iters, const TSpSVDReOrtoType &ReOrtoType, TFltV &EigValV, TFltVV &EigVecVV, const bool &SvdMatrixProductP=false)
Definition: linalg.cpp:1134
static void ToVec(const TIntFltKdV &SpVec, TFltV &Vec, const int &VecLen)
Definition: linalg.cpp:1805
static void SimpleLanczosSVD(const TMatrix &Matrix, const int &CalcSV, TFltV &SngValV, const bool &DoLocalReortoP=false)
Definition: linalg.cpp:1440
int PGetRows() const
Definition: linalg.h:142
void Save(TSOut &SOut) const
Definition: linalg.h:482
TVec< TIntFltKdV > RowSpVV
Definition: linalg.h:95
static void Lanczos2(const TMatrix &Matrix, int MaxNumEig, int MaxSecs, const TSpSVDReOrtoType &ReOrtoType, TFltV &EigValV, TFltVV &EigVecVV, const bool &SvdMatrixProductP=false)
Definition: linalg.cpp:1290
static void SaveMatlabTFltVV(const TFltVV &m, const TStr &FName)
Definition: linalg.cpp:1643
void Load(TSIn &SIn)
Definition: linalg.h:83
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TLinAlgGemmTranspose
Definition: linalg.h:263
TSparseColMatrix(TVec< TIntFltKdV > _ColSpVV)
Definition: linalg.h:76
void Save(TSOut &SOut)
Definition: linalg.h:81
TFlt A
Definition: linalg.h:456
static void SolveLinearSystem(TFltVV &A, const TFltV &b, TFltV &x)
Definition: linalg.cpp:994
static void FillZero(TFltV &Vec)
Definition: linalg.h:526
static void SaveMatlabTFltVVCol(const TFltVV &m, int ColId, const TStr &FName)
Definition: linalg.cpp:1632
TSparseColMatrix(TVec< TIntFltKdV > _ColSpVV, const int &_RowN, const int &_ColN)
Definition: linalg.h:77
static void LanczosSVD(const TMatrix &Matrix, int NumSV, int Iters, const TSpSVDReOrtoType &ReOrtoType, TFltV &SgnValV, TFltVV &LeftSgnVecVV, TFltVV &RightSgnVecVV)
Definition: linalg.cpp:1454
void Load(TSIn &SIn)
Definition: ds.h:946
void Load(TSIn &SIn)
Definition: linalg.h:481
static void MultiplyT(const TFltVV &A, const TFltV &x, TFltV &y)
Definition: linalg.cpp:468
static void InverseSVD(const TFltVV &A, TFltVV &B)
Definition: linalg.cpp:555
static void InverseTriagonal(TFltVV &A)
Definition: linalg.cpp:881
Definition: dt.h:1386
Definition: fl.h:58
void Save(TSOut &SOut) const
Definition: ds.h:954
static void Normalize(TFltV &x)
Definition: linalg.cpp:328
static void NormalizeLinf(TFltV &x)
Definition: linalg.cpp:404
static void Project(const TIntFltKdV &Vec, const TFltVV &U, TFltV &ProjVec)
Definition: linalg.cpp:1476
virtual int PGetRows() const =0
TSparseRowMatrix(TVec< TIntFltKdV > _RowSpVV)
Definition: linalg.h:111
static void SaveMatlabTFltVVMjrSubMtrx(const TFltVV &m, int rowN, int colN, const TStr &FName)
Definition: linalg.cpp:1657
static void SparseMerge(const TKeyDatV &SrcV1, const TKeyDatV &SrcV2, TKeyDatV &DstV)
Definition: linalg.h:548
TFullColMatrix()
Definition: linalg.h:146
static int SumVec(const TIntV &Vec)
Definition: linalg.cpp:1769
static void Rotate(const double &OldX, const double &OldY, const double &Angle, double &NewX, double &NewY)
Definition: linalg.cpp:611
static void MultiplyScalar(const double &k, const TFltV &x, TFltV &y)
Definition: linalg.cpp:414
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
static void NormalizeL1(TFltV &x)
Definition: linalg.cpp:380
virtual void PMultiplyT(const TFltVV &B, int ColId, TFltV &Result) const =0
double operator()(const double &x) const
Definition: linalg.h:486
static void LUSolve(const TFltVV &A, const TIntV &indx, TFltV &b)
Definition: linalg.cpp:974
static double Norm2(const TFltV &x)
Definition: linalg.cpp:320
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1229
int GetRows() const
Definition: linalg.h:45
static void CholeskyDecomposition(TFltVV &A, TFltV &p)
Definition: linalg.cpp:797
void Load(bool &Bool)
Definition: fl.h:84
static double NormLinf(const TFltV &x)
Definition: linalg.cpp:390
static void AddVec(const double &k, const TFltV &x, const TFltV &y, TFltV &z)
Definition: linalg.cpp:232
int PGetRows() const
Definition: linalg.h:71
virtual void PMultiply(const TFltVV &B, int ColId, TFltV &Result) const
Definition: linalg.cpp:101
TSigmoid()
Definition: linalg.h:474
static void PrintTIntV(const TIntV &Vec, const TStr &VecNm)
Definition: linalg.cpp:1735
int GetCols() const
Definition: linalg.h:47
void GetSigmoidAB(double &A_, double &B_)
Definition: linalg.h:489
static void nrerror(const TStr &error_text)
Definition: linalg.cpp:655
void Load(TSIn &SIn)
Definition: linalg.h:119
static void EigSymmetricTridiag(TFltV &d, TFltV &e, int n, TFltVV &z)
Definition: linalg.cpp:740
TVec< TIntFltKdV > ColSpVV
Definition: linalg.h:60
static void PrintTFltVV(const TFltVV &A, const TStr &MatrixNm)
Definition: linalg.cpp:1724
static void SolveSymetricSystem(TFltVV &A, const TFltV &b, TFltV &x)
Definition: linalg.cpp:837
static void FillZero(TFltVV &M)
Definition: linalg.h:527
void Load(TSIn &SIn)
Definition: linalg.h:151
bool Transposed
Definition: linalg.h:10
Definition: fl.h:128
static void Fill(TFltVV &M, const double &Val)
static void SaveMatlabTIntV(const TIntV &m, const TStr &FName)
Definition: linalg.cpp:1622
virtual void PMultiply(const TFltVV &B, int ColId, TFltV &Result) const
Definition: linalg.cpp:3
Definition: linalg.h:8
void Save(const bool &Bool)
Definition: fl.h:173
static void Multiply(const TFltVV &A, const TFltV &x, TFltV &y)
Definition: linalg.cpp:428
TSigmoid(TSIn &SIn)
Definition: linalg.h:480
static void SymetricToTridiag(TFltVV &a, int n, TFltV &d, TFltV &e)
Definition: linalg.cpp:668
static void CholeskySolve(const TFltVV &A, const TFltV &p, const TFltV &b, TFltV &x)
Definition: linalg.cpp:815
static void SimpleLanczos(const TMatrix &Matrix, const int &NumEig, TFltV &EigValV, const bool &DoLocalReortoP=false, const bool &SvdMatrixProductP=false)
Definition: linalg.cpp:1053
void Multiply(const TFltVV &B, int ColId, TFltV &Result) const
Definition: linalg.h:24
Definition: ut.h:161
TVec< TFltV > ColV
Definition: linalg.h:131
static double NormL1(const TFltV &x)
Definition: linalg.cpp:357
static void LoadMatlabTFltVV(const TStr &FNm, TVec< TFltV > &ColV)
Definition: linalg.cpp:1670
virtual void PMultiplyT(const TFltVV &B, int ColId, TFltV &Result) const
Definition: linalg.cpp:79
void Multiply(const TFltV &Vec, TFltV &Result) const
Definition: linalg.h:29
static void SaveCsvTFltV(const TFltV &Vec, TSOut &SOut)
Definition: linalg.cpp:1598
static double pythag(double a, double b)
Definition: linalg.cpp:660
Definition: dt.h:412
TFlt B
Definition: linalg.h:457
static void SaveMatlabTFltV(const TFltV &m, const TStr &FName)
Definition: linalg.cpp:1612
static void FillIdentity(TFltVV &M)
Definition: linalg.cpp:1751
TSparseRowMatrix(TVec< TIntFltKdV > _RowSpVV, const int &_RowN, const int &_ColN)
Definition: linalg.h:112
void Load(TSIn &SIn)
Definition: dt.h:1405
static void LUDecomposition(TFltVV &A, TIntV &indx, double &d)
Definition: linalg.cpp:909
virtual void PMultiply(const TFltVV &B, int ColId, TFltV &Result) const
Definition: linalg.cpp:147
static double DotProduct(const TFltV &x, const TFltV &y)
Definition: linalg.cpp:165
TSigmoid(const double &A_, const double &B_)
Definition: linalg.h:475
static void InverseSubstitute(TFltVV &A, const TFltV &p)
Definition: linalg.cpp:843
void Save(TSOut &SOut)
Definition: linalg.h:150
virtual ~TMatrix()
Definition: linalg.h:21
static void Inverse(const TFltVV &A, TFltVV &B, const TLinAlgInverseType &DecompType)
Definition: linalg.cpp:548
static void ToSpVec(const TFltV &Vec, TIntFltKdV &SpVec, const double &CutWordWgtSumPrc=0.0)
Definition: linalg.cpp:1785
static void OrtoIterSVD(const TMatrix &Matrix, int NumSV, int IterN, TFltV &SgnValV)
Definition: linalg.cpp:1021
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TMatrix()
Definition: linalg.h:20
static void Gemm(const double &Alpha, const TFltVV &A, const TFltVV &B, const double &Beta, const TFltVV &C, TFltVV &D, const int &TransposeFlags)
Definition: linalg.cpp:493
static void LinComb(const double &p, const TFltV &x, const double &q, const TFltV &y, TFltV &z)
Definition: linalg.cpp:218
static void ConvexComb(const double &p, const TFltV &x, const TFltV &y, TFltV &z)
Definition: linalg.cpp:227
void MultiplyT(const TFltV &Vec, TFltV &Result) const
Definition: linalg.h:39
static void InverseSymetric(TFltVV &A)
Definition: linalg.cpp:872
int PGetCols() const
Definition: linalg.h:72
void Save(TSOut &SOut) const
Definition: dt.h:1402
static void PrintTFltV(const TFltV &Vec, const TStr &VecNm)
Definition: linalg.cpp:1714
virtual void PMultiplyT(const TFltVV &B, int ColId, TFltV &Result) const
Definition: linalg.cpp:133
static void MultiplyATA(const TMatrix &Matrix, const TFltVV &Vec, int ColId, TFltV &Result)
Definition: linalg.cpp:1003
static double EuclDist2(const TFltV &x, const TFltV &y)
Definition: linalg.cpp:298
virtual void PMultiply(const TFltVV &B, int ColId, TFltV &Result) const =0
static double sign(double a, double b)
Definition: linalg.cpp:651
TSparseColMatrix()
Definition: linalg.h:75