Re: Polynomials in arbitrary basis

[Vladislav Malyshkin]

Juan,
Right now I have to finish some other things, but in any case regardless of whether the final implementation will be done by me or by somebody else the "Summer_of_Code_Project" need to be written anyway, for the reason it requires an API to be be introduced, and as you know, API selection is a very "political" issue. Below I will try to write my first draft of Generalized Polynomials API proposal, the extended version of which will be added to the "Summer_of_Code_Project".
What do you think if I write API like below? With java-implementation available it will not be of much work either to integrate my existing java code, or re-implement it natively in octave (the code is simple, the most difficult part there - is unit tests, but my java code does have all the unit tests needed).
Vladislav

P.S. proposal example:
Currenty https://octave.org/doc/v4.0.3/Polynomial-Manipulations.html perform polynomial manipulation only in monomial (x^k) basis. This proposal to introduce octave class API with the goal to manipulate polynomials in arbitrary basis.

1. In arbitrary Q_k(x) basis (e.g. Chebyshev, Hermite, etc), a polynomial is represented as array coefficients
P(x)= a0*Q₀(x) + a1*Q₁(x) + a2*Q₂(x) +a3*Q₃(x) + ...
The coefficients a0, a1, a2 are represented as vector elements a = [a0, a1, a2, …, an]; vector (see https://octave.org/doc/v4.2.1/Creating-a-Class.html#Creating-a-Class example, note the order is different from https://octave.org/doc/v4.0.3/Polynomial-Manipulations.html where it is [an, ....,a2,a1,a0]  example)
An instance of GeneralizedPolynomial class to implement the following methods (like com/polytechnik/utils/BasisPolynomials.java)

(return types: s- scalar, [] - vector)

• [] convertToMonomialFromBasis(a) convert a polynomial in T-basis to the polynomial in monomial basis
• [] convertToBasisFromMonomial(a) convert a polynomial in monomial basis to the polynomial in T-basis
• s calculateSum(p,x) calculate sum p[k-1]Q_k(x)
• s calculateSumD1(p,x) calculate sum p[k-1] d/dx Q_k(x)
• s calculateSumD2(p,x) calculate sum p[k-1] d²/dx² Q_k(x)
• [] differentiate(p) differentiate a polynomial
• [] Integrate(p) integrate
• [] getQjQkLinearization(j,k) expand Q_jQ_k product as a sum c_mQ_m
• [] multiplyPQ(p,q) multiplies P*Q
• [] multiplyAxB(p,a,b) multiplies p*(ax+b)
• [[],s] sdiv1(p,x0) synthetic division p/(x-x0), returns quotient and remainder
• [[],[]] sdiv(p,q) synthetic division p/q, returns quotient and remainder
• [[]] expandNewtonBinomialLike(m,a,b) expand Q_m(a(x+b))  as sum c_kQ_k(x)
• [] getXQmoments(Qmoments) given <Q_k(x)> moments calculates <xQ_k(x)>
• [] getPQmoments(p,Qmoments) given <Q_k(x)> moments and polynomial P(x) calculates <P(x)Q_k(x)>
• [][] getConfederateMatrix(p) given a polynomial, calculate its confederate matrix (used to find polynomial roots)

2. The class GaussQuadratures calculates Gauss --type quadratures working in polynomial basis of GeneralizedPolynomial type.
This way input moments can be of <Q_k(x)> type, not necessary <x^k>. The methods

• .... about 10 methods from OrthogonalPolynomialsABasis.java ...

 

On 06/20/2018 03:11 AM, Juan Pablo Carbajal wrote:

Hi Vlad,

I suggest the next following steps:

A. If you have time to do it yourself:
1.A Read about linking java and the octave interpreter
https://octave.org/doc/v4.4.0/Java-Interface.html
2.A Prepare a package so we can help with the
testing.https://wiki.octave.org/Creating_packages, you can find some
slides and simple examples here
https://sites.google.com/site/octavecole/my-forms/OctaveHSR_2018.zip?attredirects=0&d=1
Also check other packages with java code, e.g. LTFAT
https://github.com/ltfat/ltfat/tree/master/blockproc

I have never interfaced with Java myself so I have no clue how much
work that is. It seems like it shouldn't be too much.

B. If you do not have time:
1.B Prepare a description of the project
https://wiki.octave.org/Summer_of_Code_Project_Ideas



On Wed, Jun 20, 2018 at 9:01 AM, Vladislav Malyshkin <address@hidden> wrote:

Juan,
generalized basis polynomial code is now also available from two places:

http://www.ioffe.ru/LNEPS/malyshkin/code_polynomials_quadratures.zip
(referenced from my https://arxiv.org/pdf/1510.05510 paper, page 30)
https://yadi.sk/d/AtPJ4a8copmZJ?locale=en , the file
polynomial_code.June_17_2018.zip

Vladislav

#sha1sum polynomial_code.June_17_2018.zip code_polynomials_quadratures.zip
d8dacf0c0573f850c38978a9fc97d70298e1fa68  polynomial_code.June_17_2018.zip
d8dacf0c0573f850c38978a9fc97d70298e1fa68  code_polynomials_quadratures.zip


On 06/17/2018 04:29 PM, Vladislav Malyshkin wrote:

Juan,
it is now available from https://yadi.sk/d/AtPJ4a8copmZJ?locale=en
the file  polynomial_code.June_17_2018.zip
Vladislav

On 06/17/2018 04:21 PM, Juan Pablo Carbajal wrote:

Hi,

There is little use of static zip sent around. Better set up a public
repository (gitlab, bitbucket, etc...) and share that.
I never linked java code to Octave, but since Java is a dependency of
Octave I can imagine it is very simple. Maybe you want to ask around
before investing time in re.writing your code.

I would say that the functionality is very important so if you do noot
have time to make a package of it, then we put it for the next summer
of code... or a bachelor student somewhere!

Regards,


On Sun, Jun 17, 2018 at 10:06 PM, Vladislav Malyshkin <address@hidden>
wrote:

Juan,
The code is java written, I do not have octave package. Only java.
Earlier version (bundled with other code) is available at
https://yadi.sk/d/AtPJ4a8copmZJ?locale=en file
AMuseOfCashFlowAndLiquidityDeficit.20_Sept_2017.zip
latest code version (minor API changes & code structure) is attached to this
e-mail: polynomial_code.zip (this is preferred version to use, I did not
release it yet, but changes from Sept 20 1017 version are really minor (few
functions renamed))
There are basically two API of interest to you:

Generalized polynomial basis functionality
com/polytechnik/utils/BasisPolynomials.java
Gauss--type quadratures calculation in generalized basis
com/polytechnik/utils/OrthogonalPolynomialsABasis.java

These API are implemented for Chebyshev, Legendre, HermiteE, Laguerre,
Shifted Legendre, Monomials  bases.
Polynomials operations are implemented in
com/polytechnik/utils/{Chebyshev,Legendre,HermiteE,Laguerre,LegendreShifted,Monomials}.java
with built-in selftest (e.g. run java com/polytechnik/utils/Chebyshev to
selftest the class).

There are not that much code there, it may be easier to re-implement that
code natively  in octave, rather than do any java-wrapper, especially
because my quadraures (not polynomial) code call few lapack subs converted
from fortran, it is probably better for octave to call Lapack subs
directly). All my code is under GPL.

Polynomials manipulation and Gauss--type quadratures calculation in
generalized basis is described in https://arxiv.org/pdf/1510.05510 ,
Appendix A & B, page 30.

Vladislav

P.S. To test the code
unzip polynomial_code.zip
javac -g com/polytechnik/*/*java
# then one can run selftest for, say, Legendre Basis & Quadratures
calculation in Legendre basis.
java  com/polytechnik/utils/Legendre
java  com/polytechnik/utils/OrthogonalPolynomialsLegendreBasis
# to run all selftests
java  com/polytechnik/utils/UnitTests

P.P.S. http://www.chebfun.org/docs/guide/chebfun_guide.pdf by Lloyd N.
Trefethen is good, but has different goals.

On 06/17/2018 02:49 PM, Juan Pablo Carbajal wrote:

Hi,

Sounds interesting. Could you share the repository where you host your code?
Also, you can create a package, compress it and provide an url, this
way anybody can install it from within octave

pkg install http://your.url

needs Octave >= 4.4


On Sat, Jun 16, 2018 at 9:39 PM, Vladislav Malyshkin <address@hidden> wrote:

Octave currently has polynomials manipulation functionality
https://octave.org/doc/v4.0.3/Polynomial-Manipulations.html
only in monomials basis: sum ckxk
In practice it is often very convenient to have polynomial represented in
other polynomials basis: sum ckQk(x)
where the basis  Qk(x) is orthogonal polynomials of some kind.
There is my implementation of polynomials manipulation functionality (and
Gauss-type quadratures calculation) in the basis of Chebyshev, Legendre,
Laguerre, Hermite bases.
The code is available under GPL and is java-written (however it will not be
much a problem to rewrite it in C/C++).
You can read about code at https://arxiv.org/pdf/1510.05510 see Appendix A &
B.
Let me know if you have any interest.
Vladislav
P.S. From the other alternative basis software I know only matlab-written
http://www.chebfun.org/ by Alex Townsend, but his project has different
goals.