- #1

- 3,133

- 1,707

- TL;DR Summary
- I need to determine whether the eigenvalues of a large [itex]2n[/itex] by [itex]2n[/itex] block matrix are inside the unit circle, and have reduced the problem to an [itex]n[/itex]-dimensional non-linear eigenvalue problem.

I have a matrix [itex]M[/itex] which in block form is defined as follows: [tex]

\begin{pmatrix} A (\equiv I + 3\alpha J) & B (\equiv -\alpha J) \\ I & 0 \end{pmatrix}[/tex] where [itex]J[/itex] is an [itex]n[/itex]-by-[itex]n[/itex] complex matrix, [itex]I[/itex] is the identity and [itex]\alpha \in (0,1][/itex] is a parameter. The problem is to determine whether the eigenvalues of [itex]M[/itex] lie in the unit circle.

This comes from the discretization of a PDE, so [itex]n[/itex] is potentially on the order of 5000 and I'm looking for a numerical method. I would prefer not to have to find the eigenvalues of a [itex]2n[/itex] by [itex]2n[/itex] matrix if there's a more efficient way to solve an equivalent [itex]n[/itex]-dimensional problem.

By definition [itex]\lambda[/itex] is an eigenvalue of [itex]M[/itex] if and only if there exist [itex](p_1, p_2) \in (\mathbb{C}^{n})^2 \setminus \{(0,0)\}[/itex] such that [tex]

\begin{pmatrix}A & B \\ I & 0 \end{pmatrix}

\begin{pmatrix} p_1 \\ p_2 \end{pmatrix} = \lambda \begin{pmatrix} p_1 \\ p_2 \end{pmatrix}.[/tex] This leads me to the non-linear eigenvalue problem [tex]

\lambda(A - \lambda I)p_2 = -B p_2[/tex] with [itex]p_1 = \lambda p_2[/itex], which in terms of [itex]J[/itex] is

[tex]

\lambda(3 \alpha J - (\lambda - 1)I)p_2 = \alpha J p_2.

[/tex] Is there an efficient algorithm to solve this?

Alternatively, if the eigenvalues of [itex]M[/itex] can be determined directly from those of [itex]J[/itex] then so much the better.

\begin{pmatrix} A (\equiv I + 3\alpha J) & B (\equiv -\alpha J) \\ I & 0 \end{pmatrix}[/tex] where [itex]J[/itex] is an [itex]n[/itex]-by-[itex]n[/itex] complex matrix, [itex]I[/itex] is the identity and [itex]\alpha \in (0,1][/itex] is a parameter. The problem is to determine whether the eigenvalues of [itex]M[/itex] lie in the unit circle.

This comes from the discretization of a PDE, so [itex]n[/itex] is potentially on the order of 5000 and I'm looking for a numerical method. I would prefer not to have to find the eigenvalues of a [itex]2n[/itex] by [itex]2n[/itex] matrix if there's a more efficient way to solve an equivalent [itex]n[/itex]-dimensional problem.

By definition [itex]\lambda[/itex] is an eigenvalue of [itex]M[/itex] if and only if there exist [itex](p_1, p_2) \in (\mathbb{C}^{n})^2 \setminus \{(0,0)\}[/itex] such that [tex]

\begin{pmatrix}A & B \\ I & 0 \end{pmatrix}

\begin{pmatrix} p_1 \\ p_2 \end{pmatrix} = \lambda \begin{pmatrix} p_1 \\ p_2 \end{pmatrix}.[/tex] This leads me to the non-linear eigenvalue problem [tex]

\lambda(A - \lambda I)p_2 = -B p_2[/tex] with [itex]p_1 = \lambda p_2[/itex], which in terms of [itex]J[/itex] is

[tex]

\lambda(3 \alpha J - (\lambda - 1)I)p_2 = \alpha J p_2.

[/tex] Is there an efficient algorithm to solve this?

Alternatively, if the eigenvalues of [itex]M[/itex] can be determined directly from those of [itex]J[/itex] then so much the better.

Last edited: