evaluating polynomials
Martin Rubey
(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
Comments?
Martin
Martin Rubey
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
>
> 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
> > 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
the file i-funsel.boot. Maybe the following thread is helpful:
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
Please take a look at this page:
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
> the file i-funsel.boot. Maybe the following thread is helpful:
> http://groups.google.at/group/fricas-devel/browse_thread/thread/3b0db244f0562948/7133b4ee2b13055b#7133b4ee2b13055b
Yes, this reference was very helpful. As you can see I incorporated
your comments in SandBoxInterpIFunselBoot.
>
> 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:
http://en.wikipedia.org/wiki/Laurent_polynomial
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
"Bill Page" <bill...@newsynthesis.org> writes:
> Martin,
>
> 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. 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
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
>
> 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
>
> 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
> 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?
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
>
> 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
> 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?
\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
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?
Regards,
Bill Page.
Ralf Hemmecke
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
Yes that is prettier, thanks. I am guilty of cut-paste-and-edit from
wikipedia article:
http://en.wikipedia.org/wiki/Coalgebra
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
> 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?
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
>
> 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 Spad.
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