# evaluating polynomials

0 Aufrufe
Direkt zur ersten ungelesenen Nachricht

### Martin Rubey

ungelesen,
13.08.2008, 02:56:1813.08.08
an fricas-devel
While trying to solve Perrin's problem, I noticed the following:

(30) -> poly := (a*b^2+c)::DMP([a,b,c],Integer)

2
(30) a b + c
Type: DistributedMultivariatePolynomial([a,b,c],Integer)
(31) -> eval(poly, [c=3.2])

2
(31) a b + 3.2
Type: Polynomial Float

The interpreter is coercing the DMP to a POLY, then evaluating it. Souldn't we
prefer a DMP([a,b,c], Float) here? Things might get complicated though:

(32) -> eval(poly, [c=x^2])

2 2
(32) x + a b
Type: Polynomial Integer

or even

(33) -> eval(poly, [c=x^2*a])

2 2
(33) a x + a b
Type: Polynomial Integer

Martin

### Martin Rubey

ungelesen,
13.08.2008, 03:10:3413.08.08
Another question:

do we want to maintain i-coerfn.boot (and probably add LAUPOL there), or try to
move the functionality there into the algebra and start to understand the
coercion algorithm?

(I think I'll be unable to do both)

Martin

### Bill Page

ungelesen,
13.08.2008, 09:36:3313.08.08
On Wed, Aug 13, 2008 at 3:10 AM, Martin Rubey wrote:
>
> Another question:
>
> do we want to maintain i-coerfn.boot (and probably add LAUPOL there),

No.

> or try to move the functionality there into the algebra and start to understand
> the coercion algorithm?
>

Yes. Understanding and improving the coercions done by the interpreter
is a critically important way to improve FriCAS from the point of view
of a new user.

> (I think I'll be unable to do both)

I am willing to help with this sort of project.

Regards,
Bill Page.

### Martin Rubey

ungelesen,
13.08.2008, 10:49:3213.08.08
"Bill Page" <bill...@newsynthesis.org> writes:

> > or try to move the functionality there into the algebra and start to
> > understand the coercion algorithm?
> >
>
> Yes. Understanding and improving the coercions done by the interpreter is a
> critically important way to improve FriCAS from the point of view of a new
> user.
>
> > (I think I'll be unable to do both)
>
> I am willing to help with this sort of project.

Great. I believe that one very rewarding point might be to properly document

Side effect would be to be able to fix bug 105...

-------------------------------------------------------------------------------

A different project might be to look at the documentation of the libalgebra
library of Aldor, find out about the design of the hierarchy of polynomials
there and in axiom and compare the two and design a better system for axiom.

I guess that this is a bigger task, however.

Martin

### Bill Page

ungelesen,
13.08.2008, 22:37:3513.08.08
Martin,

http://axiom-wiki.newsynthesis.org/SandBoxInterpIFunselBoot

Near the bottom you will find a possible solution for issue #105

On Wed, Aug 13, 2008 at 10:49 AM, you wrote:
>...

> I believe that one very rewarding point might be to properly document

Yes, this reference was very helpful. As you can see I incorporated

>
> Side effect would be to be able to fix bug 105...
>

Yes, after a lot of experimentation I think I am vaguely beginning to
understand some of the "black magic" and heuristics used in the
function selection process. As a result I have a (very preliminary)
proposal for how to solve this problem.

>
> A different project might be to look at the documentation of the libalgebra
> library of Aldor, find out about the design of the hierarchy of polynomials
> there and in axiom and compare the two and design a better system for
> axiom.
>
> I guess that this is a bigger task, however.
>

I am not too keen on digging into libalgebra, but in the wikipedia article:

I noticed the following comment:

"The Laurent polynomial ring R[X, X－1] is isomorphic to the group ring
of the group Z of integers over R. More generally, the Laurent
polynomial ring in n variables is isomorphic to the group ring of the
free abelian group of rank n. It follows that the Laurent polynomial
ring can be endowed with a structure of a commutative, cocommutative
Hopf algebra."

Now I realize that I am quite interested in the subject of Laurent
polynomials because I really am interested in the subject of Hopf
algebras! :-) Hopf algebras are especially interesting to me because
of their non-trivial co-algebraic properties. I am looking for almost
any good example of co-algebras to begin implementing something in
Axiom.

Unfortunately, so far I have found very little accessible to me on the
Internet that explains the relationship between Laurent polynomials
and Hopf algebra in more detail than the above quote. Does anyone have
a better reference?

Regards,
Bill Page.

### Martin Rubey

ungelesen,
14.08.2008, 03:51:5314.08.08
Dear Bill,

"Bill Page" <bill...@newsynthesis.org> writes:

> Martin,
>
>
> http://axiom-wiki.newsynthesis.org/SandBoxInterpIFunselBoot

Oh, that debug statement is very effective!

> Near the bottom you will find a possible solution for issue #105

Well, no, not quite there yet. Although I guess that penalizing EXPR may make
sense, I still do not understand the algorithm, and what the various functions
do. Most importantly: I'd like to see as little mention of specific domains as
possible, and, if necessary, they should appear only in one place. Ideally,
the necessary special values would be done in the algebra or in a separate file
like exposed.lsp.

I'm afraid, the only way to achieve this is hard work. Maybe you could draft
how the various functions are related, and a short description of their in- and
output.

Why can't we just assign *one* value to each type, and calculate the cost of a
signature according to that? hitListOfTarget seems to do something like
that:

-------------------------------------------------------------------------------
hitListOfTarget(t) ==
-- assigns a number between 1 and 998 to a type t

-- want to make it hard to go to Polynomial Pi

t = '(Polynomial (Pi)) => 90000

EQ(CAR t, 'Polynomial) => 300
EQ(CAR t, 'List) => 400
EQ(CAR t,'Matrix) => 910
EQ(CAR t,'UniversalSegment) => 501
EQ(CAR t,'RationalFunction) => 900
EQ(CAR t,'Union) => 999
EQ(CAR t,'Expression) => 1600
500
-------------------------------------------------------------------------------

but how are these magic numbers chosen? Expression is mentioned in many many
places (hand slected list, no idea what $Expression is compared to Expression): i-funsel.boot:296: putTarget(opNode, target := ['Kernel, ['Expression,$Integer]])
i-funsel.boot:345: ['Expression, $Integer] i-funsel.boot:349: a1 is ['Expression,b1] and a2 is ['Equation, ['Polynomial,b2]] => i-funsel.boot:379: target := ['Expression, a2] i-funsel.boot:383: target := ['Expression, a3] i-funsel.boot:686: EQ(CAR t,'Expression) => 1600 i-funsel.boot:783: tar and tar ^=$Expression => NIL
i-funsel.boot:784: [[[dc, $Expression, dc], [$Expression,'$], [NIL, NIL]]] i-funsel.boot:1421: AlgebraicallyClosedFunctionSpace ExpressionSpace Polynomial is even worse: i-funsel.boot:349: a1 is ['Expression,b1] and a2 is ['Equation, ['Polynomial,b2]] => i-funsel.boot:391: or a1 is ['Polynomial,.] or a1 is ['RationalFunction,.])) => i-funsel.boot:395: putTarget(opNode, target := '(Polynomial (Integer))) i-funsel.boot:400: a2 is ['Polynomial, D] => i-funsel.boot:431: a2 is ['Polynomial,D] => i-funsel.boot:436: a1 is ['Polynomial,D] => i-funsel.boot:440: a2 is ['Polynomial,D] and (a1 = D) => i-funsel.boot:460:mkRationalFunction D == ['Fraction, ['Polynomial, D]] i-funsel.boot:470: a is [D,uD] and MEMQ(D, '(Polynomial RationalFunction Fraction)) => i-funsel.boot:676: -- want to make it hard to go to Polynomial Pi i-funsel.boot:678: t = '(Polynomial (Pi)) => 90000 i-funsel.boot:680: EQ(CAR t, 'Polynomial) => 300 i-funsel.boot:975: mpolys := '("Polynomial" "MultivariatePolynomial" i-funsel.boot:976: "DistributedMultivariatePolynomial" i-funsel.boot:977: "HomogeneousDistributedMultivariatePolynomial") i-funsel.boot:1403: cat is ['PolynomialCategory, d, :.] => i-funsel.boot:1404: dom' := ['Polynomial, d] i-funsel.boot:1430: d := ['Polynomial,$Integer]
i-funsel.boot:1433: d := ['Fraction, ['Polynomial, $Integer]] i-funsel.boot:1731: t:= '(Polynomial (Integer)) Martin ### Martin Rubey ungelesen, 14.08.2008, 03:53:3214.08.08 an fricas...@googlegroups.com Sorry, forgot something important: if the testsuite doesn't show any problems, I think it still should go in. Maybe it encourages you to do further work? Maybe it would make sense to start a new branch? Martin ### Bill Page ungelesen, 14.08.2008, 09:04:0714.08.08 an fricas...@googlegroups.com On Thu, Aug 14, 2008 at 3:51 AM, Martin Rubey wrote: > > Bill Page writes: > >> Please take a look at this page: >> >> http://axiom-wiki.newsynthesis.org/SandBoxInterpIFunselBoot > > Oh, that debug statement is very effective! > >> Near the bottom you will find a possible solution for issue #105 > > Well, no, not quite there yet. What do you mean by "not quite there yet"? Do you see a problem with the result? > Although I guess that penalizing EXPR may make sense, I still do not > understand the algorithm, and what the various functions do. Most > importantly: I'd like to see as little mention of specific domains as > possible, and, if necessary, they should appear only in one place. > Ideally, the necessary special values would be done in the algebra or > in a separate file like exposed.lsp. > These are good ideas. > I'm afraid, the only way to achieve this is hard work. Maybe you could > draft how the various functions are related, and a short description of > their in- and output. > As usual, it is very hard to create "documentation" when there is none. I do not have any idea about how to do that. What we can read in the code is all that we know, the rest is just guess-work. It seems to me that since BOOT code is really quite readable, just re-presenting the same information in textual form does not add anything. Instead, I think email exchange like this is and online experimentation with the code is the best we can do right now. > Why can't we just assign *one* value to each type, and calculate the cost > of a signature according to that? Do you believe that it really is possible to associate a linear cost with each signature? Is "cost" really the criteria that one should use to choose a particular function? "cost" implies, maybe, something related to performance but from the point of view of the user perhaps the "principle of least surprise" is more important than performance. From this point of view the percieved complexity of the underlying types matters. > hitListOfTarget seems to do something like that: > > ------------------------------------------------------------------------------- > hitListOfTarget(t) == > -- assigns a number between 1 and 998 to a type t > > -- want to make it hard to go to Polynomial Pi > > t = '(Polynomial (Pi)) => 90000 > > EQ(CAR t, 'Polynomial) => 300 > EQ(CAR t, 'List) => 400 > EQ(CAR t,'Matrix) => 910 > EQ(CAR t,'UniversalSegment) => 501 > EQ(CAR t,'RationalFunction) => 900 > EQ(CAR t,'Union) => 999 > EQ(CAR t,'Expression) => 1600 > 500 > ------------------------------------------------------------------------------- 'hitListOfTarget' apparently only applies to the result type of functions. > > but how are these magic numbers chosen? I have no idea. I expect that it was mostly a matter of trial-and-error. I do not see any signs of a theory anywhere in the code. Do you have any ideas about how to change this? Perhaps we could create somekind of table and keep all of this information in one place, but right now I do not know enough about the code to even guess how such a table should be structured. Regards, Bill Page. ### Bill Page ungelesen, 14.08.2008, 09:11:4914.08.08 an fricas...@googlegroups.com On Thu, Aug 14, 2008 at 3:53 AM, Martin Rubey wrote: > > Sorry, forgot something important: > > if the testsuite doesn't show any problems, I think it still should go > in. Maybe it encourages you to do further work? > No, it does not encourage me very much since the particular problem that this change fixes does not affect anything that I really want to do with Axiom. However the participation of other people looking at this same issue is something that would encourage me to do likewise. > Maybe it would make sense to start a new branch? > Since at this time I cannot imagine doing much more than just "tweaking" the code a little more in the same manner, a new branch seems like overkill and is probably much more awkward than just playing with the web page. Regards, Bill Page. ### leh...@bayou.uni-linz.ac.at ungelesen, 18.08.2008, 11:26:2918.08.08 an fricas...@googlegroups.com On Wed, Aug 13, 2008 at 10:37:35PM -0400, Bill Page wrote: > Unfortunately, so far I have found very little accessible to me on the > Internet that explains the relationship between Laurent polynomials > and Hopf algebra in more detail than the above quote. Does anyone have > a better reference? That's shortly explained on http://en.wikipedia.org/wiki/Hopf_algebra : Any group algebra is a cocommutative Hopf algebra with comultiplication \Delta(g) = g\otimes g (i.e. it has only group-like elements) \eps(g)=1 and antipode S(g) = g^{-1} Another possibility (keyword "quantum groups") considers \IC^G (the space of complex valued functions, if G is infinite one takes continuous functions) with comultiplication \Delta f(x,y) = f(xy) (notice that \IC^G\otimes\IC^G = \IC^(G\times G)) \eps(f) = f(e) and antipode Sf(x) = f(x^{-1}); see e.g. S.Majid, Foundations of Quantum Group Theory. Perhaps you also find interesting papers by William R.Schmitt on Hopf algebras in combinatorics. regards, Franz ### Bill Page ungelesen, 18.08.2008, 22:35:1418.08.08 an fricas...@googlegroups.com On Mon, Aug 18, 2008 at 11:26 AM, Franz Lehner wrote: > > On Wed, Aug 13, 2008 at 10:37:35PM -0400, Bill Page wrote: >> Unfortunately, so far I have found very little accessible to me on the >> Internet that explains the relationship between Laurent polynomials >> and Hopf algebra in more detail than the above quote. Does anyone >> have a better reference? > That's shortly explained on > http://en.wikipedia.org/wiki/Hopf_algebra : > Any group algebra is a cocommutative Hopf algebra with comultiplication > \Delta(g) = g\otimes g (i.e. it has only group-like elements) > \eps(g)=1 > and antipode S(g) = g^{-1} > I hope that this is not too "stupid" a question ;-) but what might be a good representation in Axiom for the tensor product \otimes of two polynomials? > ... Thanks also for the additional references. Regards, Bill Page. ### leh...@bayou.uni-linz.ac.at ungelesen, 19.08.2008, 02:27:5619.08.08 an fricas...@googlegroups.com On Mon, Aug 18, 2008 at 10:35:14PM -0400, Bill Page wrote: > I hope that this is not too "stupid" a question ;-) but what might be > a good representation in Axiom for the tensor product \otimes of two > polynomials? In this case it's easy: just polynomials in two variables, \Delta(x^n) = x_1^nx_2^n. For general vector spaces one would have to take the cartesian product of two bases. regards, Franz ### Bill Page ungelesen, 20.08.2008, 16:44:5620.08.08 an fricas...@googlegroups.com The second example on page considers the polynomial ring K[X] in one indeterminate X. And claims that it becomes a coalgebra if we define \Delta(X^n) = \sum_{m=0}^n X^m\otimes X^{n-m} and \epsilon(X^n)=\begin{cases}1& \mbox{if } n=0\\ 0& \mbox{if } n\ne 0 \end{cases} extended linearly over K[X]. This gives a somewhat more complex structure. Is this structure not necessary for Laurent Polynomials to be a Frobenius algebra? Regards, Bill Page. ### Ralf Hemmecke ungelesen, 20.08.2008, 17:05:0020.08.08 an fricas...@googlegroups.com Hi Bill, with \usepackage{amsmath} (I think, it is that one), I would rather write that > \epsilon(X^n)=\begin{cases}1& \mbox{if } n=0\\ 0& \mbox{if } n\ne > 0 \end{cases} as \epsilon(X^n)= \begin{cases} 1& \text{if$n=0$}\\ 0& \text{if$n\ne0$} \end{cases} Search for "cases" in ftp://ftp.ams.org/pub/tex/doc/amsmath/amsldoc.pdf Ralf ### Bill Page ungelesen, 20.08.2008, 17:20:3920.08.08 an fricas...@googlegroups.com Yes that is prettier, thanks. I am guilty of cut-paste-and-edit from wikipedia article: Note in particular that I wanted to wrote: 0& \text{if$n\ne0$} rather than 0& \text{if$n>0\$}

in an attempt to generalize this definition for Laurent polynomials.

Do you think that makes sense?

Regards,
Bill Page.

### leh...@bayou.uni-linz.ac.at

ungelesen,
21.08.2008, 06:26:1121.08.08
On Wed, Aug 20, 2008 at 04:44:56PM -0400, Bill Page wrote:
> The second example on page
>
> http://en.wikipedia.org/wiki/Coalgebra
>
> considers the polynomial ring K[X] in one indeterminate X. And claims
> that it becomes a coalgebra if we define
>
> \Delta(X^n) = \sum_{m=0}^n X^m\otimes X^{n-m}
>
> and
>
> \epsilon(X^n)=\begin{cases}1& \mbox{if } n=0\\ 0& \mbox{if } n\ne
> 0 \end{cases}
>
> extended linearly over K[X]. This gives a somewhat more complex
> structure. Is this structure not necessary for Laurent Polynomials to
> be a Frobenius algebra?
I don't know Frobenius algebras, but throw in a few remarks.
On the one hand, this is a "quantum semigroup" type of coalgebra.
The polynomial ring is the monoid ring of the nonnegative integers
(group operation = addition, but written multiplicatively,
i.e. the free monoid with a single generator)
and
\Delta (\delta_x) = \sum_{yz=x} \delta_y\otimes \delta_z

If you do this on Laurent polynomials, you get an infinite sum
and it is better to write it in functional notation
\Delta f(s,t) = f(st).

On the other hand, this is the reduced incidence coalgebra of IN as an ordered
set, see the paper
Doubilet/Rota/Stanley: On the foundations of combinatorial theory VI,
Sixth Berkeley Symposium on Mathematical Statistics and Probability
and for more examples
Joni & Rota, Coalgebras and bialgebras in combinatorics,
Studies in Applied Mathematics 61

regards,
Franz

### Waldek Hebisch

ungelesen,
16.09.2008, 17:46:4816.09.08
Martin Rubey wrote:
>
> Another question:
>
> do we want to maintain i-coerfn.boot (and probably add LAUPOL there), or try to
> move the functionality there into the algebra and start to understand the
> coercion algorithm?
>
> (I think I'll be unable to do both)
>

We _have to_ do both. Currently i-coerfn.boot contains several
conversion functions which ideally would be available inside
algebra. But at least some functions in i-coerfn.boot are only
partial coercions -- they only work for some values. Also, the
final type may depend on value to be coerced (and not only on
its type). So it is not possible to express the same thing

In other words, we should try to move as much as possible to
algebra, but some parts for technical reasons must stay inside
interpreter and certainly we need to maintain i-coerfn.boot.
Concerning LAUPOL: we probably should have (or maybe already have)
retractIfCan form rational functions to LAUPOL. retractIfCan
is part of interpreter coercion algorithm.

More generally, interpreter tries to synthetize coecions from
corece, retractIfCan, convert, map and some special cases
in i-coerfn.boot. We should try to provide enough building
blocks in algebra and even in special cases it may be
possible to move part of them to algebra (AFAICS some
operations are done at Boot level because it is much
faster than using general algebra mechanizms). But much
of coercion code must remain part of interpreter. Actually,
I would like to make coercions in compiler smarter, so
for example machinery to synthetize complex coercions
form building blocks could be shared by compiler and
interpreter. But unless we want to dumb down the
interpreter we will need a lot code for special cases.

--
Waldek Hebisch
heb...@math.uni.wroc.pl

Allen antworten
Dem Autor antworten
Weiterleiten
0 neue Nachrichten