2
$\begingroup$

I have noticed arpack comes with a driver dsdrv1 that exploits symmetry of a real-valued matrix.

Is there a way to analogously exploit a Hermitian matrix in some way via z--- drivers?

The manual discusses Hermitian matrices in section 3.2.1, but I'm not sure if this analysis and proposal is already present in the ARPACK suite.

$\endgroup$
6
$\begingroup$

No, there is no specialized ARPACK routine for complex Hermitian matrices.

The ARPACK authors recommend using the znaupd routine for both Hermitian and non-Hermitian problems:

https://www.caam.rice.edu/software/ARPACK/UG/node43.html#SECTION00790000000000000000

Reasoning (direct quote from the ARPACK manual):

Occasionally, when using znaupd on a complex Hermitian problem, eigenvalues will be returned with small but non-zero imaginary part due to unavoidable round-off errors. These should be ignored unless they are significant with respect to the eigenvalues of largest magnitude that have been computed.

There is little computational penalty for using the non-Hermitian routines in this case. The only additional cost is to compute eigenvalues of a Hessenberg rather than a tridiagonal matrix.

For the problem configurations this software is designed to solve, the size of these matrices are small enough that the differences in computational cost are negligible compared to the major ${\cal O}(n)$ work that is required.

The relevant driver routines are zndrvX, with $X = 1 \dots 4 $.

Another library that appears to implement sparse Hermitian eigensolvers is PRIMME, http://www.cs.wm.edu/~andreas/software/

Yet another, bigger beast, is SLEPc (built on top of petsc). They, too, offer support for sparse Hermitian eigensolvers (user's manual).

$\endgroup$
  • $\begingroup$ This seems utterly bizarre. The Arnoldi-style algorithms for real symmetric matrix carry over trivially to Hermitian. In fact there is virtually nothing in linear algebra which is true and interesting for real symmetric matrices but not true for Hermitian matrices also. The suggested approach in 3.2.1 is (IHMO) just dumb. Reference: 30 years doing this stuff myself, starting before ARPACK was written! $\endgroup$ – alephzero Mar 28 at 0:01
3
$\begingroup$

If there are no algorithms specifically for sparse Hermitian matrices, a practical alternative is to convert the problem into double-sized real matrices.

Write the complex matrix-vector products in your problem, for example $Ax$, in real an imaginary parts $(A_r + i A_i)(x_r + i x_i)$, and then convert to real symmetric matrix products like $$\begin{bmatrix}A_r & -A_i \\ A_i & A_r \end{bmatrix} \begin{bmatrix}{x_r \\ y_i}\end{bmatrix}.$$ Note that since in a Hermitian matrix $A_i$ is skew-symmetric, the above real matrix is indeed symmetric, despite the minus sign.

This will double the storage for the matrices and multiply the solution cost by $2^k$ where $k$ is a small integer (typically 2 or 3) but it should always work.

In some applications of Hermitian eigenproblems, it turns out that $A_i$ is significantly more sparse than $A_r$, and this approach can take advantage of that situation using sparse matrix algorithms.

$\endgroup$
  • $\begingroup$ Interesting trick, hadn't seen that before. Especially when nnz(Ai) << nnz(Ar). Any related insights for the complex-symmetric case? Perhaps not so much for eigenproblems, as the resulting structure would be asymmetric (forced to use long recurrence methods like Arnoldi instead of short recurrence ones like Lanczos, right?). But maybe for linear system solution, you could block diagonal precondition with inv(Ar), then treat the imaginary part as a low rank perturbation? Just fishing. $\endgroup$ – rchilton1980 Mar 28 at 0:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.