Possible to optimize over many different constant terms?

[dlfivefifty]

I need to calculate the roots of

p(y) - z

for many different choices of z (which will then be plotted). Is this use case optimized for,say in the underlying fortran code?

[andreasnoack]

I don't think they are considering that in paper and I have only studied the source enough to be able to wrap it. The authors have been responsive to my questions so you should try to ask them if it is possible to optimize that case.

[thomasmach]

I am one of the authors. I thought about your problem. I think the answer is no, the code is not suitable for dealing efficiently with polynomials that vary in a_0. At the begin of the algorithm the companion matrix for the polynomial is factorized in a special compressed form. Unfortunately, already the first step (and all subsequent steps) of this factorization depend on a_0 (see (4.2) in the preprint http://www.cs.kuleuven.be/publicaties/rapporten/tw/TW654.pdf).

[dlfivefifty]

How about using the roots from one choice of z as a prediction for the next roots? I suppose it might still take n^2 ops though..

Sent from my iPad

On 7 Jan 2015, at 10:44 pm, Thomas Mach notifications@github.com wrote:

I am one of the authors. I thought about your problem. I think the answer is no, the code is not suitable for dealing efficiently with polynomials that vary in a_0. At the begin of the algorithm the companion matrix for the polynomial is factorized in a special compressed form. Unfortunately, already the first step (and all subsequent steps) of this factorization depend on a_0 (see (4.2) in the preprint http://www.cs.kuleuven.be/publicaties/rapporten/tw/TW654.pdf).

— Reply to this email directly or view it on GitHub.

[thomasmach]

Unfortunately, QR algorithms typically do not benefit from known approximations to the roots. Even using exact roots only reduces the computational costs by a factor of about two. Although we have not tested it for this specific algorithm.

If time is the main concern, then I would recommend to solve the problems in parallel by a trivial parallelization. Otherwise MPSolve might be an option, since it can use (to some extend) prediction of the roots.

[dlfivefifty]

Ok I'll look into parallelising. I haven't had good luck with @parallel, but those cases were either too simple or called LAPack, which is multithreaded. I'm assuming AMVW is not multithreaded?

Sent from my iPad

On 7 Jan 2015, at 11:21 pm, Thomas Mach notifications@github.com wrote:

Unfortunately, QR algorithms typically do not benefit from known approximations to the roots. Even using exact roots only reduces the computational costs by a factor of about two.

If time is the main concern, then I would recommend to solve the problems in parallel by a trivial parallelization. Otherwise MPSolve might be an option, since it can use (to some extend) prediction of the roots.

— Reply to this email directly or view it on GitHub.

[thomasmach]

Correct, AMVW is purely singlethreaded.