SNAP Library 4.0, Developer Reference  2017-07-27 13:18:06
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
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 
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:
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
virtual void PMultiplyT(const TFltVV &B, int ColId, TFltV &Result) const =0
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
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
virtual int PGetRows() const =0
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
virtual void PMultiply(const TFltVV &B, int ColId, TFltV &Result) const =0
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: linalg.h:481
static void MultiplyT(const TFltVV &A, const TFltV &x, TFltV &y)
Definition: linalg.cpp:468
virtual int PGetCols() const =0
static void InverseSVD(const TFltVV &A, TFltVV &B)
Definition: linalg.cpp:555
static void InverseTriagonal(TFltVV &A)
Definition: linalg.cpp:881
Definition: dt.h:1383
Definition: fl.h:58
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
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
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:1402
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:1399
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
static double sign(double a, double b)
Definition: linalg.cpp:651
TSparseColMatrix()
Definition: linalg.h:75