[Axiom-developer] CATS and Maple test suite

[root]

INTRODUCTION --------------------------------------------------------

I've been working for some time to construct a Computer Algebra
Test Suite (CATS). The idea came about because it is clear that
there is a lack of time and attention on cross-platform testing.
We should have available a range of problems with associated
math theory and verified results that every computer algebra
system can use for testing purposes. To this end I've been 
collecting test suites from various computer algebra systems and
running them thru Axiom. The lastest collection is the Maple bug
list posted by Vladimir. 

Of course there is no common syntax and so one of the problems
is that every integral has to be hand-written to match the likely
semantics of the original. This is a time consuming effort.
Furthermore there is no general mechanism for collecting results
(although I have been looking at automating regression testing
in Axiom) so result collection and summary are also hand operations.
Nevertheless, the process has completed the first phase of testing
and I've attached some summary statistics. Detailed results will
be included with the next release of Axiom.

For the next phase I've built a special purpose version of Axiom
with instrumentation in all of the integration routines. I plan to
classify each integral and associate it with the code as part of
the literate documentation. This will give us a basis for finding
bugs and corner cases. It will also give us working regression
test cases.


BREAKDOWN OF RESULTS -------------------------------------------------

There were 4865 integrals tested. Of these

  *> (5     0.10%) Missing Functions
  *> (1206 24.78%) Undefined Special Functions or untranslated functions
  *> (84    1.72%) Mismatched signatures of existing functions
  *> (158   3.25%) Badly Behaved Integrals
  *> (7     0.14%) Axiom Internal Errors
  *> (279   5.73%) Risch Algorithm Boundary Cases
  *> (2331 47.91%) Failed results
  *> (490  10.07%) Successful Results
  *> (305   6.27%) Indeterminate Results

Of the 4865 integrals the first three cases would not run. That
leaves 3570 tests. Of these there were 3097 (73.38%) integrals 
that had a potential pole in the path of integration making them
rather more difficult to compute.

We further break down the results. The number in parentheses is
the number of integrals of this class. One observation is that a
large number of these integrals involve the signum function. Axiom
does not have an integrable form of this function. Frankly, I'm not
sure how to integrate functions involving signum. It is hardly a
surprise that Maple gets these wrong.

On some of the functions I've given example integrals that exhibit
the behavior of their category.

Axiom has a robust implementation of the Risch algorithm done by
Barry Trager and Manuel Bronstein. Still, there are some corner
cases that are not implemented. We collected these under a
separate category so they will be useful for people who want to
investigate extending the algorithms. It is hardly a surprise that
Maple finds these hard to do.

These tests have uncovered 3 internal errors involving a total of
6 of the integrals. These will be investigated and fixed in a future
release.

Testing continues on the results that did not complete. Raising the
maximum time limit to 10 minutes has generated additional results.


(5) MISSING FUNCTIONS ---------------------------------------------------

These are apparently bogus function names. 

  *> (1) f 
  *> (1) op
  *> (1) product
  *> (2) elt

(1206) UNDEFINED SPECIAL FUNCTIONS OR UNTRANSLATED FUNCTIONS ------------

Maple has these functios in different forms than Axiom. Some of the special
functions have equivalent Axiom representations but Maple is much stronger
in special functions. Axiom has single-argument forms of some of these
functions but the translations were not clear.


  *> (2) airyAi -- 2 argument form
  *> (1) airyBi -- 2 argument form
  *> (2) argument
  *> (57) atan -- 2 argument form
  *> (26) ceil 
  *> (2) chebyshevT -- with fractional first argument
  *> (1) chebyshevU -- with fractional first argument
  *> (5) conjugate
  *> (8) Chi
  *> (78) csgn 
  *> (19) Dirac
  *> (11) Ei
  *> (2) EllipticE 
  *> (9) EllipticK 
  *> (4) EllipticPi 
  *> (1) erfc 
  *> (23) floor
  *> (3) frac
  *> (30) FresnelC
  *> (3) Fresnelf
  *> (1) Fresnelg
  *> (26) FresnelS
  *> (3) GegenbauerC 
  *> (6) HankelH1
  *> (8) HankelH2 
  *> (22) Heaviside 
  *> (2) hermiteH -- with fractional first argument
  *> (1) hypergeom 
  *> (4) KelvinKei
  *> (4) KelvinKer 
  *> (4) KummerU 
  *> (3) LambertW 
  *> (2) legendreP -- having 3 arguments
  *> (4) LegendreQ 
  *> (15) LerchPhi 
  *> (2) MeijerG 
  *> (31) polylog 
  *> (34) Psi
  *> (1) Re 
  *> (1) RootOf 
  *> (25) round 
  *> (2) Shi 
  *> (3) Ssi 
  *> (669) signum
  *> (11) StruveH
  *> (10) StruveL 
  *> (12) trunc
  *> (13) Zeta 

