Re: [eigen] Polynomial solver, eigenvalues of companion matrix and balancing

[Benoit Jacob <jacob.benoit.1@xxxxxxxxx>]

2010/1/18 Manuel Yguel <manuel.yguel@xxxxxxxxx>:
> Hello,
> I have written a class to compute the roots of a real polynomial.
> I build the companion matrix and compute its eigenvalues.
> You can see the code in the attached file (not a patch yet ... see the
> following).
> I have some problems with that method:
>
> A] When testing: I encounter almost systematic failure for polynomials
> with deg greater than 7 (see test file attached),
> therefore I wonder:
>
> 1) Do I use the right eigensolver ?

If you only want to support real polynomials, then yes.

> 2) Does the eigensolver balance the input matrix ?

Not as far as I can see.

> I have written some code to balance a companion matrix explicitly (and
> I am testing this stuff at the moment) but before investing more time
> in that direction I need to know if doing the balancing is redundant.

Ask Gael to be sure, but I don't think that we have this right now.

> B] A somehow related question is: the eigensolver make a copy of the
> matrix however, the companion matrix is sparse and for high degree
> polynomial this copy could be avoided.
> I have thought about writing the companion matrix class as a
> cwiseNullaryOp. Do I follow the right thread?

In all these decomposition algorithms, the work matrix is initialized
at the start by copying the input matrix into it. This is how these
algorithms work. If you want to preserve sparsity, you need a
completely different algorithm: this one won't preserve sparsity at
all. But I am not sure that companion matrices offer real
opportunities to take advantage of sparsity here.

Benoit

> P.S. I am also writing a solver with a Bézier bissection, it is
> claimed to perform faster.

Interesting!