Introduction to FriCAS/Axiom

[Alasdair]

I've just put into one file - and attempted to clean up - some introductory material I wrote about 7 or 8 years ago.  I've not added much, but I'm happy to consider this a constant work in progress, and add to it (or remove from it) according to people's wishes.  I would like to add some material about the interfaces: console, Texmacs, emacs+ifricas, the Jupyter interface and online at SageMathCloud etc.  Plus using it under Windows/Mac (but I'd need help with this, I use neither of 'em).

Anyway, I've attached the file for your criticism.

cheers,
Alasdair

[oldk1331]

FYI, there is also an Emacs extension axiom-environment [1], which is
very nice and it has Org-mode support: ob-axiom.

The Risch algorithm implemented in FriCAS is still incomplete, there are a few holes
in the mixed algebraic-transcendental case.

There is a right parenthesis missing in "(12) -> sum(1/k,k=1..100", page 4.
And a typo "dispkay => display" on page 4.

There is a right parenthesis missing in "(16) -> exp(%pi*sqrt(163.0)", page 5;
"(24) -> expand((x+2*y-3*z)^5", page 6;
"(36) -> solve[x^2-y^2=4,x*y=3],1.0e-10)", left parenthesis, page 7;
"(39) -> limit(x/sqrtx^2-1,x=%plusInfinity)", parenthesis missing, page 7;
"(106) -> expand((x-2*y+3*z)^3", page 20;
"”Axiom: The Scientific Computation System”", quotes don't match, page 23;
"”diff ”", quotes don't match, page 24;
"”difference”", quotes don't match, page 25.

Typo "ploat => plot" on page 14.

Generally speaking, this is a good introduction.

[1] https://bitbucket.org/pdo/axiom-environment

[Alasdair]

Thank you very much!  I thought I'd cleaned up the spelling errors and typos - but obviously not.  I'll get onto that soon.  Could you enlarge on the Risch algorithm?  I always assumed that Axiom had a complete implementation, but if not I'd want to be put right.  And of course I'd be happy to take on board any nice snippets which shows Axiom's superiority over other systems.

-Alasdair

[oldk1331]

> Could you enlarge on the Risch algorithm?  I always assumed that Axiom
> had a complete implementation, but if not I'd want to be put right.

First, according to my research, the theory of integration, aka Risch algorithm,
is still not complete.

Although Risch published his "algorithm" around 1970, it's very inefficient.
Bernoulli gives "algorithm" for rational function integration in 1703, but the
efficient algorithm is given by Lazard, Rioboo and Trager around 1990.
Trager gives a better ("rational") algorithm for pure algebraic function
integration in 1984. Bronstein "extends the major techniques of Trager
to handle elementary functions. If all the algebraic extensions are n th
root adjunctions, then the algorithm is 'rational'. Otherwise, we use a
simplified version of Risch's (1968) technique.", quoted from "Integration
of Elementary Functions, 1990".

So I think the "not all the algebraic extensions are n th root adjunctions"
case still doesn't have an efficient "rational" algorithm.

Second, in FriCAS code,  in intalg.spad, there are four cases failure of
"implementation incomplete": constant residues, irrational residues,
residue poly has multiple non-linear factors, has polynomial part.

Finally, there are lots of examples FriCAS can not handle and give
"implementation incomplete" error message, of course, these examples
all belong to the mixed algebraic-transcendental case:

integrate(sqrt atan x,x)  -- example from Bronstein

-- examples from Symbolic Integration Tutorial by Bronstein
((log x)^2+2*x*log(x)+x^2+(x+1)*sqrt(x+log(x)))/(x*(log x)^2+2*x^2*log(x)+x^3)

((x^2+2*x+1)*sqrt(x+log(x))+(3*x+1)*log(x)+3*x^2+x)/((x*log(x)+x^2)*sqrt(x+log(x))+x^2*log(x)+x^3)

(3*(x+exp x)^(1/3)+(2*x^2+3*x)*exp(x)+5*x^2)/(x*(x+exp x)^(1/3))

