Benjamin Hackl

Computing with Asymptotic Expressions

It has been quite some time since my last update on the progress of my Google Summer of Code project, which has two reasons.

On the one hand, I have been busy because of the end of the semester, as well as because of the finalization of my Master’s thesis — and on the other hand, it is not very interesting to write a post on discussing and implementing rather technical details. Nevertheless, Daniel Krenn and myself have been quite busy in order to bring asymptotic expressions to SageMath. Fortunately, these efforts are starting to become quite fruitful.

In this post I want to discuss our current implementation roadmap (i.e. not only for the remaining Summer of Code, but also for the time afterwards), and give some examples for what we are currently able to do.

Structure and Roadmap

An overview of the entire roadmap can be found at here (trac #17601). Recall that the overall goal of this project is to bring asymptotic expressions like $2^n + n^2 \log n + O(n)$ to Sage. Our implementation (which aims to be as general and expandable as possible) tackles this problem with a three-layer approach:

• GrowthGroups and GrowthElements (trac #17600). These elements and parents manage the growth (and just the growth!) of a summand in an asymptotic expression like above. The simplest cases are monomial and logarithmic growth groups. For example, their elements are given by $n^r$ and $\log(n)^r$ where the exponent $r$ is from some ordered ring like $\mathbb{Z}$ or $\mathbb{Q}$. Both cases (monomial and logarithmic growth groups) can be handled in the current implementation — however, growth elements like n2logn are intended to live in the cartesian product of a monomial and a logarithmic growth group (in the same variable). Parts of this infrastructure are already prepared (see trac #18587).

• AsymptoticTerms and TermMonoids (trac #17715). While GrowthElements only represent the growth, AsymptoticTerms have more information: basically, they represent a summand in an asymptotic expression. There are different classes for each type of asymptotic term (e.g. ExactTerm and OTerm — with more to come). Additionally to a growth element, some types of asymptotic terms (like exact terms) also possess a coefficient.

• AsymptoticExpression and AsymptoticRing (trac #17716). This is what we are currently working on, and we do have a running prototype! 🙂 The version that can be found on trac is only missing some doctests and a bit of documentation. Asymptotic expressions are the central objects within this project, and essentially they are sums of several asymptotic terms. In the background, we use a special data structure (“mutable posets”, trac #17693) in order to model the (partial) order induced by the various growth elements belonging to an asymptotic expression. This allows to perform critical operations like absorption (when an $O$-term absorbs “weaker” terms) efficiently and in a simple way.

The resulting minimal prototype can, in some sense, be compared to Sage’s PowerSeriesRing: however, we also allow non-integer exponents, and extending this prototype to work with multivariate expressions should not be too hard now, as the necessary infrastructure is there.

Following the finalization of the minimal prototype, there are several improvements to be made. Here are some examples:

• Besides addition and multiplication, we also want to divide asymptotic expressions, and higher-order operations like exponentiation and taking the logarithm would be interesting as well.

• Also, conversion from, for example, the symbolic ring is important when it comes to usability of our tools. We will implement and enhance this conversion gradually.

Examples

An asymptotic ring (over a monomial growth group with coefficients and exponents from the rational field) can be created with

sage: R.<x> = AsymptoticRing('monomial', QQ); R
Asymptotic Ring over Monomial Growth Group in x over Rational Field with coefficients from Rational Field

Note that we marked the code as experimental, meaning that you will see some warnings regarding the stability of the code. Now, as we have an asymptotic ring, we can do some calculations. For example, take $(2 \sqrt{x} + O(1))^{15}$.

sage: (2*x^(1/2) + O(x^0))^15
O(x^7) + 32768*x^(15/2)

We can also have a look at the underlying structure:

sage: expr = (x^(3/7) + 2*x^(1/5)) * (x + O(x^0)); expr
O(x^(3/7)) + 2*x^(6/5) + 1*x^(10/7)
sage: expr.poset
poset(O(x^(3/7)), 2*x^(6/5), 1*x^(10/7))
sage: print expr.poset.full_repr()
poset(O(x^(3/7)), 2*x^(6/5), 1*x^(10/7))
+-- null
|   +-- no predecessors
|   +-- successors:   O(x^(3/7))
+-- O(x^(3/7))
|   +-- predecessors:   null
|   +-- successors:   2*x^(6/5)
+-- 2*x^(6/5)
|   +-- predecessors:   O(x^(3/7))
|   +-- successors:   1*x^(10/7)
+-- 1*x^(10/7)
|   +-- predecessors:   2*x^(6/5)
|   +-- successors:   oo
+-- oo
|   +-- predecessors:   1*x^(10/7)
|   +-- no successors

As you might have noticed, the “O”-constructor that is used for the PowerSeriesRing and related structures, can also be used here. In particular, $O(\operatorname{expr})$ acts exactly as expected:

sage: expr
O(x^(3/7)) + 2*x^(6/5) + 1*x^(10/7)
sage: O(expr)
O(x^(10/7))

Of course, the usual rules for computing with asymptotic expressions hold:

sage: O(x) + O(x)
O(x)
sage: O(x) - O(x)
O(x)

So far, so good. Our next step is making the multivariate growth groups usable for the AsymptoticRing and then improving the overall user interface of the ring.