From: Shawn Rusaw <Shawn.Rusaw@comlab.ox.ac.uk>
Subject: What algorithm does Maple use for Sturm sequences?
Date: Tue, 03 Aug 1999 13:30:01 +0100
Newsgroups: sci.math.symbolic

I was just looking at the code for the function _sturmseq_
in Maple5R4 and am a bit confused about the method used
to calculate a Sturm sequence. I am familiar with the following
method to generate a Sturm sequence of f(x).

1. Reduce multiple roots to simple roots by dividing by gcd(f,f')
2. The terms of the sequence are {S_k} where
   S_0 = f
   S_1 = f'
   S_k = -(S_{k-1} mod S_{k-2})


Using this method, the final term is always a constant polynomial.

Maple seems to do things backward to some degree... 

1. S_0 = f (normalized by leading coefficient)
   S_1 = f'
   S_k = -(S_{k-1} mod S_{k-2})

If the last term happens to be a non-constant polynomial, then
all terms are
divided by the final term. You can look the
code with the following commands:

> readlib(sturm);
> interface(verboseproc=2);
> eval(sturmseq);

I am not familiar with this algorithm. Does someone have a 
citation, or know where I should look for more info? While I'm 
at it, the _sturmseq_ functions uses modified _rem_ and _quo_ 
functions in order avoid what is called a "fuzzy zero" in the 
online help. I would like to know what is meant by this as well.

Thanks,

--
Shawn Rusaw                      
Oxford University Computing Laboratory