From: fateman@cs.berkeley.edu   
      
   Divide and Conquer   
      
      Computer Algebra Systems and "division"  -- especially Maxima.   
      
      
   1.  Maxima's programs are generally written with an expectation   
   that the user does not know "abstract algebra". There are   
   reasons for this.   
      
      a.  Requiring the user to specify domains is an extra burden, and   
   one that is especially onerous for people in application areas   
   who don't know about Rings, Fields, Unique Factorization Domains,   
   etc.   
      
      b. Systems that DO require the user to be more formal are   
   unpopular outside the "application" area of pure mathematics.   
   CAS also have to make up some novel domain   
   names that no one uses in a regular mathematical context. Like   
   "Integration Result"   or "Expression". This adds to the burden.   
      Examples of such systems:  Axiom/Fricas, Sage.   
      
      c. Sometimes a program is written in some context, but then it   
   is used in another. Sometimes the program can be smoothly   
   extended to cover new contexts. For example, extending the   
   reach of programs like solve() and integrate() sometimes   
   by nice mechanisms "object oriented/ data dispatch"   
   can be considered.   
      
   2. There is a downside to being vague about domains.   
      People can ask a program   
   to do something that it tries to do and eventually fails   
   because the program was not written to allow or forbid   
   that particular input, and the program fails because somewhere   
   down the line a subroutine just cannot do what it has to do.   
   For instance, integrate("x^2",x)  integrates a string.   
   The answer, "x^2"*x  is either just what you deserve, or nonsense.   
   Should it be an error to integrate a string?   
      
   3. What does this have to do with division?   
      
   what is divide(5,3)? We are in general agreement that it is 1 remainder 2.   
   The obvious interpretation is division over the integers.   
      
   what is divide(1/5,1/3) ?  Maxima says 3/5  remainder 0.   
      
   what is divide(a/b,c/d) ?  It is  a*d/(b*c) remainder 0.   
      
      In fact, Maxima figures that here you are dividing in a field. In a   
   field the   
   remainder is always zero. (except for an error if you divide by 0),.   
      
   What about  divide(x,y)  ?   It seems we have a choice.   
   x/y remainder 0   
   0  remainder x   
      
     ( theorem:  divide s by t to get quotient q and remainder r. Then q*t+r=s)   
      
   both pairs satisfy that theorem.  Maxima happens to give [0,x]   
      
   If we are to have a unique result, there has to be some additional condition   
   on the q,r.  If s and t are polynomials in one or more   
   variables, then we can specify the variable, say x and require that   
   deg(r) < deg(t) in x.   
      
   If s and t  don't share the specified x   
   then quotient =0, remainder =s  works.   
      
   A basis reduction in several variables that looks for   
   the highest degree of the variable that is of highest   
   priority in general is not doing division. It does something else.   
      
   ....   
   Why does this matter in more subtle ways than might   
   not be entirely apparent?   
      
   Assume you have knowledge of a relationship or rule.   
   For example,  s^2+c^2=1.    (Think: sin and cos).   
      
   You have a complicated expression M in s,c, and other   
   terms.   
      
   By some choice of main variable (s or c) you can   
   divide M by (s^2+c^2)  to get quotient Q and remainder R.   
      
   Regardless of how you exactly did the division, we should be   
   sure you have   
      
        M = Q*(s^2+c^2)+R   
   because that's what division means.   
   We can now apply the rule and simplify M   to Q*1+R.   
   If it is in fact simpler.   
      
   Do this for powers of the rule, other rules, etc, and   
   you can simplify expressions, maybe.  This is a classic   
   approach in CAS, prominently used in Hearn's Reduce   
   starting in the 1960s. Also used in most other systems   
   eventually.   
      
      Note that we haven't said what happens if M is not a polynomial,   
   and our notion of division and the computer's program may   
   not correspond exactly.   But the rule idea based on   
   division is a way to simplify or otherwise transform.   
     Maxima's ratsubst() program is an implementation/extension of this idea.   
   So, in some ways, is Groebner Basis reduction.   
      
   ...............   
   Also, of course, division is a step in GCD computation.   
   As is the case with the sub-step of division,   
   this can be performed in various domains,   
     Maxima allows you to use the same command regardless. It doesn't   
   tell you what domain it is using, but attempts to derive it from the inputs.   
      
   Thus gcd(1/x,1/y)   returns  g= 1/(x*y).   Why?   
      
   divide(1/x,g) returns y with remainder 0, so g is a divisor of 1/x.   
   divide(1/y,g)  returns x with remainder 0, so g is a divisor of 1/y.   
   so maybe you are happy with that?   
      
   Maybe you would prefer g=1   because   
     A*1/x +B*1/y =g   has solution   
      0*1/x + y*1/y =1   
       and uh,   1 is "greater" that 1/(x*y)?   
      
   To return to our earlier point..   
      
   The premise in Maxima is that if some potentially useful meaning can   
   be extracted from a possibly nonsensical question, then it may give   
   some answer.   
      
     If you write a program with premature error checking,   
   you are cutting off the possibility that, some time later a programmer   
   will 'cover' that error with a solution.   
      
   You are free to write a system with different ideas, and it   
   is also possible to rein in Maxima to be more formal.  Indeed,   
   the internal Lisp programs in Maxima (say, the ones that   
   compute GCD in finite fields, work with algebraic extensions,   
   taylor series, etc etc  are, for the most part,   
     tightly bound to their abstract domains, in support ultimately   
   of the notion that the user should generally not need to   
   know abstract algebra to use a CAS.   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)