We had problem with complex polynomial root finding: it is slow
and used to be inaccurate. I have fixed accuracy problem, so
now roots should be quite accurarate. However, finding them
still is slow: we use Groebner bases to transform degree n
complex plynomial essentially into degree n^2 real polynomial.
This is inherently expensive.
We have another packege for finding root: CRFP by Johannes
Grabmeier. My experiments indicate that usually it is faster
than current procedure and there is some potential for speeding
it up. But currently it is not nice to use: one needs to set
needed accuracy of floating point operations before use and if
accuracy is too low the package goes into infinite loop.
So CRFP would requre some work to make it generaly usable.
Also, one of main operations in CRFP is approximate GCD
(called 'divisorCascade' there) and apparently it is hard
to compute it really quickly.
I also looked at more conventional methods for root finding
and I must admit I am somewhat dismayed with my findings.
One would expect that polynomial root finding is classical
topic and the methods should well worked out and well described.
But it seems that most descriptions ignore crucial problem:
how to ensure convergence. While authors of a method show
examples where method work, if method is mentioned on other
text the other text frequently gives examples where method
does not work. My experiments indicate that just using
what is described (and filling in missing parts with
"reasonable" guess) may fail to work in cases where authors
claimed that method works. So it seems that to get robust
root finder one has to essentially work out from scratch
the most importamt parts. Related to this is issue of
precision of arithmetic operations: most work on root
findung uses machine float. This is fast, but there
are limits to things which can be computed using machine
accuracy. Again, there are examples where machine
arithmentic gives widely wrong results, and examples
which at first glance are too hard but work well
using machine accuracy, but no general theory...
Bottom line is that currently we have accurate but slow root
finder. Conventional root finder should be much faster, but
it is tricky to make them work reliably, so it will take
some time before we get a good one. In the mean time we
could try to swith to CRFP, but I am not sure if it is
worth to invest time in it.
--
Waldek Hebisch
[email protected]
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/fricas-devel?hl=en.
