Polynomials. Different kinds of polynomials

[lounres]

It would be great to have at least univariate and multivariate (with named variables) polynoamials.

For now I have an implementations (the repo) of 3 kinds of polynomials:

1. Univariate polynomials (UnivariatePolynomial and UnivariatePolynomialSpace). It is extended realization of current KMath Polynomial and PolynomialSpace. Now it is honest realization ring (see #336).
2. Polynomials with numbered variables (NumberedPolynomial and NumberedPolynomialSpace). It is implementation of multivariate polynomials where variables are considered numbered with natural numbers (0 is natural).
3. Polynomials with labeled variables (LabeledPolynomial and LabeledPolynomialSpace). It is implementation of multivariate polynomials where variables are considered named (with some strings).

P.S. Use cases of the polynomials:

1. Univariate polynomials are very useful for simple algebra with polynomials. I used them a lot in combination with field of rational numbers for a lot of number theory problems (like computing Stirling number (of both the first and the second kinds) and sequence A002869).
2. Numbered polynomials are useful for multivariate polynomial calculations with a lot of variables of the same nature (and no other variables). Like computation with symmetric polynomials with a lot of variables. I didn't use it a lot. But sometimes it may be useful.
3. Labeled polynomials are very useful for multivariate polynomials calculation. I used them a lot in combination with field of rational numbers for algebraic calculations in geometry. Naming of variables obviously came in handy for user-friendly representation of the polynomials.

Also UnivariatePolynomial as KMath's Polynomial suffers from polynomials with few terms of large degree (see #446). In such cases NumberedPolynomial is almost an honest solution as a polynomial with backing map instead of backing list.

P.S. I also created interface PolynomialSpace in my prototype to unify the logic of polynomials. I still didn't find any use case for it. But it might be useful if one wants to create a realization of theirs own polynomials (like Laurent polynomial, etc.) or their own realization.

P.P.S. I didn't implement interface ScaleOperations by any class in my prototype. Because it looks meaningless scaling polynomials by real numbers (formally speaking, Double). For example, take F_p[x]. Adding or multiplication (also dividing in most times) by integers are meaningful: integers may be represented as elements of the field (n as n mod p; cleverly speaking there is one and only one homomorphism from Z to any possible ring or field). The same operations for rationals may be implemented in the same way and are meaningful, but are confusing. But there is no sense in addition real value to member of F_p or multiplication a member of F_p by real value. Hence, the scaling has no sense. And the same goes for polynomial extension of the field.

[altavir]

Polynomial algebra is already implemented here: https://github.com/mipt-npm/kmath/blob/master/kmath-functions/src/commonMain/kotlin/space/kscience/kmath/functions/Polynomial.kt though the documentation is thin and there are not examples. Maybe you could review the design?

Also PR into that module is welcome.

[altavir]

As for labeling, so far I am for using Map<Symbol,T> for passing arguments to multivariate environment. Map lookup is slower, than array lookup, but not by far. Also it is possible to transform Map into array using SymbolIndexer.

[lounres]

Polynomial algebra is already implemented here: https://github.com/mipt-npm/kmath/blob/master/kmath-functions/src/commonMain/kotlin/space/kscience/kmath/functions/Polynomial.kt though the documentation is thin and there are not examples.

Yeah, I've mentioned it in short comparisons (see point 1 of main body and ending of P.S. in my comment; but in dev branch instead of master).

Maybe you could review the design?

OK. (Let C be type of coefficients.) Here is comparison of KMath's Polynomial, and my UnivariatePolynomial, NumberedPolynomial and LabeledPolynomial.

1. Polynomial and UnivariatePolynomial are both backed by coefficient list List<C> (but Map<Int, C> is advised as alternative of / support for List<C>; see #446). Whereas NumberedPolynomial and LabeledPolynomial are backed by Map<List<Int>, C> and Map<Map<Variable, Int>, C>.
2. All four has additive group support (zero and addition operation).
3. Polynomial provides scaling. Whereas UnivariatePolynomial, NumberedPolynomial and LabeledPolynomial provide full ring support and algebraic support for C and Int (i.e. addition, subtraction and multiplication of C, Int and polynomial types in any composition (thus, 3 operations in each of 3×3 kinds of interaction); LabeledPolynomial also provides support for Variable (thus, 4×4 kinds of interaction)). Long story short, x * x + 0.5 * x + 3 is supported by UnivariatePolynomial, NumberedPolynomial and LabeledPolynomial, but not by Polynomial.
4. Polynomial support algebraic operations like substitution or (anti-) derivative. All of it is already supported or is going to be supported by the other three. (It's not a problem here.)
5. Polynomial has a lot of integration in other logic like PiecewisePolynomial and suchlike. The other three were not tried to integrate.

Also PR into that module is welcome.

OK. Then I am going to replace the current Polynomial with my prototypes. (I'll try to save scalar operations and integrations of Polynomial everywhere that are already implemented.) I'll be able to do it in a while. Then I'll make a PR.

As for labeling, so far I am for using Map<Symbol,T> for passing arguments to multivariate environment. Map lookup is slower, than array lookup, but not by far. Also it is possible to transform Map into array using SymbolIndexer.

OK. I still did not have chance to look what Symbol is, I will learn about it. Thanks for the comment!

[altavir]

Symbol is just more general replacement for String it allows to use it in a safe way, also it allows to have different kind of symbols. Like symblols with default values etc.