And there are more of this kind -- mixed algebraic-transcendental functions.

Please correct me if I'm wrong.

[Waldek Hebisch]

Alasdair wrote:
>
> Could you enlarge on
> the Risch algorithm? I always assumed that Axiom had a complete
> implementation, but if not I'd want to be put right.

Implementation in Axiom had substantial gaps. Basically,
decision procedure due to Risch, Rothstein, Davenport,
Trager, Bronstein, etc. called "Risch algorithm" has three
main stages.

Preparatory stage:
- choose top transcendental kernel
- write integrand as an algebraic function of top transcendetal
with coefficient depending on other kernels
- remove irrationalities from denominator

First stage (Hermite reduction):
- use integration by parts to remove multiple factors
from denominator

Second stage:
- find logarithmic part of the integral

After the fist two stages remaining integrand has trivial
denominator and also integral (if exists) must have
trivial denominator.

Third stage:
- handle the remaining part (called polynomial part). In
general this involves recursion and "simpler" version
of integration problem.

First stage, that is Hermite reduction was fully implemented
in Axiom by Bronstein. The second stage that is finding
logarithmic part was inplemented for transcendental functions
(in full generality) and for purely algebraic functions
having "simple" residues. For example, if you had
function of form

f = (c_1*log(a_1) + c_2*log(a_2))

where c_1 and c_2 were general algebraic constants and
a_1 and a_2 were purely algebraic functions, then Axiom
could not handle such function -- genaral c_1 and c_2
mean that residues are too complicated (not "simple").
FriCAS contains heuristic code which can handle many
such cases, but it is still quite far from general
algorithm for purely algebraic integrands.

For algebraic integrands which are not purely algebraic
both FriCAS and Axiom can not find logarithmic part.

The third stage that in finding "polynomial part" may
look trivial at first, but in fact biggest hole were
there: algorithm in Axiom was incomplete even for
purely transcendetal integrands (sometimes Axiom would
print weird error message, sometimes return unevaluated
integral). In FriCAS this part for purely transcendental
functions is complette. For functions where top
kernel is algebraic this part is unimplemented. In
fact currently is not needed: for purely algebraic
functions one can change variables so that already
Hermite reduction produces "polynomial part", so
separate code to get "polynomial part" is not needed.
For algebraic functions depending on a transcendental,
before computing "polynomial part" we need to find
logaritmic part. But since finding logaritmic part
is unimplemented we can not get to "polynomial part"...
There is somewhat tricky situation with mixed
functions where top kernel is tanscendental, but
coefficients are algebraic. In such case our code
for "polynomial part" is incomplete, in fact when
computing polynomial part we may recursively call
a variant of code computing logaritmic part, so
core problem for mixed functions basically is that
directly or after some recursion we may be forced
to determine logarithmic part of algebraic integral.

Let me add that is is quite easy to find integrals
which are not handled by our implementations of
Risch algorithm. However, beside Risch algorithm
integrator has a bunch of tricks to handle
common simple cases. So one have to pile a few
difficulties together -- still there are relatively
small examples showing incompeleteness.

--
Waldek Hebisch

[Kurt Pagani]

Very nice!

A link to Ralf's http://fricas.github.io/ in the "Online help" section
seems indispensable to me (especially the API).

Regarding Jupyter I've just started writing some documentation - that is
documenting the features which are special in connection with FriCAS.
May take some weeks ;)
To test the interface I've converted the (some 250) input files in the
distro to nb format (also some pages of the book). If you are interested
you'll find them @ https://github.com/nilqed/fricas_input/tree/master/nb
(Github allows rendering notebooks, a nice fature).

BTW Happy New Year
Best wishes
Kurt

[Waldek Hebisch]

