Hi, I wonder if there's any way to convert the string representation of a found horner factorisation to codes. To be more specific, I'm looking for some functions similar to 'ccode' in Matlab or 'export' in Mathematica.
For example,
'x_1 (x_1 (x_1 (1.0 x_2) + 2.0 x_3) + 3.0 x_2 x_3) + 5.0' can give me

t1 = x_2 * x_3;
t2 = x_1 * x_2 + 2.0 * x_3;
t3 = x_1 * t2 + 3.0 * t1;
res = x_1 * t3 + 5.0;

which I can compile it in C.

Under ARM64 this error arises:
OSError: dlopen(/Users/jmichelf/github/multivar_horner/__pycache__/eval_poly_-757448186211189212.so, 0x0006): tried: '/Users/jmichelf/github/multivar_horner/__pycache__/eval_poly_-757448186211189212.so' (mach-o file, but is an incompatible architecture (have (x86_64), need (arm64e)))

Hi,

I would like to print the whole Horner polynomial with real coefficients (instead of c's).

This should not be too difficult but I am having some troubles dwelling into your code and your well thought but convoluted data structures.

Thank you!

At the moment, I have to evaluate the polynomial one at a time through this library. It is not possible to give multiple inputs at once through a 2D numpy array, and get multiple outputs in return.

Could this perhaps be more easily possible through the numba backend?

I tried to run one example in the documentation page, and it gave me a type error in one of the helper functions:
TypeError("coefficients must be given as numpy.ndarray")

Code below:

import numpy as np

from multivar_horner.multivar_horner import HornerMultivarPolynomial

horner_polynomial = HornerMultivarPolynomial(coefficients, exponents)
coefficients = [5.0, 1.0, 2.0, 3.0]
exponents = [[0, 0, 0], [3, 1, 0], [2, 0, 1], [1, 1, 1]]
horner_polynomial = HornerMultivarPolynomial(
    coefficients, exponents, rectify_input=True
)
horner_polynomial = HornerMultivarPolynomial(coefficients, exponents, keep_tree=True)

compiling the representation string takes extra time when constructing a polynomial class instance. make it optional (new kwarg).

float128 is not available under arm64 architecture
cf. vivarium-collective/vivarium-core#196

Optimal Horner Factorisation A* search:
The current heuristic to estimate the minimal number of required operations (lower bound) is to optimistic. This often causes every possible factorisation to be evaluated. For larger polynomials this makes this algorithm infeasible. -> Make the heuristic more accurate.

Attention: Tradeoff between accuracy of heuristic (how many factorisations are being skipped) and the time required to compute the heuristic for every node (is it cheaper to just try a factorisation?)

Optimise the factorisation such that it minimizes the numerical error during evaluation.
take the magnitude of the coefficients... into account during factorization.
The effects of Horner factorizations on the numerical error have been considered in

[3] J. M. Peña and T. Sauer, “On the multivariate Horner scheme”, SIAM journal on numerical analysis, vol. 37, no. 4, pp. 1186–1197, 2000.

[4] J. M. Peña and T. Sauer, “On the multivariate Horner scheme II: Running error analysis”, Computing, vol. 65, no. 4, pp. 313–322, 2000.

add the newton raphson method to the implementation.
as sample code in example.py not in code. (<- simple algorithm and often personal adjustments useful for users)

optimise factor evaluation in order to save instructions ('factor factorisation'):
a monomial factor consists of scalar factors and in turn some monomial factors consist of other monomial factors
-> the result of evaluating a factor can be reused for evaluating other factors containing it
-> find the optimal 'factorisation' of the factors themselves
-> set the factorisation_idxs of each factor in order to link the evaluation appropriately

idea:
choose 'Goedel IDs' as the monomial factor ids
then the id of a monomial is the product of the ids of its scalar factors
find the highest possible divisor among all factor ids
(corresponds to the 'largest' factor included in the monomial)
this leads to a minimal factorisation ('factorisation tree') for evaluating the monomial values quickly

factorize independently of the coefficients.
let the first part of the value array be equal to the coefficient array. it can then be easily replaced without affecting the factorisation

a user might want to represent and evaluate multiple polynomials (different coefficients) with the same properties.
This is useful e.g. for gradients (= partial derivative polynomial for each dimension)!
add support for 2D coefficient arrays and adjust Numba jit compilation.
then the gradient can be returned as a single polynomial with the same exponents but 2D coefficients or multiple distinct polynomials with smaller exponent matrices.
The naivel canonical polynomial evaluation for 2D coefficient arrays can benefit from reusing intermediary results.
If someone wants to work on this let me know here. I have example code ready for this already.

add option to improve naive representation by also compiling a recipe for evaluation.
thereby avoid the unnecessary operations of the matrix representation
factorise monomials (improved evaluation of monomials, reuse value)

currently the factorisation progress has been coded in highly unefficient OOP style.
move towards more pythonic functional paradigm
use data classes as containers for the properties
use only functions processing data classes (as input arguments)

factorisation is comparatively slow since coded in pure python.
find ways to optimise.
e.g. code time critical factorisation modules in C(++), parallelisation...

after building a factorisation tree for the factors themselves (#12)
use its structure to cleverly reuse storage space
-> use compiler construction theory: minimal assembler register assignment, 'graph coloring'...

Please add to the paper code showing how to print out the human-readable representation of the Horner polynomial.

In an empty directory, I create a ./venv folder and run the following:
python -m venv .\venv\

I am on Python 3.8.10 on a Windows 10 machine.

I update pip to the latest version with:
python -m pip install --upgrade pip

I am on pip 22.1.2

I then run:
pip install multivar_horner[numba]

Running pip freeze shows the following:

llvmlite==0.38.1
multivar-horner==3.0.0
numba==0.55.2
numpy==1.22.4

I then open up a python command line, and attempt to import the Multivar Polynomial, as shown in the Getting Started docs:

(venv) PS F:\Downloads\HornerTest> python
Python 3.8.10 (tags/v3.8.10:3d8993a, May  3 2021, 11:48:03) [MSC v.1928 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.

>>> import numpy as np
>>> from multivar_horner.multivar_horner import HornerMultivarPolynomial
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "F:\Downloads\HornerTest\venv\lib\site-packages\multivar_horner\__init__.py", line 2, in <module>
    from multivar_horner.classes.abstract_poly import load_pickle
ModuleNotFoundError: No module named 'multivar_horner.classes'
>>>

Please let me know what I might be doing wrong here!

input validations should raise Exceptions!

add new function (feature) to compute all optimal horner factorisations of a given polynomial.

The existing A* search has to be adapted to not terminate once the first full factorisation has been found, but instead collect all fully factorized optimal solutions until the next best factorisation in the heap has a higher cost estimate

Attention: do not remove an entire factorisation subtree, but just one realisation each time!

For common polynomials the optimal factorisations can be precomputed and stored. This data can perhaps also be used to learn better heuristics for factorizing more optimally in less time.

cf. https://github.com/jannikmi/extremitypathfinder/blob/master/.github/workflows/build.yml
dont forget write permission

Is there any specific reason why the method cannot be implemented for complex coefficients or the polynomial cannot be evaluated at complex values?

I found a few minor things in the paper that should be improved:

• The sentence "Representing multivariate polynomials of arbitrary degree also in canonical form, computing derivatives of polynomials and evaluating polynomials at a given point are further features of the package." doesn't read well; the problem is the "also". I would rephrase the entire sentence to something like "In addition, the package allows to/offers..."
• "can be helpful always when" should instead be "can be helpful whenever". In addition, perhaps I would change the "can be helpful" to "is useful" or so.
• "The polynomial p is the sum of 5 monomials" There are only four monomials.

This issue is part of the JOSS review (openjournals/joss-reviews#2392).