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
--
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 [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