oldk1331 wrote:
>
> > Could you enlarge on the Risch algorithm? I always assumed that Axiom
> > had a complete implementation, but if not I'd want to be put right.
>
> First, according to my research, the theory of integration, aka Risch
> algorithm,
> is still not complete.
>
> Although Risch published his "algorithm" around 1970, it's very inefficient.
> Bernoulli gives "algorithm" for rational function integration in 1703, but
> the
> efficient algorithm is given by Lazard, Rioboo and Trager around 1990.
> Trager gives a better ("rational") algorithm for pure algebraic function
> integration in 1984. Bronstein "extends the major techniques of Trager
> to handle elementary functions. If all the algebraic extensions are n th
> root adjunctions, then the algorithm is 'rational'. Otherwise, we use a
> simplified version of Risch's (1968) technique.", quoted from "Integration
> of Elementary Functions, 1990".

Bronstein's remark above is about algebraic case of Risch differential
equation (which is needed as part of full algorithm). Current code in
Axiom and FriCAS uses a different method: it "just" uses differential
equation solver. Current solver can only handle differential
equations with purely algebraic coefficients. However Singer
proposed a method that in principle should be able to solve
differential equations with elementary coefficients. IIUC
it it "rational", but I would expect it to be quite inefficient
because it replaces single equation over big field by a (probably
quite large) system of equations over smaller field. However
C Raab recently made progress with this, so at least some
systems should be efficiently solvable.

I also looked at this problem and I think I can adapt method
for transcendental case. I did not work out all details, but
basically the most problematic part is getting bounds in
so called "third case". Here, for elementary functions
finding boulnds is essentially the same as finding logaritmic
part of an auxiliary integral.

> So I think the "not all the algebraic extensions are n th root adjunctions"
> case still doesn't have an efficient "rational" algorithm.

The word "efficient" is freqently misused. Using it together
with "rational" may create wrong impression. Namely simplistic
reading of this is that one should avoid factorization and
introducing algebraic extensions. Now, avoiding _useless_
extensions helps efficiency. However factorization may
be faster than "rational" methods.

There are natural limitations to speed of integration
algorithm. First, a small integrand can have huge integral,
so integration may fail or be too slow simply because output
is too large. Second, size of intermediate quantities
is somewhat corelated to size of output. And basic
algorithtms (like polynomial multiplication) in practice
are at least quadratic, so for large output compute time
probably will be more limiting than size.

> Second, in FriCAS code, in intalg.spad, there are four cases failure of
> "implementation incomplete": constant residues, irrational residues,
> residue poly has multiple non-linear factors, has polynomial part.

