Opened 3 years ago
Last modified 2 years ago
#26549 new enhancement
Formal power series over large commutative rings
Reported by:  ghNatStapleton  Owned by:  ghNatStapleton 

Priority:  minor  Milestone:  
Component:  algebra  Keywords:  formal power series 
Cc:  niles  Merged in:  
Authors:  Owen McGrath, Rick McQueen, Ethan Reed, Nathaniel Stapleton  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/ghtheowen/formal_power_series_over_large_commutative_rings (Commits, GitHub, GitLab)  Commit:  d3f34349dcf5b89ccd4b5885c80e1228ec65d68d 
Dependencies:  Stopgaps: 
Description (last modified by )
The goal of this project is to build software in Sage for doing lazy computation with multivariable formal power series over large commutative ring (such as the Lazard ring, which is a polynomial ring over the integers in an countable number of variables).
We will define power series by describing a function from a cartesian power of the natural numbers to the coefficient ring. We plan to manipulate such power series in a completely formal manner. For example, when two formal power series are added, the resulting formal power series is just a tree containing the node "+" with the two functions defining the formal power series as children. The only time computation of the coefficients occurs is when the user asks to "view" a power series out to some range. Then our goal is to perform the minimal amount of computation in order to show the resulting power series to the user to the specified precision.
We also introduce a class of commutative rings called "IndRings?". They are simply sequential diagrams of finitely generated kalgebras, where k is a base ring that Sage knows about. An IndRing? is defined by specifying a function from the natural numbers to finitely generated kalgebras and, for each natural number i, a map of kalgebras from the kalgebra associated to i to the kalgebra associated to i+1.
A map of IndRings? is a map of Indobjects in finitely generated kalgebras. That is, it is given by specifying countable subsets S and T of the natural numbers and a surjective lax order preserving map f from S to T and a map of kalgebras from the kalgebra associated to an element s in S to the kalgebra associated to f(s). These maps are supposed to commute with all of the structure, but we will not check this in the software.
We also provide a way to promote a finitely generated kalgebra to an IndRing?.
Given an IndRing?, we define a nvariable power series over it by specifying a function 'b' from the natural numbers to the natural numbers and then a function from the ntuples of natural numbers of total degree i (just the sum of the values in the ntuple) to the b(i)'th ring in the IndRing?. When the user asks to view the power series to degree 'i', the result will be a polynomial of total degree i over the b(i)'th ring in the IndRing?.
Relation to Power Series and Multivariate Power Series (the code already in Sage):
We built this code on top of the existing code. This code is not meant to be a replacement but to be an extension of the existing code.
As mentioned above, the formal power series in this code are functions from a cartesian power of the natural numbers to a ring (or IndRing? as described above). These formal power series are manipulated completely formally, we keep track of a tree of operations that user has performed on their formal power series.
However, when the user asks to view one of these formal power series out to some degree, then the formal power series in the leaves of the tree are used to construct multivariate power series (in the sense of Sage) and these multivariate power series are manipulated according to the operations in the tree using the existing Sage code.
There are two points at which something strange happens.
First, if the user asks to apply reversion to a single variable formal power series, then we convert the multivariate power series into a power series (in the sense of Sage) and apply reversion and then convert the result back to a multivariable power series.
Second, we found the multiplication of multivariable power series to be slow. After looking at the code, we believe that this is due to the fact that the current code multiplies the underlying polynomials and then truncates the result. Of course, it is more efficient to only multiply terms that contribute to the product up to the degree that you are interested in. We have implemented this more efficient multiplication in this code and it is the default multiplication for formal power series. We also make use of this faster multiplication when the user asks to view the composite of certain formal power series.
Attachments (3)
Change History (24)
comment:1 Changed 3 years ago by
 Description modified (diff)
 Owner changed from (none) to ghNatStapleton
Changed 3 years ago by
Changed 3 years ago by
comment:2 Changed 3 years ago by
 Branch set to t/26549/formal_power_series_over_large_commutative_rings
comment:3 Changed 3 years ago by
 Cc niles added
