[enhancement]: Bypassing uncomputability issues about intervallinearalgebra.jl HOT 1 OPEN

thank you for your interest in the project and sorry for the long delay in answering, very busy week :D

I think your idea sounds very interesting and would make sense to include something like that in the package (maybe the names of the API can be negotiated :) ). I'll try here to summarize your proposal to make sure I understand correctly and ask a few clarifying questions.

If I understand correctly you are proposing that given a matrix M, find a non-interval matrix P and an interval diagonal matrix D so that M is contained in P*D*P^{-1}. I think this would be interesting to explore and maybe it might have some practical utilities e.g. to bound functions of matrices.

• Do I understand correctly, that the advantage of your proposed approach is that you are relaxing the problem as you are not requiring P to bound the eigenvectors, computing this factorization would be more efficient than verify_eigen or the approach proposed in the paper in #116 ? I have a couple of scenarios in mind where this could be useful

• I could not understand from your description whether the matrix M would be a matrix of floats (single points) or intervals. Which one did you have in mind? These would have slightly different problem formulations:

  • find P, D so that M ∈ PDP⁻¹ (starting from floating point)
  • find P, D so that M ⊆ PDP⁻¹ (starting from interval)
  • The reason I'm asking is because while the latter is more generals and algorithms working for that work also for the former, if you can assume that the starting point is a matrix of floats (or very small intervals), then you can generally find more performant algorithms, so I think it could be good to separate the two cases and start benchmarking only with the former could be an easier start.

• In your proposal you mention to compute P⁻¹, as you probably know matrix inversion cannot be computed exactly with floating point, if you want to work with intervals and want rigorous computations generally there are two options:

  • Compute P⁻¹ rigorously, meaning in the factorization P would be a matrix of floats, D an interval matrix and P⁻¹ an interval matrix guaranteed to contain the true inverse of P
  • Slightly modify the problem: Find P, D, R so that M ∈ PDR, where D is interval and P, R not. Then probably an approximate inverse of P would be good enough.

• Did you have in mind an algorithm on how to determine P and D? Can you link some papers I should link to better understand this issue?

If you have further questions / comments, do not hesitate to ping me.

from intervallinearalgebra.jl.