[Axiom-math] Re: [Axiom-developer] Examples for good types

[Martin Rubey]

Dear all,

Please reply only to axiom-math.

I very recently discovered another example, which I find (personally) more
convincing.

Axiom has a (rather weak, but still) domain for symmetric functions.
The multiplication of two symmetric functions goes as follows:

(7) -> powerSum 4 * powerSum 2 * powerSum 2 * powerSum 2

3
(7) (4 2 )
Type: SymmetricPolynomial Fraction Integer

(i.e., it is represented as an integer partition, where equal parts are, as
customary, written as exponents.)

Symmetric Functions like determinants a lot, especially in Axiom:

m := matrix [[complete 1, complete 0],[complete 2, complete 1]]

+ (1) [] +
| |
(2) |1 1 2 |
|- (2) + - (1 ) (1)|
+2 2 +
Type: Matrix SymmetricPolynomial Fraction Integer
(3) -> determinant m

1 1 2
(3) - - (2) + - (1 )
2 2
Type: SymmetricPolynomial Fraction Integer

Note that Axiom uses the product in the ring of symmetric functions to compute
the determinant. To check, by Jacobi-Trudi the result should coincide with the
Schur function corresponding to the partition $(1,1)$:

(4) -> SFunction [1,1]

1 1 2
(4) - - (2) + - (1 )
2 2
Type: SymmetricPolynomial Fraction Integer


Martin

[Ralf Hemmecke]

(1/2)*x^2 + (1/3)*x + 3
Type: Polynomial Fraction Integer
%::Fraction(Polynomial(Integer))
2
3x + 2x + 18
-------------
6
Type: Fraction Polynomial Integer
When you read a maths book most of the equations are actually just
"icons". The real meaning of the equation is in the surrounding text
and context. Axiom carries that surrounding information in the type
whereas other systems focus on the "icons" and syntactic manipulations.

The above expressions can be assembled just from these 4 types (or
classes in SymPy): Add, Mul, Pow, Integer
what is the advantage to introduce more classes, like Polynomial
Fraction Integer or Fraction Polynomial Integer?
Because having the expression in the form of the 4 basic classes (Add,
Mul, Pow, Integer), everything else can be easily inferred from this.

Even mathematically
Fraction Polynomial Integer ---- QQ(Z[x,y,z,...])
and
Polynomial Fraction Integer ---- Q[x,y,z,...]
are not the same.
1/x lies in the first, but not in the second domain.
(By QQ I mean the operator to form the field of fractions.)

But there is something else with that example. Some people prefer the
first and some the second form. There is simply not THE simplest form.

Suppose you have the equations

3*x*p-1=0

and you want to solve it for p.

Clearly, the solution in QQ(Z[x]) is 1/(3*x).
The solution in Q[x] is... *no solution*.

Do you see that there is a difference.

Ralf

[Martin Rubey]

Dear all,

2
3x + 2x + 18
-------------
6
Type: Fraction Polynomial Integer

The above expressions can be assembled just from these 4 types (or classes in
SymPy): Add, Mul, Pow, Integer
what is the advantage to introduce more classes, like Polynomial Fraction
Integer or Fraction Polynomial Integer?

You get a normal form for free, keeping a lot of flexibility. Apart from that,
it is not correct that we introduce a class "Fraction Polynomial Integer". We
introduce a function "Fraction", a function "Polynomial" and a function
"Integer".

A normal form for "expressions" composed with Add, Mul, Pow, Integer does not
exist, if I am not mistaken. Using types, you can very easily restrict
"attention" to classes where normal forms do exist.

Maybe polynomials are a bad example, since they are so well known. I propose
another example: Algebraic Differential Equations. Although they do not allow a
normal form, it seems. But you can still test for zero.

It would not take so much time to implement a domain that deals with such
functions. And, I guess, in SymPy, you would not be able to distinguish an ADE
from any other "expression", because in SymPy, I guess, objects are not typed.

Another example, again: how would you multiply symmetric functions in SymPy? Or
Maple or Mathematica, if you prefer.

