2
$\begingroup$

I have a special type of companion matrix, where the "special" part is that each element in the matrix are matrices. For instance, the diagonal with "1":s is instead a diagonal with identity matrices, and so on... My question is if anyone knows of a solid algorithm for finding the eigen-decomposition of such a matrix? If you don't know the exact algorithm, perhaps you know of some work that has been done in the area?

If anyone is interested, I can clarify what my eigendecomposition will be used; AND this poses another problem, which is really the core problem I am facing.

I want to simulate a companion matrix (p x p), with each element being a matrix (n x n). The only restriction I have is that all eigenvalues must satisfy |λ|<1 . Ultimately, I would like to simulate the eigenvalues from (−1,1) , and then produce a companion matrix from that. I realize there might be (most likely are) multiple solutions, but that does not matter. I would settle for any solution. :)

My idea of solving this is to look at the general eigendecomposition of a companion matrix, simulate the eigenvalues, possible simulate the eigenvectors, and then reproduce the companion matrix.

Am I making any sense with this? I hope you understand the issue I have, and if not, please feel free to ask. As I said above, this area is fairly new to me...

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

You can get some savings with respect to the naive $O(n^3d^3)$ by using the semiseparable structure, but I don't think you can get anything faster than $O(n^3d^2)$ (stable) or $O(n^3d\log d)$ (maybe unstable). Algorithms for semiseparable matrices aren't exactly easy to start working with unless you work in numerical linear algebra, so unless $d$ is large, this isn't typically worth the trouble.

Inside Matlab there are some computations that use this problem (see polyeig), but as far as I know they run unoptimized QR.

Good Google search words for related literature are "companion linearizations of matrix polynomials". Though I'm afraid you won't find much in the direction you are interested in.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I agree; research on block companion matrices still looks to be underdeveloped. IIRC Robert Corless and colleagues have managed to build on previous work by Lancaster and others, but there's still room for better algorithms. $\endgroup$
    – J. M. isn't a mathematician
    Commented Dec 1, 2011 at 2:03
  • $\begingroup$ Thank you both for your inputs. This area is fairly new to me (stumbled upon it when doing research in financial mathematics), so the first problem is really finding out what to google! :) \\ I will look into "polyeig" and do some more searching. \\ Thank you!! $\endgroup$
    – ibbore
    Commented Dec 1, 2011 at 7:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .