Sage: Ticket #12657: Better implementation of Frobenius automorphism
https://trac.sagemath.org/ticket/12657
<p>
The Frobenius automorphism of <em>p</em>-adic fields was added in <a class="closed ticket" href="https://trac.sagemath.org/ticket/8241" title="enhancement: p-adic fields should have Witt Frobenius (closed: fixed)">#8241</a>. The implementation is horribly inefficient and should use Hensel lifting directly rather than decomposing into a list of Teichmuller representatives.
</p>
<p>
This optimization should probably wait on <a class="closed ticket" href="https://trac.sagemath.org/ticket/12555" title="enhancement: Reimplement elements of Zp and Qp using templates (closed: fixed)">#12555</a>.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/12657
Trac 1.1.6jdemeyerTue, 13 Aug 2013 15:35:53 GMTmilestone changed
https://trac.sagemath.org/ticket/12657#comment:1
https://trac.sagemath.org/ticket/12657#comment:1
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.11</em> to <em>sage-5.12</em>
</li>
</ul>
TicketroedMon, 06 Jan 2014 21:24:41 GMTdependencies set
https://trac.sagemath.org/ticket/12657#comment:2
https://trac.sagemath.org/ticket/12657#comment:2
<ul>
<li><strong>dependencies</strong>
set to <em>#14304</em>
</li>
</ul>
<p>
The method that needs to be improved is <code>frobenius_unram</code> in <code>src/sage/libs/linkages/padics/unram_shared.pxi</code>. This may want to wait on some more p-adic polynomial developments, but could also be done now.
</p>
Ticketvbraun_spamThu, 30 Jan 2014 21:20:52 GMTmilestone changed
https://trac.sagemath.org/ticket/12657#comment:3
https://trac.sagemath.org/ticket/12657#comment:3
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.1</em> to <em>sage-6.2</em>
</li>
</ul>
Ticketvbraun_spamTue, 06 May 2014 15:20:58 GMTmilestone changed
https://trac.sagemath.org/ticket/12657#comment:4
https://trac.sagemath.org/ticket/12657#comment:4
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.2</em> to <em>sage-6.3</em>
</li>
</ul>
Ticketvbraun_spamSun, 10 Aug 2014 16:51:03 GMTmilestone changed
https://trac.sagemath.org/ticket/12657#comment:5
https://trac.sagemath.org/ticket/12657#comment:5
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.3</em> to <em>sage-6.4</em>
</li>
</ul>
TicketjpfloriFri, 14 Nov 2014 10:53:51 GMTcc set
https://trac.sagemath.org/ticket/12657#comment:6
https://trac.sagemath.org/ticket/12657#comment:6
<ul>
<li><strong>cc</strong>
<em>jpflori</em> added
</li>
</ul>
TicketroedMon, 17 Jul 2017 17:38:51 GMTkeywords set
https://trac.sagemath.org/ticket/12657#comment:7
https://trac.sagemath.org/ticket/12657#comment:7
<ul>
<li><strong>keywords</strong>
<em>sd87</em> added
</li>
</ul>
TicketasteeleWed, 19 Jul 2017 19:57:28 GMTbranch set
https://trac.sagemath.org/ticket/12657#comment:8
https://trac.sagemath.org/ticket/12657#comment:8
<ul>
<li><strong>branch</strong>
set to <em>u/asteele/better_implementation_of_frobenius_automorphism</em>
</li>
</ul>
TicketgitWed, 19 Jul 2017 21:02:44 GMTcommit set
https://trac.sagemath.org/ticket/12657#comment:9
https://trac.sagemath.org/ticket/12657#comment:9
<ul>
<li><strong>commit</strong>
set to <em>ffcb86ca34e2f45641ec8639b2a045527f5c1e61</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=9a280e0d22e449a981086f98c80a23408d89ae06"><span class="icon"></span>9a280e0</a></td><td><code>Add cached method for computing frob of generator of unramified extension. Speeds up general frob</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=ffcb86ca34e2f45641ec8639b2a045527f5c1e61"><span class="icon"></span>ffcb86c</a></td><td><code>Make frob_gen() method private</code>
</td></tr></table>
TicketgitWed, 19 Jul 2017 21:38:09 GMTcommit changed
https://trac.sagemath.org/ticket/12657#comment:10
https://trac.sagemath.org/ticket/12657#comment:10
<ul>
<li><strong>commit</strong>
changed from <em>ffcb86ca34e2f45641ec8639b2a045527f5c1e61</em> to <em>3a03a51b0875bc8d72e3f51b787245938e464493</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=3a03a51b0875bc8d72e3f51b787245938e464493"><span class="icon"></span>3a03a51</a></td><td><code>Add doctest for _frob_gen()</code>
</td></tr></table>
TicketasteeleThu, 20 Jul 2017 02:07:42 GMTstatus changed
https://trac.sagemath.org/ticket/12657#comment:11
https://trac.sagemath.org/ticket/12657#comment:11
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TicketgparkThu, 20 Jul 2017 16:02:26 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/12657#comment:12
https://trac.sagemath.org/ticket/12657#comment:12
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>GaYee Park</em>
</li>
</ul>
<p>
All test passed.
</p>
TickettscrimThu, 20 Jul 2017 23:17:16 GMTstatus, milestone changed
https://trac.sagemath.org/ticket/12657#comment:13
https://trac.sagemath.org/ticket/12657#comment:13
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
<li><strong>milestone</strong>
changed from <em>sage-6.4</em> to <em>sage-8.1</em>
</li>
</ul>
<p>
Author name missing.
</p>
TicketasteeleThu, 20 Jul 2017 23:30:42 GMTstatus changed; author set
https://trac.sagemath.org/ticket/12657#comment:14
https://trac.sagemath.org/ticket/12657#comment:14
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>author</strong>
set to <em>asteele, Ricky Magner</em>
</li>
</ul>
TicketcarusoFri, 21 Jul 2017 03:40:42 GMTcc, reviewer changed
https://trac.sagemath.org/ticket/12657#comment:15
https://trac.sagemath.org/ticket/12657#comment:15
<ul>
<li><strong>cc</strong>
<em>caruso</em> added
</li>
<li><strong>reviewer</strong>
changed from <em>GaYee Park</em> to <em>GaYee Park, Xavier Caruso</em>
</li>
</ul>
<p>
I don't understand why you need to redo Newton iteration in <code>frobenius_unram</code>.
</p>
<p>
Alternatively, instead of storing the powers of <code>frob_a</code> in a dictonary, you can use Horner scheme.
</p>
TicketasteeleFri, 21 Jul 2017 04:10:14 GMT
https://trac.sagemath.org/ticket/12657#comment:16
https://trac.sagemath.org/ticket/12657#comment:16
<p>
We redid the Newton iteration in _frob_gen() because that was easier (for me) than finding & adapting an existing method. The only method I see is .hensel_lift(p,e) in sage.rings.polynomial.polynomial_element.Polynomial, and I don't see the advantage of adapting that.
</p>
<p>
As for the horner scheme--our experiments suggested that the expensive operation was multiplication (in large degree unramified extensions). For example, In R.<a> = Zq(37<sup>100</sup>,100), addition of two random elements takes ~80 micro seconds, while muliplication takes ~80 milli seconds. My naive guess is that cacheing the powers of frob_a in the dictionary and paying the cost of addition will be much faster than paying the repeated cost of multiplication. In any case, storing the powers in a dict or computing the polynomials via horner are much faster than the previous method of computing frobenius.
</p>
TicketroedFri, 21 Jul 2017 04:53:37 GMTauthor changed
https://trac.sagemath.org/ticket/12657#comment:17
https://trac.sagemath.org/ticket/12657#comment:17
<ul>
<li><strong>author</strong>
changed from <em>asteele, Ricky Magner</em> to <em>Ander Steele, Ricky Magner</em>
</li>
</ul>
TicketcarusoFri, 21 Jul 2017 05:50:58 GMT
https://trac.sagemath.org/ticket/12657#comment:18
https://trac.sagemath.org/ticket/12657#comment:18
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12657#comment:16" title="Comment 16">asteele</a>:
</p>
<blockquote class="citation">
<p>
We redid the Newton iteration in _frob_gen() because that was easier (for me) than finding & adapting an existing method. The only method I see is .hensel_lift(p,e) in sage.rings.polynomial.polynomial_element.Polynomial, and I don't see the advantage of adapting that.
</p>
</blockquote>
<p>
I wanted to say that you redid Newton iteration in <code>_frob_gen()</code> and in <code>frobenius_unram()</code>. Is there a reason for that?
</p>
<blockquote class="citation">
<p>
As for the horner scheme--our experiments suggested that the expensive operation was multiplication (in large degree unramified extensions). For example, In R.<a> = Zq(37<sup>100</sup>,100), addition of two random elements takes ~80 micro seconds, while muliplication takes ~80 milli seconds. My naive guess is that cacheing the powers of frob_a in the dictionary and paying the cost of addition will be much faster than paying the repeated cost of multiplication. In any case, storing the powers in a dict or computing the polynomials via horner are much faster than the previous method of computing frobenius.
</p>
</blockquote>
<p>
I don't understand why Horner method is more costly in terms of multiplications. On the contrary, I think that it is (a bit) less costly.
</p>
TicketgitFri, 21 Jul 2017 09:07:50 GMTcommit changed
https://trac.sagemath.org/ticket/12657#comment:19
https://trac.sagemath.org/ticket/12657#comment:19
<ul>
<li><strong>commit</strong>
changed from <em>3a03a51b0875bc8d72e3f51b787245938e464493</em> to <em>62cec73f79f300e700cc683b9a2486d796777905</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=ea18e00487a1c2e054e42f823df00e3f93423ff0"><span class="icon"></span>ea18e00</a></td><td><code>fix whitespace</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=62cec73f79f300e700cc683b9a2486d796777905"><span class="icon"></span>62cec73</a></td><td><code>Remove duplicated code</code>
</td></tr></table>
TicketasteeleFri, 21 Jul 2017 10:16:36 GMT
https://trac.sagemath.org/ticket/12657#comment:20
https://trac.sagemath.org/ticket/12657#comment:20
<p>
Aha, thanks for catching that! That was a mistake, and has been fixed.
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12657#comment:18" title="Comment 18">caruso</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12657#comment:16" title="Comment 16">asteele</a>:
</p>
<blockquote class="citation">
<p>
We redid the Newton iteration in _frob_gen() because that was easier (for me) than finding & adapting an existing method. The only method I see is .hensel_lift(p,e) in sage.rings.polynomial.polynomial_element.Polynomial, and I don't see the advantage of adapting that.
</p>
</blockquote>
<p>
I wanted to say that you redid Newton iteration in <code>_frob_gen()</code> and in <code>frobenius_unram()</code>. Is there a reason for that?
</p>
</blockquote>
<p>
I just tested the Horner method and it is roughly 10 times slower in Zq(5<sup>100</sup>,100). It seems that multiplying elements of the extension by elements in Q_p is very fast, but multiplying elements in the extension is generally slow. Cacheing the expensive multiplications (and maybe performing more multiplications over all) appears to be a good strategy in very high degree.
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
As for the horner scheme--our experiments suggested that the expensive operation was multiplication (in large degree unramified extensions). For example, In R.<a> = Zq(37<sup>100</sup>,100), addition of two random elements takes ~80 micro seconds, while muliplication takes ~80 milli seconds. My naive guess is that cacheing the powers of frob_a in the dictionary and paying the cost of addition will be much faster than paying the repeated cost of multiplication. In any case, storing the powers in a dict or computing the polynomials via horner are much faster than the previous method of computing frobenius.
</p>
</blockquote>
<p>
I don't understand why Horner method is more costly in terms of multiplications. On the contrary, I think that it is (a bit) less costly.
</p>
</blockquote>
TicketcarusoFri, 21 Jul 2017 14:47:30 GMT
https://trac.sagemath.org/ticket/12657#comment:21
https://trac.sagemath.org/ticket/12657#comment:21
<p>
Let me disagree :-).
</p>
<p>
On my laptop, with your current implementation, it takes about 1s to compute the Frobenius of a random element over <code>Zq(5^100,100)</code> (without taking in account the computation of the Frobenius of the generator) while it takes less than 0.1s using the Horner scheme (cf implementation attached). It is then about 10 times faster.
</p>
<p>
By the way, as far as I understand, an element of Zq is representated as P(a) where a is the generator and P is a polynomial over Z. What we do currently is to write all the coefficients of P in radix p (this is done by the method <code>list</code>), and then just after recompose them into actual integers. It would be better to avoid this useful computation and access directly to the coefficients of P but I'm not sure it's easy to do it.
</p>
TicketcarusoFri, 21 Jul 2017 14:48:13 GMTbranch changed
https://trac.sagemath.org/ticket/12657#comment:22
https://trac.sagemath.org/ticket/12657#comment:22
<ul>
<li><strong>branch</strong>
changed from <em>u/asteele/better_implementation_of_frobenius_automorphism</em> to <em>u/caruso/better_implementation_of_frobenius_automorphism</em>
</li>
</ul>
TicketgitFri, 21 Jul 2017 14:48:45 GMTcommit changed
https://trac.sagemath.org/ticket/12657#comment:23
https://trac.sagemath.org/ticket/12657#comment:23
<ul>
<li><strong>commit</strong>
changed from <em>62cec73f79f300e700cc683b9a2486d796777905</em> to <em>8ae9f8aff0648ed4a3a90e137a6640945f208140</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=8ae9f8aff0648ed4a3a90e137a6640945f208140"><span class="icon"></span>8ae9f8a</a></td><td><code>Use Horner scheme</code>
</td></tr></table>
TicketasteeleSat, 22 Jul 2017 16:00:31 GMT
https://trac.sagemath.org/ticket/12657#comment:24
https://trac.sagemath.org/ticket/12657#comment:24
<p>
Fantastic! I see your implementation of Horner is much better than what I was doing, and I have reproduced the performance increase on k8s: After <code>_frob_gen()</code> is cached, your scheme computes frobenius of random elements of <code> Zq(5^100,100) </code> in approximately 60 ms, while the previous method was taking 800ms. Your current implementation is definitely the way to go (and is roughly 1000 times faster than what is currently in Sage)
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12657#comment:21" title="Comment 21">caruso</a>:
</p>
<blockquote class="citation">
<p>
Let me disagree :-).
</p>
<p>
On my laptop, with your current implementation, it takes about 1s to compute the Frobenius of a random element over <code>Zq(5^100,100)</code> (without taking in account the computation of the Frobenius of the generator) while it takes less than 0.1s using the Horner scheme (cf implementation attached). It is then about 10 times faster.
</p>
<p>
By the way, as far as I understand, an element of Zq is representated as P(a) where a is the generator and P is a polynomial over Z. What we do currently is to write all the coefficients of P in radix p (this is done by the method <code>list</code>), and then just after recompose them into actual integers. It would be better to avoid this useful computation and access directly to the coefficients of P but I'm not sure it's easy to do it.
</p>
</blockquote>
TicketchapotonSun, 23 Jul 2017 08:17:07 GMT
https://trac.sagemath.org/ticket/12657#comment:25
https://trac.sagemath.org/ticket/12657#comment:25
<p>
maybe the iteration <code>+ for i in range(len(coefs)):</code>
could be replaced by just <code>+ for ci in coefs:</code> ?
</p>
TicketasteeleTue, 25 Jul 2017 20:12:17 GMTbranch changed
https://trac.sagemath.org/ticket/12657#comment:26
https://trac.sagemath.org/ticket/12657#comment:26
<ul>
<li><strong>branch</strong>
changed from <em>u/caruso/better_implementation_of_frobenius_automorphism</em> to <em>u/asteele/better_implementation_of_frobenius_automorphism</em>
</li>
</ul>
TicketasteeleTue, 25 Jul 2017 20:16:38 GMTcommit changed
https://trac.sagemath.org/ticket/12657#comment:27
https://trac.sagemath.org/ticket/12657#comment:27
<ul>
<li><strong>commit</strong>
changed from <em>8ae9f8aff0648ed4a3a90e137a6640945f208140</em> to <em>5c9d33c72a8993cde39ebd9d1ccf774bfb65b07d</em>
</li>
</ul>
<p>
I've cleaned up the code a little bit, removing the previous method (which contained the non-pythonic iteration <code>for i in range(len(coefs))</code> ). Code now uses Xavier's implementation of Horner' scheme, passes all doctests and, I think, is ready for review.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=5c9d33c72a8993cde39ebd9d1ccf774bfb65b07d"><span class="icon"></span>5c9d33c</a></td><td><code>remove extraneous code</code>
</td></tr></table>
TicketcarusoFri, 28 Jul 2017 18:06:42 GMTstatus changed
https://trac.sagemath.org/ticket/12657#comment:28
https://trac.sagemath.org/ticket/12657#comment:28
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Ok, positive review (through it would be even faster to use the method <code>polynomial</code> of ticket <a class="closed ticket" href="https://trac.sagemath.org/ticket/14825" title="enhancement: Iterators for p-adic expansions, polynomial representations of padic ... (closed: fixed)">#14825</a> but it still needs work).
</p>
TicketvbraunSat, 29 Jul 2017 19:27:02 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/12657#comment:29
https://trac.sagemath.org/ticket/12657#comment:29
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>u/asteele/better_implementation_of_frobenius_automorphism</em> to <em>5c9d33c72a8993cde39ebd9d1ccf774bfb65b07d</em>
</li>
</ul>
Ticket