tight complex interval inverse #19964
Description
The current method to compute the multiplicative inverse of a complex interval uses schoolbok formula that produces intervals much bigger than the actual result.
This ticket implements a method that produces a tight interval enclosure of the result.
As a result, we get better precission in root isolating methods (and hence, less steps needed).
Here are some examples that illustrate the impact of the changes:
Old behaviour:
sage: a = CIF((1, 2), (3, 4))
sage: a.real().lower(), a.real().upper()
(1.00000000000000, 2.00000000000000)
sage: a = CIF((1, 2), (3, 4))
sage: b = a.__invert__()
sage: b.real().lower(), b.real().upper()
(0.0499999999999999, 0.200000000000001)
sage: b.imag().lower(), b.imag().upper()
(-0.400000000000001, -0.149999999999999)
sage: b.diameter()
1.20000000000000
sage: %time a.__invert__()
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 23.1 µs
1.? - 1.?*I
new behaviour:
sage: a = CIF((1, 2), (3, 4))
sage: a.real().lower(), a.real().upper()
(1.00000000000000, 2.00000000000000)
sage: b = a.__invert__()
sage: b.real().lower(), b.real().upper()
(0.0588235294117647, 0.153846153846154)
sage: b.imag().lower(), b.imag().upper()
(-0.300000000000001, -0.200000000000000)
sage: b.diameter()
0.893617021276596
sage: %time a.__invert__()
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 19.1 µs
0.1? - 0.3?*I
Another example with a smaller interval,
old:
sage: a = CIF((5, 5.01), (7, 7.01))
sage: b = a.__invert__()
sage: b.diameter()
0.00523867991752868
sage: b.real().lower(), b.real().upper()
(0.0673489564952680, 0.0677027027027028)
sage: b.imag().lower(), b.imag().upper()
(-0.0947297297297298, -0.0942885390933752)
sage: %time a.__invert__()
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 23.1 µs
-0.068? - 0.095?*I
new:
sage: a = CIF((5, 5.01), (7, 7.01))
sage: b = a.__invert__()
sage: b.diameter()
0.00253766599329326
sage: b.real().lower(), b.real().upper()
(0.0674398874563158, 0.0676112447891434)
sage: b.imag().lower(), b.imag().upper()
(-0.0945945945945946, -0.0944232370063658)
sage: a = CIF((-5.01, -5), (7, 7.01))
sage: %time a.__invert__()
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 49.1 µs
-0.068? - 0.0945?*I
As you can see, the diameter of the result can easily get cut to half or even smaller.
The timings of the inversion can vary, but they remain in the same order of magnitude as before. It has a noticeable effect in root isolation:
old:
sage: R.<x> = QQ[]
sage: f = -7/6*x^7 - x^6 + 1/2*x^4 + 2/17*x^3 + 2*x^2 - 6*x - 9
sage: %time f.roots(CC)
CPU times: user 6 ms, sys: 0 ns, total: 6 ms
Wall time: 5.34 ms
[(-1.03157268729039, 1),
(-1.18964736821330 - 0.850802715570186*I, 1),
(-1.18964736821330 + 0.850802715570186*I, 1),
(0.0780792982605128 - 1.39288589462175*I, 1),
(0.0780792982605128 + 1.39288589462175*I, 1),
(1.19878298502655 - 0.599304323571307*I, 1),
(1.19878298502655 + 0.599304323571307*I, 1)]
sage: %time f.roots(QQbar)
CPU times: user 17 ms, sys: 0 ns, total: 17 ms
Wall time: 15.7 ms
[(-1.031572687290387?, 1),
(-1.189647368213303? - 0.8508027155701860?*I, 1),
(-1.189647368213303? + 0.8508027155701860?*I, 1),
(0.07807929826051275? - 1.392885894621755?*I, 1),
(0.07807929826051275? + 1.392885894621755?*I, 1),
(1.198782985026555? - 0.5993043235713073?*I, 1),
(1.198782985026555? + 0.5993043235713073?*I, 1)]
new:
sage: R.<x>=QQ[]
sage: f = -7/6*x^7 - x^6 + 1/2*x^4 + 2/17*x^3 + 2*x^2 - 6*x - 9
sage: %time f.roots(CC)
CPU times: user 4 ms, sys: 0 ns, total: 4 ms
Wall time: 3.28 ms
[(-1.03157268729039, 1),
(-1.18964736821330 - 0.850802715570186*I, 1),
(-1.18964736821330 + 0.850802715570186*I, 1),
(0.0780792982605128 - 1.39288589462175*I, 1),
(0.0780792982605128 + 1.39288589462175*I, 1),
(1.19878298502655 - 0.599304323571307*I, 1),
(1.19878298502655 + 0.599304323571307*I, 1)]
sage: %time f.roots(QQbar)
CPU times: user 9 ms, sys: 1 ms, total: 10 ms
Wall time: 9.3 ms
[(-1.031572687290387?, 1),
(-1.189647368213303? - 0.8508027155701860?*I, 1),
(-1.189647368213303? + 0.8508027155701860?*I, 1),
(0.07807929826051275? - 1.392885894621755?*I, 1),
(0.07807929826051275? + 1.392885894621755?*I, 1),
(1.198782985026555? - 0.5993043235713073?*I, 1),
(1.198782985026555? + 0.5993043235713073?*I, 1)]
CC: @tscrim @videlec @dkrenn @jdemeyer @sagetrac-tmonteil @cheuberg
Component: numerical
Keywords: interval, root
Author: Miguel Marco
Branch: 39558b6
Reviewer: Vincent Delecroix, Marc Mezzarobba
Issue created by migration from https://trac.sagemath.org/ticket/19964