Non Symmetric Eigendecomposition and Matrix Dimensions Probable Issue

Hipparchus usage
1

Hello everyone,
I’m writing here because I’m using Hipparchus to develop a simple java application, to find beam structures damped natural frequencies and mode shapes (I’m basically writing a FEM application with beam elements). To accomplish this task I’m using EigenDecompositionNonSymmetric class.
During the usage of this class I found out that if my model is bigger than a certain size, the eigendecomposition fails to converge.
Actually, after few test I can say that if my model is bigger than 150 Degrees Of Freedom, there is no tolerance refinement that can allow to accomplish the eigendecomposition of the non-symmetric state matrix. I tried the epsilon values between 1.0e-12 to 1.0e-125 but there is no way to drive the decomposition to convergence. Instead if I use a model with maximum 66-70 DOF there is no problem with the decomposition routine, and the model is the same with less elements.
So, finally, after briefly explaining my problem, I would like to ask:

  1. is there any limitation with EigenDecompositionNonSymmetric and number of element of the matrix to be decomposed?
  2. Is it possible to enhance or force the convergence with many element matrix? If yes which could be the best strategies?

Thanks in advance to anyone who could answer.
Umberto

2

Hi @Umberto welcome

There are no explicit limitation on the size of the matrices. For eigen decomposition, I guess there may be numerical problems if some eigen values are close to each other.

The only current tuning parameter that is available is the epsilon value unfortunately and you already used that.

How does the convergence failure appear? Is it during the decomposition to Schur form or is it when extracting the vectors from the Schur form?

Also do you need both the eigenvalues and the eigenvectors or only eigenvalues? We currently only provide both, but if only eigenvalues are needed, there are dedicated algorithms that can do that.

Another possibility would be to use OrderedComplexEigenDecomposition which is based on a different implementation.

3

Hi luc,
Thanks for the reply.
The structures I’m trying to analyze are symmetric in shape, so, it is common to have eigenvalues with very similar values (tipically equal in pairs).
I understand this is not a good condition for thishipparchus eigendecomposition, isnt’it?
Unfortunately I need both Eigenvalues and Eigenvectors so, there are not many shortcuts I think…
Regarding the failure itself, I think the solver fails during the decomposition to Schur form, but for clarity i will report the stack trace of interest here below:

Exception in thread "main" org.hipparchus.exception.MathIllegalStateException: convergence failed
	at org.hipparchus.linear.SchurTransformer.transform(SchurTransformer.java:225)
	at org.hipparchus.linear.SchurTransformer.<init>(SchurTransformer.java:100)
	at org.hipparchus.linear.EigenDecompositionNonSymmetric.transformToSchur(EigenDecompositionNonSymmetric.java:269)
	at org.hipparchus.linear.EigenDecompositionNonSymmetric.<init>(EigenDecompositionNonSymmetric.java:123)
	at org.hipparchus.linear.EigenDecompositionNonSymmetric.<init>(EigenDecompositionNonSymmetric.java:110)

Finally, the matrices I work with are often non-symmetric. I assume that OrderedComplexEigenDecomposition class is akin to EigenDecompositionSymmetric class, which is not suitable to decompose non-symmetric matrices.
If there are alternative ways, please let me know.
In the worst case where there would be no solution to my problem, please indicate me which classes can exctract only the eigenvalues from the matrix to be solved.
Many Thanks.

Umberto

EDIT:
Just tested and it is very strange, maybe it can help troubleshooting why the Schur transform fail to achieve convergence:
bar decomposed in 22 nodes/21 elements of 1.25 m length. In this configuration, Shur transform convergence is achieved immediately, with the default epsilon, and result is:

  1. First Eigenvalue = 15.284867915214772
  2. Second Eigenvalue = 15.284932285755787

If one more node and thus one more element is added to the bar (23 nodes/22 elements now), maintaining the total bar length to 1.25 m, the Schur decomposer fail to achieve convergence.

EDIT 2:
Another little update: I tried to use the class ComplexEigenDecomposition and this is the failure stack trace:

Exception in thread "main" org.hipparchus.exception.MathRuntimeException: failed decomposition of a 54x54 matrix
	at org.hipparchus.linear.ComplexEigenDecomposition.checkDefinition(ComplexEigenDecomposition.java:456)
	at org.hipparchus.linear.ComplexEigenDecomposition.<init>(ComplexEigenDecomposition.java:167)

Which seems to be a failure due to the last check of the ComplexEigenDecomposition constructor, that verify if AV = VD…

4

Sorry if I’m bothering you again, but it seems I found the cause of the failure:
when two eigenvalues are too near, the decomposition is unable to ditinguish between the two and rather than giving the same eigenvalue with multiplicity two or giving just one of the two equal (numerically speaking) eigenvalues, it happily fails throwing exception.
So now the question that rises is:

  • is there a way to let the decomposer (be it OrderedComplexEigenDecomposition, ComplexEigenDecomposition or EigenDecompositionNonSymmetric) do its job without failing, being conscious that one of the eigenvalues will have multeplicity two, althought it will appear just once in the eigenvalues list?

Thank you very much to everyone will answer.

Umberto

5

I guess in this case we should probably put the eigenvalue twice in the list, according to its algebraic multiplicity.
I don’t know how to handle eigenvectors here, i.e. if we can find several different eigenvectors (which corresponds to the geometric multiplicity). We know geometric multiplicity is always between 1 and the algebraic multiplicity, but there are cases where geometric multiplicity is less than algebraic multiplicity (I encountered that once recently, with a small matrix that had an eignevalue with algebraic multiplicity 2 but geometric multiplicity 1.