GeoMetric Embedding Kit 1.0 FAQ

This FAQ is divided as follows
  1. Installation & Compilation
  2. Numerical Method

Installation & Compilation

  1. Q: I'm getting Internal compiler error when building the project c:\big bang code\topaggr\tgeoapprox\gexpoint.h(27) : fatal error C1001: INTERNAL COMPILER ERROR (compiler file 'msc1.cpp', line 1786) Please choose the Technical Support command on the Visual C++ Help menu, or open the Technical Support help file for more information
    A: You don't have VS6sp3 or later installed. Check http://support.microsoft.com/default.aspx?scid=kb;EN-US;194295 which service pack is installed on yours see If you don't have VC6 service pack installed Install VS6SP3: http://support.microsoft.com/support/kb/articles/q192/5/39.asp
  2. Q: I'd like to set breakpoints in one of the solver dlls, e.g. GdhSimplexd.dll,
    A: At the debug tab in project settings of the TGeoApprox program, switch to the category of additional dlls and add GdhSimplexd.dll.
  3. Q: Can I mix debug and release versions of TGeoApprox.exe, GeometricApprox.dll and other solver dlls?
    A: Mixing of the debug and release exe/dlls in the same run is NOT supported. This is due to problem with the static data of the PointN template. The debug dlls all have 'd' suffix. For example don't load GdhSimplexd.dll, from the release TGeoApprox program, and don't load release GdhSimplex.dll from debug TGeoApprox.

Numerical Method

  1. Q: The BBS algorithm has 4 phases, while in each phase a different potential energy function is used. How did you decide when a phase should terminate? Does a phase terminate when the solution---node positions in the Euclidean space---doesn't change any more, or does it terminate before that? If the latter case is true, then does the phase end after a fixed number of iterations, or does it use any other criterion?
    A: The criteria for stopping a calculation phase are identical in all four phases. However the thresholds used are different in the first phase, in which the embedding error is unormalized, vs. normalized in rest phases 2-4: 1. max. particle velocity below threshold This situation usually happens if the acheaved embedding is considerably better then its neighborhood, i.e. a deep optimum. 2. max. distortion below 1+threshold, if a nearly exact solution is found. This situation happens only for simulated metric. 3. slow decrease rate or small oscillations in embedding error 4. diverging solution (too high max. velocity or embedding error) Some iterations are always performed in the beginning of each phase to prevent premature quitting. Only after physical system's time reaches a fixed value, e.g. 10 seconds, the testing of stop conditions 3 and 4 is commenced.
  2. Q: At the beginning of the first iteration of the first phase, all nodes are assumed to be 'on the same point'. What do you do in the first iteration of the first phase?
    A: This part is described in section 2.2(see eq. 10 there) of the full paper, currently being reviewed for a journal. [1] is an earlier version of it.
  3. Q: The use of both friction coefficients: - what are the suitable value of coefficients and what are the link between both coefficients and weights of the edges and number of nodes in the graph?
    A: Regarding the first part of the question: As demonstrated in fig. 3 of the BBS paper any value between 0.003 and 3 will work equally well. Decreasing the coefficient too much (e.g. .0001) we'll cause longer running time but should have no effect on final distortion. Regarding the second part: This is documented on the tech report, but omitting the values of adjust factor used which were: adjustFactor(eq. 13)=7500 normalizedAdjustFactor(eq. 14)=100
  4. Q: Incremental of time step in each iteration: - what do you mean by "...keeping it small to detect and attract particles to global minimum points of the potential energy function"?
    A: When simulation time step is too coarse it will skip over the minima attractors.
  5. Q: When a calculation of a phase ends: - You mentioned 4 types of threshold to decide when a phrase should end but how do we decide what the threshold are?
    A: I tuned the thresholds of velocity and convergance rate by simple manual process which decrease the threshold value until the accuracy cease to improve.
  6. Q: Initial position of particles in phase 2, 3 and 4: - What do you mean in "... at t=0, all particles are at rest at the point where the potential energy achieved its global minimum along the particles trajectories of the previous phase"?
    A: Whenever the particles acheave new minimum value of the potential function (=embedding error) I store their position. At the end of each phase I pick the stored position of this acheaved minimum.
  7. Q: Derivation of the induced forces for phase 2, 3 and 4.
    A: Hopefully following two answers are consitent with each other:-)
    1. This derivation is included in appendix of the full paper, currently being reviewed for a journal. [1] is an earlier version of it.
    2. The function calcElementDerivativeByDistDividedByDist(pairDist,inpPairMetric) in C source file phase_derivative.cpp calculates the quotient F_ij/|v_ij|. To obtain the force F_i you should multiply the returned derivative by the vector connecting points i and j and some over all j\neq i. The different switch cases correspond to different calculation phases.

    References

    [1] Yuval Shavitt and Tomer Tankel
    Big-Bang Simulation for embedding network distances in Euclidean space. IEEE/ACM Trans. on Networking, accepted for publication, 2004
    Last updated 2003/11/8
    This material is based upon work supported by a grant from the United States Israel Binational Science Foundation (BSF), Jerusalem, Israel. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.