#19964: tight complex interval inverse
-------------------------------------+-------------------------------------
Reporter: mmarco | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-7.1
Component: numerical | Resolution:
Keywords: interval, root | Merged in:
Authors: Miguel Marco | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/mmarco/tight_complex_interval_inverse|
97f4504c20b5bfbf315f5e00013dab27df25fbd3
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Old 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).
New 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)]
}}}
--
Comment (by mmarco):
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. But it has a big effect in root isolation:
--
Ticket URL: <http://trac.sagemath.org/ticket/19964#comment:6>
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.
