Any O(N^2) method for finding the eigenvalues of J-Hermitian (complex Hamiltonian) matrix?

Question

I came across the problem of finding the eigenvalue spectrum of a general J-Hermitian (complex Hamiltonian) matrix. Is there any method (available algorithms) that would work faster than the "standard" methods for finding the eigenvalues of non-structured (no symmetry) complex-valued matrices (the number of flops is O(N^3), with N being the dimension of the matrix). In the picture below $\gamma_k$ are the complex Fourier-expansion coefficients of some given complex-valued functionHere is the part of the paper text where that matrix eigenproblem is defined with more details regarding its elements and structure

Answer 1

The complexity of the eigenvalue problem for complex Hamiltonian matrices has been studied in A Note on the Numerical Solution of Complex Hamiltonian and Skew-Hamiltonian Eigenvalue Problems. There is no improvement over the usual $N^3$ complexity, however, what you can achieve is an algorithm that respects the structure of the matrix, so that if $\lambda$ is an eigenvalue also $-\bar{\lambda}$ is one. In particular, the routine returns eigenvalues with real part exactly equal to zero.