On 1/9/2013 7:32 PM, Raymond Toy wrote:
>>>>>> "Richard" == Richard Fateman <fateman at eecs.berkeley.edu> writes:
> Richard> well, not the general issue, but finding roots of polynomials.
> Richard> These programs tend to have difficulty when there are multiple roots.
> Richard> e.g. (x-3)^2.
>
> Richard> But we can remove multiple roots and count them by using sqfr.
> Richard> It is a feature of computer algebra that we seem to have neglected.
>
>
> Richard> Anyone willing to muck around with this? Maybe for bfallroots?
>
> How would this work if the root is some floating-point number?
OK, let's try this out for size.
You have a polynomial with coefficients that are either given as floats
or integers or rationals or bigfloats.
Interpret this as a polynomial with rational coefficients, which happen
to be given to you exactly, either
as numbers of type integer or rational, or as binary-float-numbers which
are also exact, namely fraction X 2^exp.
To reiterate, these are exact numbers. (They may not be the numbers you
are thinking they are, if you are
thinking 0.10 is the number --- it cannot be represented in binary float
-- but the number in the computer is, regardless,
some exact binary number).
Looked at it this way, a polynomial p(x) either has exact multiple roots
or not. The test is easy. If p(x) and p'(x), its derivative
wrt x have no common factors then it has no multiple roots. So compute
gcd(p,p').
If the gcd is 1, then you (and you can tell your root-finder program)
that there are NO multiple roots. (Oh, if gcd is not 1, it
tells you a polynomial whose roots have multiplicity >1; you can divide
out by this ,etc.)
Now once you have decided there are no multiple roots, you can use a
floating point program like allroots or bfallroots to
find the roots. Any rational or integer coefficients may be converted to
floats. I suppose that conversion could produce
a situation with multiple roots, and that would be distressing. So I'm
not sure how to entirely fix up the design.
> It
> seems that it wouldn't work well if you have a floating-point
> approximation to a root.
A floating point approximation to a root is a rational approximation to
a root.
There is an argument to be made that the gcd(p,p') should be done in
floating-point. People
have been worrying about what this might mean for about 15 years. I
don't know if anyone
has tried to make it work for polynomial square-free computation as a
prelude to root finding though.
RJF
> But don't know anything about how sqfr
> works, so I'm probably all wrong.
>
> Ray
>
>
> _______________________________________________
> Maxima mailing list
> Maxima at math.utexas.edu
> http://www.math.utexas.edu/mailman/listinfo/maxima