comment:4 Changed 3 years ago by
Great! I can't see the branch you've created  perhaps it is not uploaded to trac? Are you using the git trac
command (here)? Or using git directly (known as the hard way, but it's not that hard ;)?
In any case, one of the questions I know people will ask will be how this relates/integrates with the existing power series. Can this be implemented as an addon to the current interface? (maybe you've already done that in your branch?)
Another question will be some examples demonstrating differences in speed and memory usage in this implementation v.s. the current power series. If you have any such examples, let me know.
comment:5 Changed 3 years ago by
 Description modified (diff)
comment:6 Changed 2 years ago by
 Milestone changed from sage8.5 to sage8.7
comment:7 Changed 2 years ago by
 Branch changed from t/26549/formal_power_series_over_large_commutative_rings to u/ghtheowen/formal_power_series_over_large_commutative_rings
comment:8 Changed 2 years ago by
 Commit set to 0fd26e11ed5fcef292869fb04948ee734c3bf00b
Thanks! I've been slow at getting to this, but it is on my list :)
New commits:
0fd26e1  initial port into sage

comment:9 Changed 2 years ago by
 Commit changed from 0fd26e11ed5fcef292869fb04948ee734c3bf00b to 658e4f7053698c2a79a4cc6b6aaead0227c595c4
Branch pushed to git repo; I updated commit sha1. New commits:
658e4f7  add imports and fix sage code > python code

comment:10 Changed 2 years ago by
 Commit changed from 658e4f7053698c2a79a4cc6b6aaead0227c595c4 to c9d5e42a944559a6fed03f22ca9b86b4c51b7620
Branch pushed to git repo; I updated commit sha1. New commits:
c9d5e42  better code separation in files

comment:11 Changed 2 years ago by
 Commit changed from c9d5e42a944559a6fed03f22ca9b86b4c51b7620 to a8843a73297e0879cf828c24790b184a7482bf3d
Branch pushed to git repo; I updated commit sha1. New commits:
a8843a7  autoload formal_group_laws on startup

comment:12 Changed 2 years ago by
 Commit changed from a8843a73297e0879cf828c24790b184a7482bf3d to 7a5b4f0b760aa2ed1594fa12be894a0b88dc7ade
Branch pushed to git repo; I updated commit sha1. New commits:
7a5b4f0  explain examples further

comment:13 Changed 2 years ago by
I think this is good progress. Eventually the examples should be folded in to the docstrings, so you might consider moving toward that format. For example, the documentation for power series looks like this:
https://doc.sagemath.org/html/en/reference/calculus/sage/symbolic/series.html
and the source code is like this:
https://git.sagemath.org/sage.git/tree/src/sage/symbolic/series.pyx
Since there is a lot of stuff in your code, I will try to go through it in parts. I'll start with the IndRing
stuff, unless you think there is a better place to start  let me know :)
comment:14 Changed 2 years ago by
 Commit changed from 7a5b4f0b760aa2ed1594fa12be894a0b88dc7ade to b532f5f860b87c7022d748317f0068d53656a8a2
Branch pushed to git repo; I updated commit sha1. New commits:
b532f5f  add documentation files

comment:15 Changed 2 years ago by
 Milestone changed from sage8.7 to sage8.8
Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)
comment:16 Changed 2 years ago by
 Commit changed from b532f5f860b87c7022d748317f0068d53656a8a2 to 3b12bc0259ef4cc8feafcbeba8c3dfc56bb8e02e
comment:17 Changed 2 years ago by
 Commit changed from 3b12bc0259ef4cc8feafcbeba8c3dfc56bb8e02e to f9960bff8f08a41e2820f2ba8393a817c6496bde
Branch pushed to git repo; I updated commit sha1. New commits:
f9960bf  allow calculating log() of a FGL

comment:18 Changed 2 years ago by
 Commit changed from f9960bff8f08a41e2820f2ba8393a817c6496bde to cfbc0b01a278af43c82522a3d5d791c5b7e487d8
Branch pushed to git repo; I updated commit sha1. New commits:
cfbc0b0  take log of ufgl

comment:19 Changed 2 years ago by
Second, we found the multiplication of multivariable power series to be slow. After looking at the code, we believe that this is due to the fact that the current code multiplies the underlying polynomials and then truncates the result. Of course, it is more efficient to only multiply terms that contribute to the product up to the degree that you are interested in. We have implemented this more efficient multiplication in this code and it is the default multiplication for formal power series. We also make use of this faster multiplication when the user asks to view the composite of certain formal power series.
I think this should be split off as a separate ticket as it is of independent interest and would be good to get into Sage faster. ;)
comment:20 Changed 2 years ago by
 Commit changed from cfbc0b01a278af43c82522a3d5d791c5b7e487d8 to d3f34349dcf5b89ccd4b5885c80e1228ec65d68d
Branch pushed to git repo; I updated commit sha1. New commits:
d3f3434  fix iseries

comment:21 Changed 2 years ago by
 Milestone sage8.8 deleted
As the Sage8.8 release milestone is pending, we should delete the sage8.8 milestone for tickets that are not actively being worked on or that still require significant work to move forward. If you feel that this ticket should be included in the next Sage release at the soonest please set its milestone to the next release milestone (sage8.9).
the formal power series package, do "sage preparse FPS.sage" to be able to import it