class LinearRecurrence

[Ralf Stephan]

Please make your comments on the design while it's baking.

http://trac.sagemath.org/ticket/15714

Regards,

Ralf Stephan

[David Joyner]

Have you looked at what SymPy has already (it is included in Sage)?

> --
> You received this message because you are subscribed to the Google Groups
> "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sage-devel+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/groups/opt_out.

[Thierry]

Hi,

not the same but quite related, there are people working on having
D-finite functions in Sage, it could be nice to have consistent
notations. Here are some slides from SD49:

http://marc.mezzarobba.net/exposes/sd49-mezzarobba-20130620-slides.pdf

Ciao,
Thierry

[Ralf Stephan]

Thanks

​for​

 the hints. The recurrence solvers in SymPy (sympy.solvers.recurr.rsolve) will be helpful to have.

​ I have my own ideas too.​

​​ 

As to D-finite series, I have respect for the folks tackling the next generalization (polynomial coefficients) which is way over my head. I'll try to adapt to what they can offer.

You received this message because you are subscribed to a topic in the Google Groups "sage-devel" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/sage-devel/PTx12wrVG0c/unsubscribe.
To unsubscribe from this group and all its topics, send an email to sage-devel+...@googlegroups.com.

[Marc Mezzarobba]

Ralf Stephan wrote:
> Please make your comments on the design while it's baking.
>
> http://trac.sagemath.org/ticket/15714

Just some quick thoughts.

To me most of the features you suggest look like a special case of what
is already implemented in Manuel Kauers et al.'s ore_algebra package--
which uses Sage, but is not part of it or even submitted for inclusion
yet. Note that even though ore_algebra is mostly about recurrences with
polynomial coefficients, it also provides specific parents for operators
with constant coefficients. (I don't remember if they implement any
features specific to constant coefficients, though.) It would probably
be a good idea to use and/or extend it as much as possible, and strive
to be compatible with it in any case.

That being said, in ore_algebra, the main objects are recurrence
*operators* (among other kinds of linear operators), without initial
values. I think there is also room in Sage for *recurrence sequences*
that really behave like sequences. (In fact, I was planning to implement
recurrence sequences with polynomial coefficients myself, based on
ore_algebra.) Your interface goes in that direction, but it also
contains things such as guess() and random_object() that do not belong
there if the mathematical object you are trying to model is a sequence.
IMO it is useful to distinguish between recurrence operators and
*solutions* of recurrences (and possibly inhomogeneous recurrence
equations in between). And in general, a given class should model only
one kind of mathematical object!

Best wishes,

--
Marc

[Ralf Stephan]

I'm leaning towards the operator kind of recurrence because I definitely don't think about it as a sequence with specific length. But the core object really is the ogf, i.e. the polynomial fraction which defines everything in the same sense special function expressions are sufficient to define all D-finite sequences. So, the object is a fraction, everything else an alternative interface, and other values are only cached for programming convenience.

For this reason, without having looked at ore algebra, I would have trouble understanding why the operator would be a core concept of all holonomic function expressions or sequences.

Can you point at my error in thinking, please?

[Ralf Stephan]

I see now how powerful the ore algebra approach is. It is still unclear to me if all polynomial fractions (even those >1) can be represented, which would be prerequisite to represent recurrences with all possible initial values.

Looking forward to ore_algebra. If that package link were available now I would start using it immediately, but the page was under construction.

[Marc Mezzarobba]

Ralf Stephan wrote:
> Looking forward to ore_algebra. If that package link were available
> now I would start using it immediately, but the page was under
> construction.

The direct link that was posted to sage-devel a few month ago still
seems valid:

http://www.risc.jku.at/research/combinat/software/ore_algebra/

--
Marc

[Marc Mezzarobba]

Ralf Stephan wrote:
> I'm leaning towards the operator kind of recurrence because I
> definitely don't think about it as a sequence with specific length.
> But the core object really is the ogf, i.e. the polynomial fraction
> which defines everything in the same sense special function
> expressions are sufficient to define all D-finite sequences. So, the
> object is a fraction, everything else an alternative interface, and
> other values are only cached for programming convenience.
> For this reason, without having looked at ore algebra, I would have
> trouble understanding why the operator would be a core concept of all
> holonomic function expressions or sequences.
> Can you point at my error in thinking, please?

I think I don't understand what you mean, sorry.

But let me try to clarify what I was trying to say:

* Despite the name of your class, it looks like you intend its
instances to represent solutions of recurrences with constant
coefficients, not recurrences themselves.

* That's fine, but then the interface should be consistent with that
choice. In particular, I find the name LinearRecurrence misleading,
and I think methods like guess() and random_object() should go
elsewhere (for instance, in the parent to which your sequences
will belong). [#]

* It would be useful to have both recurrence operators (as
implemented in ore_algebra) and recurrence sequences. The design
that makes the most sense to me is to implement recurrence sequences
on top of recurrence operators, but I didn't really give it a lot of
thought. In any case, we need to avoid code duplication and make the
interfaces as consistent as possible.

[#] More about the name: IMO we should reserve LinearRecurrenceSequence
to for solutions of linear recurrences with arbitrary coefficients. What
about CFiniteSequence (and CFiniteSequenceRing or CFiniteSequenceAlgebra
for the parent) ?

--
Marc

[Marc Mezzarobba]

One more remark: there is also a basic implementation of linear
recurrences with constant coefficients in sage.crypto.lfsr...

--
Marc

[Ralf Stephan]

I have the ore_algebra package now. I'm not satisfied with its interface, nor with that of LSFR or its services.

The guess() and random_object() methods of my proposed class indeed do not belong to such an object. That's why they are declared @static_method.

Yes, we need to avoid code duplication. The ore_algebra package however is heavyweight, and I'm already finding bugs in the guess function which I'm reporting there. Usual methods for C-finite sequences use the well-established and fast LLL algorithm. The guessing possibility of LSFR appears to only give the characteristic polynomial, so is not complete. Note that none of the alternatives offer services to convert between sequence and g.f. and back.

I like the name you propose. It is very distinct. I am also not fixed on developing this issue in favor of patching the ore_algebra. I'll see how responsive the author is.