Because having the expression in the form of the 4 basic classes (Add, Mul,
Pow, Integer), everything else can be easily inferred from this.

I should add: it is indeed useful to have such a representation, too. (called:
ExpressionTree). Many things are easier to do with ExpressionTrees. But even
better is to have both, as we do in Axiom/Aldor.

Martin

[Martin Rubey]

Post by Martin Rubey
You get a normal form for free, keeping a lot of flexibility. Apart from that,
it is not correct that we introduce a class "Fraction Polynomial Integer". We
introduce a function "Fraction", a function "Polynomial" and a function
"Integer".

Ok, but a Fraction(a,b) is the same as Mul(a,Pow(b,-1)), and
Polynomial is the same as Add(Pow(x,2), Mul(2,x)) etc.

Yes, but what you have is not a normal form:

x^2 - 1 = (x+1)(x-1).

I am sorry, I have some questions regarding a terminology that you use. By
normal form, do you mean something like a canonical form?

Something like, yes. But definitively not a hash. A normal form is a
datastructure where equality of two objects implies equality of the
corresponding datastructures.

Somewhat weaker is the existence of a zero test: you can check algorithmically
whether a given object is the zero object, or, equivalently, whether two
objects are equal.

For general expressions, one has neither.

http://mathworld.wolfram.com/Differential-AlgebraicEquation.html
?

Nearly, for me, F should be a (multivariate) polynomial.

OK, but if I wanted to work with ADE - more than just multiply them together,

Ahem, how would you multiply them together? That's quite non-trivial, in
fact. Mind you: the result should have as solution the product of the solutions
of the given two equations!

I would need to introduce a new class ADE. The same is with polynomials, like
polynomial gcd is an algorithm, that only works for polynomials.

Another point for Axiom: in axiom, you define the gcd once. Of course, you are
free to define more efficient versions for certain domains, but you have a
default version that works for any Eucledian Domain.

Currently, in SymPy, the input to gcd is just an expression tree and it
checks, if it is a polynomial (and computes gcd), otherwise raises an
exception.

And in Axiom, you do not need to check.

How are you doing this in Axiom - are you converting from the expression tree
to introduce a type Polynomial, or do you work with the type Polynomial right
from the beginning?

You can do, as you wish. Sometimes it is more convenient to work with
expressions in the beginning, and coerce them to a polynomial later, sometimes
(in fact, most of the time) it is better to do all computations in the ring of
polynomials.

Post by Martin Rubey
Another example, again: how would you multiply symmetric functions in
SymPy? Or Maple or Mathematica, if you prefer.

What particular property do you want to get?

In Axiom you can say:

x := powerSum 5
y := powerSum 3

x*y

or

z := SFunction([5,3])

x*y*z

And, mind that "*" does not need to check in which domain the objects x, y and
z live. It just knows. And thus I can also use the usual determinant. I gave
the example onve already:

Many CAS's can do what is given above. To show the advantages of generic
programming using types, consider the following matrix of complete symmetric
functions, written in the basis of power sum symmetric functions:

m := matrix [[complete 1, complete 0],[complete 2, complete 1]]

+ (1) [] +
| |
(2) |1 1 2 |
|- (2) + - (1 ) (1)|
+2 2 +
Type: Matrix SymmetricPolynomial Fraction Integer
(3) -> determinant m

1 1 2
(3) - - (2) + - (1 )
2 2
Type: SymmetricPolynomial Fraction Integer

Note that Axiom uses the product in the ring of symmetric functions to compute
the determinant. To check, by Jacobi-Trudi the result should coincide with the
Schur function corresponding to the partition $(1,1)$:

(4) -> SFunction [1,1]

1 1 2
(4) - - (2) + - (1 )
2 2
Type: SymmetricPolynomial Fraction Integer




Martin

[Martin Rubey]

So how are you comparing x^2-1 and (x+1)(x-1) in Axiom? Is it the same, or
not?

