all polynomial roots, how?

Is there a way to calculate all (i.e. complex and real) roots of a polynomial with cuda?

Or in other word, is there a way to calculate the eigenvalue( complexe and real) of general form matrix? I know there is an example under “NVIDIA Corporation\NVIDIA GPU Computing SDK 3.2\C\src\eigenvalues”, but which is seems to only calculate the tridiagonal symmetric matrix

I also did a simple search and found that CULA maybe can do so. But is there any free/open source to do so?

I say I “general form matrix” because I found how matlab calculate the roots on

which is actually the eigenvalues of a matrix like

6    72    27

     1     0     0

     0     1     0


P.S. I am using windows OS, not linux

you will want to calculate a lot of polynomials (at least thousands) in parallel, in order to fully utilize the GPU. So your problem is to calculate all eigenvalues of several thousands of small ‘general’ matrices. Up to my knowledge, CULA (or any other current CUDA library) does not support this sort of stuff (linear algebra for lots of ‘small’ matrices) so far. See also for a related topic.

You are probably more interested in the ‘poly’ function in MATLAB if you are looking to the find the roots of a matrix. The ‘roots’ function is only for vectors.

This is essentially a general eigenvalue problem which is a non-trivial task to perform on the GPU. I tried running this using a CULA accelerated version of MATLAB and was able to get a 3-4x speed up for large problems.

Normal MATLAB:

A = complex( rand(4096), rand(4096) );
tic; roots = poly(A); toc;
Elapsed time is 147.198273 seconds.

CULA Accelerated MATLAB:

A = complex( rand(4096), rand(4096) );
tic; roots = poly(A); toc;
Elapsed time is 54.026967 seconds.

I know you were looking for a free/open-source implementation but if you consider CULA it can help do what you are looking for.