Hallo Waldek, that is typical AXIOM as a scientific not a software project: My CRFP package was a mere study of this idea of powers in the remainder ring (any idea of Plesken borrowed from factorizations over finite fields) and ideas of Schönhage, never intended to have any flavour of a product like software. Nevertheless, as it found its way into the AXIOM libraries, I am happy to work on it to improve and satisfies at least some requirements.
Am 01.06.2011 um 20:11 schrieb Waldek Hebisch: > 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. > Mit freundlichen Grüßen Johannes Grabmeier Prof. Dr. Johannes Grabmeier Köckstraße 1, D-94469 Deggendorf Tel. +49-(0)-991-2979584, Tel. +49-(0)-171-5503789 Tel. +49-(0)-991-3615-100 (d), Fax: +49-(0)-1803-5518-17745 -- 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.
