
From:  Sergei Steshenko 
Subject:  availability of 'eigensolve' source code from "An Iterated Eigenvalue Algorithm for Approximating Roots of Univariate Polynomials" article 
Date:  Sun, 23 Feb 2020 08:22:18 +0200 
Useragent:  Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.5.0 
Hello,
I became interested in finding roots of large order (hundreds or more) polynomials and doing all kinds of web search and selfeducation I stumbled upon "An Iterated Eigenvalue Algorithm for Approximating Roots of Univariate Polynomials" article by Steven Fortune. The article can be found e.g. here: https://pdf.sciencedirectassets.com/272313/1s2.0S0747717100X00971/1s2.0S0747717102905262/main.pdf?XAmzSecurityToken=IQoJb3JpZ2luX2VjEIv%2F%2F%2F%2F%2F%2F%2F%2F%2F%2FwEaCXVzLWVhc3QtMSJGMEQCIBpLqpLwnMuTRvBHh4dRy7emIB1adjOcZatRiC%2FJ%2F%2BC%2BAiA7PSvxLBTI6ioXV4CQMeNeK62g4EvYzmTFFxocPMYQwyq0AwhUEAIaDDA1OTAwMzU0Njg2NSIMTlMgu18P6DbgekhbKpEDMLIOgRJlOMR5EExG9AsT2sHq6Efj767VPfg5XWrMfXh3%2FRPY%2F779gO1z4fyj1DraFCG3Ymog%2F20ZS6kHF59ZyZqspFKpTv62x6nAb%2Bo6975dPXkiJaPnHW8CsBC0rZArKJ7fhGS2YiHlt4qp6Mm63kPndn3EbnUWiILwvSq3LPmpc1tCCNYppt7Jc0%2B3d6jvXJt5hy22Oc54Lonb600JPh%2BIvCadpWklH2ny5N3FMoVdZANvGUgbwrcx8fa1cZN1eIfw9DQss2W8hbRBNAxcaa%2B6FpVSek4sCHMNxY5gMEkyjmGCTBKd%2FBvd4DpNVeoEW7cCOiSpdSbOQrOJHUsm4GkkO0gxVZ9ZoXp3J8lQAibDl6PAZTOEtaCrtbcoLn3pFVPT4hvWmHDohAOaYTXzOeu4nuXxXGklvIwpM0h4ywOjDUOHYEEyR2YYXWdSOTfQdp6Lql6%2Ba8%2BHNaeqhkFhqZcoFTyjBMSUtT1kAtBG4B%2BfCMMCa0jJJXwtD9%2BIsaMa1xpqrcsI1%2Bv0KeJo63fSKX8wkMvH8gU67AG%2BxiZaPjWjmzrVdxsFVlyFZx%2BrCeLX8vPNj9wJHoRHhQEXvfG7mFJdAjhUZ7zP7TZhJKbnf4U0CBwRxFyrdvw70olezm7l3prNA3CeZTw0coO%2BFqX1mk3nSath39%2Fr3ZUZDSxqHKHcs%2B51AG%2BqQ88X0rwgDmtsaXRpZO%2B3XtbG9MoGOO4FmtTmCixZjUCRI9BsDVzY9Pdjsq8pElZQh3EV%2Bc81vM5DBcovFcKOfBZpI8qpfFSxE9oRWJjLSC1SMUDPwWIkvQfIfBNyVmCyJ%2F8LuE5dhvb3RE%2BxfhB5YfK2Dr8108LFxte1Z6bTnw%3D%3D&XAmzAlgorithm=AWS4HMACSHA256&XAmzDate=20200223T035138Z&XAmzSignedHeaders=host&XAmzExpires=300&XAmzCredential=ASIAQ3PHCVTY4ZZ2X6NY%2F20200223%2Fuseast1%2Fs3%2Faws4_request&XAmzSignature=b2787417358297a651bdbd01727ef2746811b32194018552aaa96ed72ca81600&hash=de657c03f39dec65b2da2fca600d625645ff052dedc081180392d7902bc6d4a4&host=68042c943591013ac2b2430a89b270f6af2c76d8dfd086a07176afe7c76c2c61&pii=S0747717102905262&tid=spdf527d7c5c875241eb8cbca4dfc3c0ef84&sid=8d4d10d92eb5d5442e79911572e2d52c763egxrqb&type=client .
If the ugly link won't work, I can provide the article (and it
can be found on netlib.org IIRC).
Anyway, according to the article performance of the proposed algorithm is quite good and it can deal with very large order (thousands) polynomials.
Among other things the article states:
"
4. Implementation
The algorithm is implemented in C++ using EISPACK (Smithet al., 1976)(or LAPACK (Andersonet al., 1995)) for floatingpoint eigenvalue computation and GMP(Granlund, 1996) for extendedprecision arithmetic. The source code, exclusive of libraries, is about 3300 lines of C++. The implementation accepts polynomials of arbitrary degree with either real or complex coefficients, with real and imaginary parts specified either as an arbitraryprecision integers or arbitraryprecision rationals. The implementation can approximate roots to any requested relative error. The interface—polynomial file format and available options—is similar to the interface of Bini and Fiorentino’s mpsolve,though not as extensive. The implementation is available by following the directions on the eigensolve web site (Fortune, 2001)
".
I failed to find the "eigensolve web site" and I failed to find the source code.
Does anybody have an idea where the source code can be found ? Or maybe there's already some better code for the task ?
Thanks in advance,
Sergei.
[Prev in Thread]  Current Thread  [Next in Thread] 