Precomputing invariant errors and problems

[yirkajk]

precomputeScript.sage.py:935: UserWarning: Using generic algorithm for an inexact ring, which will probably give incorrect results due to numerical precision issues.
Error while computing min_eigenvalue for basic facet-graph two
<type 'exceptions.TypeError'>precomputeScript.sage.py:101: DeprecationWarning: BaseException.message has been deprecated as of Python 2.6
 unable to convert -2.000000000000001 - 9.224476260997897e-17*I to float; use abs() or real_part() as desired
Computation of min_eigenvalue for basic facet-graph two failed!
Error while computing min_eigenvalue for distreg_not_stronglyreg9
<type 'exceptions.TypeError'> unable to convert -1.0000000000000007 - 2.4095362866619107e-24*I to float; use abs() or real_part() as desired
Computation of min_eigenvalue for distreg_not_stronglyreg9 failed!
Error while computing min_eigenvalue for K03K04
<type 'exceptions.TypeError'> unable to convert -2.0000000000000004 - 7.021666937153402e-16*I to float; use abs() or real_part() as desired
Computation of min_eigenvalue for K03K04 failed!
Error while computing min_eigenvalue for K07K14
<type 'exceptions.TypeError'> unable to convert -2.000000000000004 - 2.608433496858071e-15*I to float; use abs() or real_part() as desired
Computation of min_eigenvalue for K07K14 failed!
Error while computing min_eigenvalue for K07K09
<type 'exceptions.TypeError'> unable to convert -2.0000000000000027 - 7.357524036154378e-16*I to float; use abs() or real_part() as desired
Computation of min_eigenvalue for K07K09 failed!
Error while computing min_eigenvalue for K05K20
<type 'exceptions.TypeError'> unable to convert -2.000000000000006 - 1.9984014443252818e-15*I to float; use abs() or real_part() as desired
Computation of min_eigenvalue for K05K20 failed!

The numerical precision warning occurred with both max_eigenvalue and min_eigenvalue.

The errors involving complex numbers only occurred with min_eigenvalue.

So, need to resolve the errors. And, do we need to recompute the values, since they might be wrong?

[math1um]

It would be useful to have an independent eigenvalue algorithm implementation to check our eigenvaue computations.

These matrices are all symmetric - that they are throwing complex eigenvalues is a mistake.

[yirkajk]

A similar numerical precision warning was given for laplacian_energy And gutman_energy

[yirkajk]

laplacian_energy_like has a totally different problem: It times out on almost every graph.

One thing we notice: This method calls the g.spectrum() method. Why does every method dealing with eigenvalues not call this built-in method?

[math1um]

Sage uses a completely different algorithm for computing matrix eigenvalues than the algorithm implemented for graph adjacency matrices (which seems to factor the characteristic polynomial).

These algorithms can easily (and should) definitely be compared for the graphs in GT

[yirkajk]

Also with numerical precision warnings: largest_eigenvalue_minus_avg_degree. And that's it for efficient invariants.

[nvcleemp]

The complex values come from numerical rounding errors as is also mentioned in the user warning. We should see if the user warning originates in our code, or in Sage code. In the latter case we should report a bug with Sage.

[yirkajk]

Just summarising the invariants to be fixed and values to be checked:

• [ ] max_eigenvalue
• [ ] min_eigenvalue
• [ ] largest_eigenvalue_minus_avg_degree
• [ ] laplacian_energy
• [ ] gutman_energy
• [ ] wilf

I'm going to begin by considering why we don't use g.spectrum() in all of these. Perhaps the reason is related to why laplacian_energy_like times out so often.

[yirkajk]

Okay, I fixed the functions by passing argument=symmetric as a parameter to eigenvalues(), forcing it to use an algorithm just for real eigenvalues. I will go back and recompute the values for all graphs for these functions, in case the numerical precision was a problem.

[yirkajk]

Values have been recomputed. The issue should be automatically closed when the precomputing branch is merged into master.