Eigenvalues problems in Sage (Cvetkovic bound example)

[math1um]

The Cvetkovic bound of a graph is the minimum of the number of non-negative and non-positive eigenvalues.

Here we compute the eigenvalues and count. But this is extremely sensitive to numerical precision errors. While an error of 10^-16 is in most cases irrelevant, it may change the sign of an eigenvalue from positive to negative (or in the cases we see, between 0 and negative).

In Sage there is more than one way to calculate graph eigenvalues. They can be computed exactly over QQ. This is (sometimes much much) slower than computing over the real field RDF. In some cases speed is preferred and others precision is required.

If you need a graph eigenvalue that's exactly 0 (and not 4*10^{-16}) you need to compute over QQ - or your counts of non-negative and non-positive will be wrong.

Here's an example:

house = graphs.HouseGraph() house.adjacency_matrix().eigenvalues() #this uses QQ

[0, -2, -1.170086486626034?, 0.6888921825340181?, 2.481194304092016?]

M=Matrix(RDF,house.adjacency_matrix()) M.eigenvalues(algorithm="symmetric")

[-2.0000000000000004, -1.1700864866260334, -3.834726932609466e-16, 0.6888921825340177, 2.481194304092016]

For many purposes the 2nd list is fine. For some its not?

How should these issues be handled in general?

[yirkajk]

It sounds like we should use Graph.spectrum(), which calls Graph.adjacency_matrix().eigenvalues() on any methods which need exact eigenvalues. We could do some other work first to check if it could even matter, and so is worth the additional time.

Otherwise, for functions like max_eigenvalue, we can stick with g.adjacency_matrix().change_ring(RDF).eigenvalues(), which uses much faster methods over the reals.

The one concern I still have applies to all invariants, not just eigenvalues. This matters in two parts: precomputed values, and conjecturing. This may be best as another issue.

• First, we need to have some standard for numerical precision in our precomputed values so people know what they're getting.
  • I would suggest storing everything as rational when possible, but since the conjecturing program is in C, everything eventually becomes a float, so I don't think this helps much.
• Second, is there any way to avoid the conjecturing program making bad/missing good conjectures due to a precision error? For example, it won't conjecture X >= Y if there's one instance where X=2 and Y=2.00000..001.

[a234]

Maybe we can compute the eigenvalues with 16-digit precision, and round them off to 6-digit precision. 6-digit precision are enough for discriminating eigenvalues of small graphs, and such an approach would never miss any case to conjecture X>=Y when X and Y are two theoretically equal eigenvalues of small graphs.

[nvcleemp]

A 6-digit precision might not be enough. A conjecture might contain an expression involving this eigenvalue, and as soon as you multiply by, e.g., the order cubed, the imprecisions might blow up quit fast. But actually this is true for any imprecision. Implementing the conjecturing part in Sage or using exact representations in the conjecturing part are also not feasible, since this would slow things down to an unusable speed for anything but small sets of objects and invariants.