SourceForge Logo
Public Implementation of a Graph Algorithm
Library and Editor

H. de Fraysseix      P. Ossona de Mendez

Diagonalise.cpp File Reference

Detailed Description

Computation of the eigenspaces of a metric and of the embedding of a set of points.

Include dependency graph for Diagonalise.cpp:



Function Documentation

void CalcNorm ( double  p,
double  q,
double &  norm,
double &  c,
double &  s 
) [static]

Computes $ {\rm norm}=\sqrt{{\rm p}^2+{\rm q}^2}, {\rm c}=\frac{\rm p}{\rm norm},{\rm s}=\frac{\rm q}{\rm norm}$.

int ComputeBilinearForm ( double **  dis,
int  ni 
) [static]

Computes the bilinear form to be put in diagonal form from the distance matrix dis.

Computes the bilinear form:

\[ {\rm dis}\leftarrow -\frac{1}{2}\left(I-\frac{J}{\rm ni}\right){\rm dis}\left(I-\frac{J}{\rm ni}\right) \]

from the developped formula:

\[ {\rm dis}_{i,j}\leftarrow -\frac{1}{2}\left( {\rm dis}_{i,j}-\frac{1}{\rm ni}\sum_{\alpha=1}^{\rm ni} {\rm dis}_{i,\alpha} -\frac{1}{\rm ni}\sum_{\alpha=1}^{\rm ni} {\rm dis}_{\alpha,j} +\frac{1}{{\rm ni}^2}\sum_{\alpha=1}^{\rm ni}\sum_{\beta=1}^{\rm ni}{\rm dis}_{\alpha,\beta}\right)\]

int diag ( double **  dis,
int  NumberOfPoints,
double **  Distances,
svector< double > &  EigenValues,
bool  project 

Isometrically embed a set of points with given distances among them in the Euclidean space $\mathbb{R}^n$.

dis coordinates of the points (returned value)
NumberOfPoints number of points > 2
Distances distances among the points
EigenValues eigenvalues of dis (returned value)
project indicates if one should project the matrix of distances before putting it in diagonal form (always true except when using the Laplacian)
  • copies the Distances matrix into the dis matrix,
  • call ComputeBilinearForm() to compute the projection matrix dis to be put in diagonal form
  • compute the trace of dis
  • call symqr() to compute the spectrum of dis
  • normalise the coordinates
  • compute the multiplicities of the eigenvalues and print some useful information.
See also:
ComputeBilinearForm() and symqr()

int symqr ( double **  dis,
int  ni,
int  nf,
double &  trace,
svector< double > &  EigenValues 
) [static]

Computes the eigenvalues of the ni $ \times $ ni matrix dis.

Variable Documentation

const double epsilon = 1.E-12

rounding precision

Generated on Thu Jan 31 16:50:54 2008 for Pigale by  doxygen 1.5.4