Opened 3 years ago

Last modified 2 years ago

#26549 new enhancement

Formal power series over large commutative rings

Reported by: gh-NatStapleton Owned by: gh-NatStapleton
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/gh-theowen/formal_power_series_over_large_commutative_rings (Commits, GitHub, GitLab) Commit: d3f34349dcf5b89ccd4b5885c80e1228ec65d68d
Dependencies: Stopgaps:

Status badges

Description (last modified by gh-NatStapleton)

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 k-algebras, 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 k-algebras and, for each natural number i, a map of k-algebras from the k-algebra associated to i to the k-algebra associated to i+1.

A map of IndRings? is a map of Ind-objects in finitely generated k-algebras. 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 k-algebras from the k-algebra associated to an element s in S to the k-algebra 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 k-algebra to an IndRing?.

Given an IndRing?, we define a n-variable power series over it by specifying a function 'b' from the natural numbers to the natural numbers and then a function from the n-tuples of natural numbers of total degree i (just the sum of the values in the n-tuple) 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)

FPS.sage (21.2 KB) - added by gh-NatStapleton 3 years ago.
the formal power series package, do "sage --preparse FPS.sage" to be able to import it
IndRing.sage (3.3 KB) - added by gh-NatStapleton 3 years ago.
the IndRing? package, run "sage --preparse IndRing?.sage", you may need to move IndRing?.sage.py to IndRing?.py.
examples.sage (4.6 KB) - added by gh-NatStapleton 3 years ago.
Examples that use our packages

Download all attachments as: .zip

Change History (24)

comment:1 Changed 3 years ago by gh-NatStapleton

  • Description modified (diff)
  • Owner changed from (none) to gh-NatStapleton

Changed 3 years ago by gh-NatStapleton

the formal power series package, do "sage --preparse FPS.sage" to be able to import it

Changed 3 years ago by gh-NatStapleton

the IndRing? package, run "sage --preparse IndRing?.sage", you may need to move IndRing?.sage.py to IndRing?.py.

comment:2 Changed 3 years ago by gh-theowen

  • Branch set to t/26549/formal_power_series_over_large_commutative_rings

Changed 3 years ago by gh-NatStapleton

Examples that use our packages

comment:3 Changed 3 years ago by niles

  • Cc niles added

comment:4 Changed 3 years ago by niles

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 add-on 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 gh-NatStapleton

  • Description modified (diff)

comment:6 Changed 2 years ago by gh-NatStapleton

  • Milestone changed from sage-8.5 to sage-8.7

comment:7 Changed 2 years ago by gh-theowen

  • Branch changed from t/26549/formal_power_series_over_large_commutative_rings to u/gh-theowen/formal_power_series_over_large_commutative_rings

comment:8 Changed 2 years ago by niles

  • Commit set to 0fd26e11ed5fcef292869fb04948ee734c3bf00b

Thanks! I've been slow at getting to this, but it is on my list :)


New commits:

0fd26e1initial port into sage

comment:9 Changed 2 years ago by git

  • Commit changed from 0fd26e11ed5fcef292869fb04948ee734c3bf00b to 658e4f7053698c2a79a4cc6b6aaead0227c595c4

Branch pushed to git repo; I updated commit sha1. New commits:

658e4f7add imports and fix sage code -> python code

comment:10 Changed 2 years ago by git

  • Commit changed from 658e4f7053698c2a79a4cc6b6aaead0227c595c4 to c9d5e42a944559a6fed03f22ca9b86b4c51b7620

Branch pushed to git repo; I updated commit sha1. New commits:

c9d5e42better code separation in files

comment:11 Changed 2 years ago by git

  • Commit changed from c9d5e42a944559a6fed03f22ca9b86b4c51b7620 to a8843a73297e0879cf828c24790b184a7482bf3d

Branch pushed to git repo; I updated commit sha1. New commits:

a8843a7auto-load formal_group_laws on startup

comment:12 Changed 2 years ago by git

  • Commit changed from a8843a73297e0879cf828c24790b184a7482bf3d to 7a5b4f0b760aa2ed1594fa12be894a0b88dc7ade

Branch pushed to git repo; I updated commit sha1. New commits:

7a5b4f0explain examples further

comment:13 Changed 2 years ago by niles

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 git

  • Commit changed from 7a5b4f0b760aa2ed1594fa12be894a0b88dc7ade to b532f5f860b87c7022d748317f0068d53656a8a2

Branch pushed to git repo; I updated commit sha1. New commits:

b532f5fadd documentation files

comment:15 Changed 2 years ago by embray

  • Milestone changed from sage-8.7 to sage-8.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 git

  • Commit changed from b532f5f860b87c7022d748317f0068d53656a8a2 to 3b12bc0259ef4cc8feafcbeba8c3dfc56bb8e02e

Branch pushed to git repo; I updated commit sha1. New commits:

eaa9fd5remve getConst, fix view(0) and start memoization
3b12bc0remove fgl.py

comment:17 Changed 2 years ago by git

  • Commit changed from 3b12bc0259ef4cc8feafcbeba8c3dfc56bb8e02e to f9960bff8f08a41e2820f2ba8393a817c6496bde

Branch pushed to git repo; I updated commit sha1. New commits:

f9960bfallow calculating log() of a FGL

comment:18 Changed 2 years ago by git

  • Commit changed from f9960bff8f08a41e2820f2ba8393a817c6496bde to cfbc0b01a278af43c82522a3d5d791c5b7e487d8

Branch pushed to git repo; I updated commit sha1. New commits:

cfbc0b0take log of ufgl

comment:19 Changed 2 years ago by tscrim

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 git

  • Commit changed from cfbc0b01a278af43c82522a3d5d791c5b7e487d8 to d3f34349dcf5b89ccd4b5885c80e1228ec65d68d

Branch pushed to git repo; I updated commit sha1. New commits:

d3f3434fix iseries

comment:21 Changed 2 years ago by embray

  • Milestone sage-8.8 deleted

As the Sage-8.8 release milestone is pending, we should delete the sage-8.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 (sage-8.9).

Note: See TracTickets for help on using tickets.