#20228: Spectral radius of graphs
-------------------------------------+-------------------------------------
Reporter: vdelecroix | Owner:
Type: enhancement | Status: needs_info
Priority: major | Milestone: sage-7.1
Component: graph theory | Resolution:
Keywords: days71 | Merged in:
Authors: Vincent Delecroix | Reviewers: Maurizio Monge
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/vdelecroix/20228 | dd2dd58d732460eeb713112306a02d37a6750db9
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by vdelecroix):
Hello Maurizio,
Thanks for having a look!
Interval arithmetic does not use machine floating point but
[http://www.mpfr.org/ mpfr]. It would be much slower than the version I
wrote. This would only be a constant time slower which on my computer
seems to be a factor `x8`. The intended application of this method is for
huge sparse graphs (let say with `~1000000` vertices). A `x8` speedup is
far from being negligible. Similarly, I could have used ball arithmetic
[http://fredrikj.net/arb/ arb] which is also shipped with Sage (and should
be faster than interval arithmetic). Moreover, it is a certain amount of
work to write `matrix/vector` code using either `mpir` or `arb`. Using
`mpir` or `arb` would also decrease readability since multiplying numbers
with `mpfr` is done via `mpfr_mul(x, a, b, prec)` which is much less
readable than `x = a*b`. Though the approach using either mpir or arb
would have the advantage of making available higher precision. This would
indeed be interesting for small graphs.
On the other hand, the function I made is written in C. It is not
reasonable to use the Cython wrapper we have in Sage as
allocating/deallocating million of Python classes is expensive.
The only thing that can easily be done would be to return an element in
`RIF` instead of a tuple of Python float.
What I wrote is not the "best and fastest algorithm" to get the Perron-
Frobenius eigenvalue. For example, it suffers from slow convergence in
absence of spectral gap. But it was very helpful to me and might as well
be helpful for others. I consider than having an arbitrary precision
version using `mpfr`, `mpir` or `arb` would be good for another ticket. It
will need some care because you want to increase slowly the precision (it
makes no sense to use the full precision on the first iterations).
Moreover, it is not immediate to determine what is the precision needed
for the computation to obtain a given precision for the answer.
I need to fix a mistake (the condition in the loop should be `(e_max -
e_min) > e_max * c_prec` instead of `e_max * (e_max - e_min) > c_prec`). I
would also like to move the `sage_free` inside the `finally` block (to
avoid unfreed memory). I am waiting for your comments before submitting
the commit.
--
Ticket URL: <http://trac.sagemath.org/ticket/20228#comment:4>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