"constant residues" and "has polynomial part" are about mixed
integrals (algebraic extension over transcendental) -- they
simply represent fact that mixed case is mostly unimplemented.
"irrational residues" in itself should be no longer a
problem. However, to decide that integral is nonelementary
we need to know all integer relations between residues.
In general this could be done via computation of splitting
field, but that is quite expensive procedure so FriCAS
does not try it. Instead FriCAS gives up if it can
not find integral and relations between residues are
too complicated (typically you will get the
"residue poly has multiple non-linear factors" message,
but also may print "impossible" (I thought that certain
problematic case can not exist, but it happens ...).
I am not sure if "irrational residues" may be reported,
but if yes then is is misleading now.


--
Waldek Hebisch

[oldk1331]

Thanks for your informative replies, Waldek Hebisch.
I have a question related about Risch algorithm and its
implementation in FriCAS.

I asked my math professor about Risch algorithm before,
he never heard of it and he seemed to not care about it,
because "numerical methods are enough, nobody cares
about symbolic results".  I want to know your perspective
of the future of Risch algorithm and its implementation in
FriCAS.

[Prof. Dr. Johannes Grabmeier privat]

To prove the importance of symbolic computations, certainly, symbolic integration is a bad, if not the worst example -- as for all practical problems numerical method will do as your professor claims.

But the beauty of symbolic methods certainly can be demonstrated by the Risch algorithm.

To my opinion: one should not play off one against the other aspect! So for a computer algebra system like FriCAS the completion of symbolic integration is a valid target, perhaps right now there are still more important target as improvement of usability for unexperienced users.

Am 11.01.16 um 10:23 schrieb oldk1331:

--
You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel...@googlegroups.com.
To post to this group, send email to fricas...@googlegroups.com.
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.

-- 
Mit freundlichen Grüßen

Johannes Grabmeier

Prof. Dr. Johannes Grabmeier
Köckstraße 1, D-94469 Deggendorf
Tel. +49-(0)-991-2979584, Tel. +49-(0)-151-681-70756
Tel. +49-(0)-991-3615-141 (d),  Fax: +49-(0)-3224-192688

[Alasdair McAndrew]

With due respect to the professor, who is no doubt a far finer scholar than me, the statement: "numerical methods are enough, nobody cares about symbolic results" is plain wrong.  Certainly from an applied point of view, numerical methods are the more important.  But symbolic algebra and calculus, and understanding them, are of great importance in extending our knowledge of both fields.  And I think it behoves all mathematicians, no matter their fields, to be open-minded about other areas.

[Waldek Hebisch]

Well, if you want numbers use numerical methods. However,
I care about formulas. And Risch algorithm is a powerful
method to produce new formulas.

Let me add a philosophical remark: thery behind Risch algorithm
deals with fundamental properties of symbolicaly defined
functions. In analogy to number theory it could be called
function theory, only most mathematicians hearing "function
theory" would imagine quite a different thing. Interestingly,
nonconstant functions in a sense are better behaved than numbers.
And results of such study seem to be more useful for computations
than results of number theory.

Concerning future of Risch algorithm, there is still theoretical
work to do. First, finding more efficient variant for elementary
functions. Second, extending algorithm to larger classes of
functions. Some generalizations are already implemented, for example
several parts writen by Bronstein deal with so called monomial
extensions. I added code to handle undefined functions, like:

(1) -> f := operator 'f

(1) f
Type: BasicOperator
(2) -> integrate(f(x)*D(f(x), x), x)

2
f(x)
(2) -----
2
Type: Union(Expression(Integer),...)

I wrote about method to find interal in terms of exponential integrals
and incomplete Gamma functions (with rational first argument). However
we would like to allow more Liouvilian functions as integrals,
in particular polylogaritms.

To put it differently, there is a long way to go. Most attention
will probably go into handling special functions (both as part
of integrand and as possible integrals). Certainly we want
to "complete" implementation for elementary functions and possibly
for larger classes. For algebraic functions probably most
important is work on other parts of FriCAS: we could greatly
improve speed for such integrals using better algorithms for
gcd, determinants, resultants, etc... For definite integrals
we need to improve limits. So beside Risch algorithm we need
to work on other parts to get a smootly working whole.

--
Waldek Hebisch

[oldk1331]

On Wednesday, January 13, 2016 at 9:57:59 AM UTC+8, Waldek Hebisch wrote:
> Interestingly,
> nonconstant functions in a sense are better behaved than numbers.
> And results of such study seem to be more useful for computations
> than results of number theory.

That's an interesting idea.

A few professors of my school teach symbolic computation (or rather,
symbolic computation software), few of them research it, that might
be the reason why my professor thought Risch algorithm like that.

> For algebraic functions probably most
> important is work on other parts of FriCAS: we could greatly
> improve speed for such integrals using better algorithms for
> gcd, determinants, resultants, etc...  For definite integrals
> we need to improve limits.

Can you elaborate more on current problems and possible
improvements of these algorithms?  So that I and others on this
group can help to improve.  One problem I know is about resultants:
there are PRS, SUBRESP, NSMP, at least some cleanup is needed.

[Kurt Pagani]

There is a nice MT on the subject:

https://www.nada.kth.se/utbildning/grukth/exjobb/rapportlistor/2009/rapporter09/terelius_bjorn_09095.pdf

and see this paper for current devlopments:
http://arxiv.org/pdf/1305.1481.pdf

BTW: numerics is to symbolics as classes are to instances ;)

Kurt