(84) MISMATCHED SIGNATURES OF EXISTING FUNCTIONS ------------------------

Axiom's integration routines return a Union of several types. 
In order to use the result in various other operations one branch
of the Union needs to be chosen. I have not done that here so these
are listed as though they were special functions with a missing
signature.

  *> (1) +
  *> (7) *
  *> (1) /
  *> (1) log
  *> (73) integrate
  *> (1) abs


(158) BADLY BEHAVED INTEGRALS -------------------------------------------

  *> (158) integrate: pole in path of integration

integrate(legendreP(0, z)/(z^2+3*z), z= 0..3,"noPole")


(7) AXIOM INTERNAL ERRORS -----------------------------------------------


  *> (1) internal error

   >> Error detected within library code:
   (construct (= left 0) (= right 2))
   is not a valid isolation interval for
   (+ (+ (- (** ? 4)) (* 2 (** ? 2))) -1)

in961:=integrate(log(z-1)*z/(z^2-1)^2, z= 1..%plusInfinity)


  *> (4) Cannot take first of an empty list

integrate(sin(z)*csc(z)*(1-1/(%i*z)^(1/2))^(1/2), z= 0..1,"noPole")


  *> (2) The function * with signature hashcode is missing from domain 
         Polynomial(OrderedCompletion (Integer)) 

integrate(a^z, z= 0..I*%plusInfinity)
integrate((1*z-3)/(2+(0*z-4)^2), z= %minusInfinity..1+I*%plusInfinity)


(279) RISCH ALGORITHM BOUNDARY CASES ------------------------------------

  *> (3) PFO::possibleOrder: more than 1 algebraic constant

integrate(tan(z)/sqrt(sin(z+%pi/4)), z= 0..1,"noPole")


  *> (1) Not integrable (provided residues have no relations)

integrate(((z^3-1)/(1+z))^(1/2)/z^2, z= 1..%plusInfinity,"noPole")


  *> (35) integrate: implementation incomplete (non-algebraic residues)

integrate(-(1-(I*z)^(1/2)/(1-I*z))^(1/2), z= -1..1,"noPole")


  *> (177) integrate: implementation incomplete (constant residues)

integrate(sin(z)^2*(1+z^(1/2))^(1/2), z= 0..1,"noPole")


  *> (22) Imaginary part is nonzero. Cannot retract.

integrate(sqrt(sin(2*z))/sqrt(cos(2*z)),z)


  *> (29) Function not supported by Risch d.e.

integrate(exp(-I*(I*z)^(1/2))/abs(z)^2, z= 0..1,"noPole")


  *> (12) integrate: implementation incomplete (residue poly has multiple 
          non-linear factors)

integrate(tanh(z)^(4/3), z = -1..1,"noPole")


  *> (0) integralBasis: possible wild ramification


(2331) FAILED RESULTS --------------------------------------------------

  *> (2033) "failed"

integrate(log(2-z^2)/(1-z^3), z= 0..1)


  *> (56) Sorry - cannot handle that integrand yet

integrate(erf((I*z)^(1/3)), z= -1..1,"noPole")


  *> (242) failed - cannot handle that integrand

integrate(sin(1/z)+(1-1/z^4)^(1/2), z= 0..%pi,"noPole")

(490) SUCCESSFUL RESULTS -----------------------------------------------

(305) INDETERMINATE RESULTS -------------------------------------------

There were some integrals that Axiom failed to complete given
the bounds on the allowed CPU time (about 10 minutes of execution).
Further effort will be applied to try to resolve these cases.

It may be that some portion of the integration algorithm either has
an infinite loop or has non-polynomial time behavior. We will attempt
to investigate both possibilities.

Tim