Of course it is. But the point is, you can choose the representation. If you
know that your polynomials will have lots and lots of factors, and if you
mainly multiply your polynomials, you will be better off to work in the domain
Factored Polynomial Integer. Otherwise, you will probably prefer to work in
Polynomial Integer.

In SymPy, every expression is converted to a canonical form and then assigned
a hash. Then we just need to compare the hashes, thus resulting in O(1)
operation.

And how does the user tell the system which canonical form is suitable?

Post by Martin Rubey
Another point for Axiom: in axiom, you define the gcd once. Of course, you
are free to define more efficient versions for certain domains, but you
have a default version that works for any Eucledian Domain.

The same with SymPy, we also implement each algorithm exactly once.

Post by Martin Rubey

The same is with polynomials, like polynomial gcd is an algorithm, that
only works for polynomials.

ALthough I do not see how your gcd algorithm will work with *any* Euclidian
Domain... (Note that multiplication and addition do not necessarily have to be
compatible with the usual multiplication and addition of, say, integers, I
guess. Well, maybe they have to, I'm not sure right now.)

Post by Martin Rubey

Currently, in SymPy, the input to gcd is just an expression tree and it
checks, if it is a polynomial (and computes gcd), otherwise raises an
exception.

And in Axiom, you do not need to check.

Well, you need to check at some point, when converting from the expression
tree to the higher level rep.

But what if I don't start at all with an expression tree?

I probably know what you mean - in Aldor, you need to specify a type of each
variable in advance, but in Python, the type of the variable is inferred from
the right hand side.

For Axiom, you have to distinguish between the extension language (say, for
example, Aldor) and the interpreter. The interpreter tries hard to infer a
sensible type for the things you type in.

Post by Martin Rubey
Note that Axiom uses the product in the ring of symmetric functions to compute
the determinant. To check, by Jacobi-Trudi the result should coincide with the
(4) -> SFunction [1,1]
1 1 2
(4) - - (2) + - (1 )
2 2
Type: SymmetricPolynomial Fraction Integer

Maybe I am wrong, but it seems to me, that the advantage of doing it this way
in Axiom is that it allows you to implement each mathematical algorithm
exactly once, and possibly specifying a faster/better algorithm in special
cases.

That's one advantage, but certainly not the only one. I still do not know how
to implement a non-standard multiplication (as, for example, for symmetric
functions) in Mathematica, Maple, or Python. Would it be possible to implement
it in SymPy *without* modifying "Mul"? I.e., I want to write

powerSum 3 * powerSum 5

and obtain the symmetric function correponding to the partition (3, 5). And, of
course, I want to compute the determinant of a matrix of symmetric functions,
also. Maybe more precisely, if you create a new class "P", how do you tell
SymPy what

Mul(P(3), P(5))

means?

Martin

[Bertfried Fauser]

On 28 Mar 2007, Martin Rubey wrote:
Hi *;

its amazing how these things cook up in a periodic manner, my guess is,
that occassional users and newcommers are afraid of typed CAS and tend to
use untyped (esy going, quick solution) CAS.

Post by Martin Rubey
Another example, again: how would you multiply symmetric functions in SymPy? Or
Maple or Mathematica, if you prefer.

If you try to implement this in maple, as I did, you really really develop
desire to have a typed CAS at your finger tips, one of my motivations to
use AXIOM on a more frequent basis. (I could provide ugly examples in
maple where typing would prevent nonsense from being produced, ...) Even
more discusting you need to produce in untyped languanges your types
yourself, loosing tremendously working power for your actual subject.

Question> How do you distinguish in SymPy a tensor A and B of say second
and third rank? (I don't want to see a list of lists etc of the
components though)

Enjoy AXIOM :))
Ciao
BF.





% PD Dr Bertfried Fauser
% Institution: Max Planck Institute for Math, Leipzig <http://www.mis.mpg.de>
% Privat Docent: University of Konstanz, Phys Dept <http://www.uni-konstanz.de>
% contact|->URL : http://clifford.physik.uni-konstanz.de/~fauser/
% Phone : Leipzig [phone] Konstanz [phone]