Power_Series

---

title: Power Series permalink: wiki/Power_Series/ layout: wiki

Saturday

PowerSeries.m2 is getting going. We know we will want to create power series from rational functions, or by inputting the general term, or by simply inputting a few terms. After some time we decided to have two types of precision for each series: the actual precision of the power series [analogous to #significant figures for a real number] and the preferred display precision.

After more work it was decided that instead a power series should have a certain amount of data "known" and also have a "growMe" function, so that each power series knows how to increase its own precision at will (or knows that it cannot!).

Sunday

The goal here is for a Series to have only a finite amount computed while retaining enough information to increase precision at-will without re-calculating anything that was already done. This is challenging, for example, when making sure that the product of a generating function with a rational function still has efficiently-growable precision.

The data structure for a Series has the following:

• Keys in our Type
  1. Polynomial (as much of the polynomial as has been computed)
  2. ComputedDegree (highest computed degree)
  3. MaxDegree (highest degree allowed, ZZ or infinity)
  4. Degree (displayed degree, one less than the O)
  5. setDegree (a function that facilitates efficiently increasing or decreasing the degree of the power series, when possible.)
     1. setDegree takes (oldPolynomial,oldComputedDegree,newDegree) and returns (newPolynomial,computedDegree). computedDegree is probably either the oldComputedDegree [no computations were requuired] or newDegree [computations were required].

This allows the function "1/(1-x)" to be displayed as 1+x+x^2+O(3) to computedDegree 2 with maxDegree infinity. This can then have its precision lowered, with the computations cached. So it may be temporarily displayed as 1+x+O(2), but if the precision is later increased to 5, the second term will not need to be re-calculated.

• There are three ways to construct a Series:
  1. Giving a finite-precision series, so giving a polynomial and a degree. This allows the user to directly enter "x + O(x^3)".
  2. Giving a generating function. This allows the power series in x with coefficients i -> i!
  3. Giving a rational function. [still to be implemented] [This exists now].
  4. (Another possibility) giving a function the computes the nth degree approximation of the series. This is essentially how we work with rational functions.

• Notes-to-self:
  1. The end degree when a binary operation is used on two series is min(MaxDegree1, MaxDegree2, max(ComputedDegree1, ComputedDegree2))
  2. we'll need to use something like Karatsuba Multiplication http://en.wikipedia.org/wiki/Karatsuba_algorithm

• Functions Needed
  1. makeCompatible (make two series compatible for binary operations)
  2. Addition
  3. Multiplication
  4. Equality-test a la floating-point numbers. Floating-point numbers are == if they agree up to the precision of the least-precise number. 1.1 == 1.134
  5. Negation
  6. Inverse
  7. Division
  8. What if people try to make a power series in (x-1)?
  9. When we add or multiply things with lots of cached (but undisplayed) information,how much should actually be computed?
  10. We really need the setDegree() for rational functions to utilize all of the infrastructure we built, i.e. not re-calculate the whole power series upon being asked to add one more term. Such time-saving techniques are already implemented for all other ways of creating series.
  11. Accessor for polynomial

Monday

Good morning!

New things we have realized we need:

• A constructor for power series that allows the user to input simply a function (polynomial -> polynomial) which takes a polynomial approximation for their power series and computes one more term for it. Since we have gone out of the way to avoid finding extra terms of series whenever we can, the formulas for such things can even involve serious computations.
  1. Note: This is currently implemented as function(ZZ) -> polynomial. Such a function could in theory keep track of the previous polynomial itself (via caching), this might be what we demand.

• We need to fix the makeCompatible function -- we should never grow a function to perform operations on it; if anything we should shrink them. Computations should not be done which will have their results non-displayed.

To see inside a FunctionClosure

• g = i -> j -> k -> (i,j,k)
• (g 4) 5
• code oo

• Functions Needed
  1. makeCompatible (make two series compatible for binary operations)
  2. Addition
  3. Multiplication
  4. Equality-test a la floating-point numbers. Floating-point numbers are == if they agree up to the precision of the least-precise number. 1.1 == 1.134
  5. Negation
  6. Inverse
  7. Division
  8. What if people try to make a power series in (x-1)?
  9. When we add or multiply things with lots of cached (but undisplayed) information,how much should actually be computed? ------- we need to fix this
  10. We really need the setDegree() for rational functions to utilize all of the infrastructure we built, i.e. not re-calculate the whole power series upon being asked to add one more term. Such time-saving techniques are already implemented for all other ways of creating series.
  11. Accessor for polynomial
  12. QQ + Series; QQ * Series
  13. Currently multiplication calculates a pile of unnecessary product bits. :(
  14. We should output series (or at least have an option to output series) in the reverse order with the "O( n )" on the right.
  15. Make setDegree with too-high degree throw an error, not a warning.
  16. When doing series operations, only compute the visible sum/diff etc, not the maxComputed sum/diff etc.
  17. Have some way to input log, sin, cos, etc.
  18. Middle product algorithm?
  19. This needs to be renamed to inefficientSeries(): A constructor that recomputes the entire series every time it grows currently exists: this is convenient for the user but wasteful and very recomputey.
  20. This needs to be created as efficientSeries(): A constructor that takes as input Function: (polynomial,degree) -> polynomial, so that the user can tell us how to recursively give us the "next term" of a series is needed. This allows them to give bad input, for instance they could try to add 2 + 1 + 1/2 + 1/4 against our will.
  21. We need to fix how sums work with finite-precision series (they pass along nonsense information in their polynomial, which will never be accessed anyway, but it shouldn't be there) [Jason]
  22. Series from hilbert series
  23. Fix all those weird warnings when package is loaded twice

Tuesday

Documentation day!

• opening PowerSeries package page.
• "Operations on power series" -- this is 3/4-done by Jason
• "Constructing power series"
• Examples*7 for all the constructors
• toPolynomial
• setDegree
• dominantTerm

Things to do:

• Clean the file

Remaining implementation issues which will probably go unimplemented:

• What if people try to make a power series in (x-1)?
• Currently multiplication calculates a pile of unnecessary product bits. :(
• Have some way to input log, sin, cos, etc.
• Middle product algorithm?
• Series ^ ZZ
• Series as functions, i.e. you can apply x+x^2 to x=1... but should you even be able to do so for x+x^2+O(3)?

The documentation is pretty!! You should look at it.