Open NatStapleton opened 5 years ago
Description changed:
---
+++
@@ -7,3 +7,5 @@
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.
Attachment: FPS.sage.gz
the formal power series package, do "sage --preparse FPS.sage" to be able to import it
Attachment: IndRing.sage.gz
the IndRing package, run "sage --preparse IndRing.sage", you may need to move IndRing.sage.py to IndRing.py.
Examples that use our packages
Attachment: examples.sage.gz
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.
Description changed:
---
+++
@@ -9,3 +9,17 @@
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.
Thanks! I've been slow at getting to this, but it is on my list :)
New commits:
0fd26e1 | initial port into sage |
Commit: 0fd26e1
Branch pushed to git repo; I updated commit sha1. New commits:
658e4f7 | add imports and fix sage code -> python code |
Branch pushed to git repo; I updated commit sha1. New commits:
c9d5e42 | better code separation in files |
Branch pushed to git repo; I updated commit sha1. New commits:
a8843a7 | auto-load formal_group_laws on startup |
Branch pushed to git repo; I updated commit sha1. New commits:
7a5b4f0 | explain examples further |
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://github.com/sagemath/sagetrac-mirror/blob/develop/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 :)
Branch pushed to git repo; I updated commit sha1. New commits:
b532f5f | add documentation files |
Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)
Branch pushed to git repo; I updated commit sha1. New commits:
f9960bf | allow calculating log() of a FGL |
Branch pushed to git repo; I updated commit sha1. New commits:
cfbc0b0 | take log of ufgl |
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. ;)
Branch pushed to git repo; I updated commit sha1. New commits:
d3f3434 | fix iseries |
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).
Changed keywords from formal power series to formal power series, LazyPowerSeries
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.
CC: @nilesjohnson
Component: algebra
Keywords: formal power series, LazyPowerSeries
Author: Owen McGrath, Rick McQueen, Ethan Reed, Nathaniel Stapleton
Branch/Commit: u/gh-theowen/formal_power_series_over_large_commutative_rings @
d3f3434
Issue created by migration from https://trac.sagemath.org/ticket/26549