3

Are there any known issues (such as precision issues) with $\mathsf{MATLAB}$ eig and charpoly functions for large enough $\{-1,0,+1\}$ matrices?

Even if I change $1$ or $2$ entries between matrices would it be able to find the accurate eigenvalues and characteristic polynomials? I am using size less $40\times40$.

My matrices are full rank and symmetric. The condition number of the matrices seems in mid $100$s to $10^{15}$ while absolute value of sum of rows/columns is same.

If I can get char poly that is good enough for me.

Turbo
  • 149
  • 3
  • 3
    It depends a lot on the properties of the matrix itself, not just matlab's eig. For example, X = horzcat(-ones(10, 1), vertcat(eye(9), (1:9)==9)); disp(X); eig(X) has all zero eigenvalues, but eig would give them on order of $10^{-3}$. I believe you can expect eig to be accurate when the matrix of eigenvectors $X$ has a low condition number, and error in eigenvalues would be on order of $\epsilon_{\mathrm{mach}} \kappa(X)$. – Kirill Dec 25 '15 at 03:18
  • 2
    Can you add any extra information about your matrices, anything at all? Knowing elements are in ${0,\pm1}$ isn't so much — it depends more on how sensitive they are to perturbations, and there are matrices in matlab's gallery that have sensitive eigenvalues but consist of ${0,\pm1}$. There is also a related question here: http://scicomp.stackexchange.com/questions/17517/diagonalization-of-matrix-omitting-small-matrix-elements – Kirill Dec 25 '15 at 03:20
  • 1
    Condition number of the matrix itself or the matrix of eigenvectors? If the matrix is symmetric (or, in general, normal), the condition number of $X$ would be precisely 1, in which case eig should be accurate. – Kirill Dec 25 '15 at 03:39
  • 2
    Please put all the relevant information you have into the question itself (not the comments), so that the question is clear, direct, and self-contained. That way the question would be helpful also to other people that have the a similar question. [Side note: krill → Kirill] – Kirill Dec 25 '15 at 03:58

2 Answers2

2

If, as you say, you only really need the characteristic polynomial of your matrices, and not the eigenvalues (solving for the roots of the characteristic polynomial doesn't in general give accurate eigenvalues), and since your matrices are really quite small ($40\times40$) and have only integers, it might be sufficient to just use matlab's symbolic manipulation to calculate the characteristic polynomial exactly, like so:

>> charpoly(sym(gallery('grcar', 10)))
ans =
[ 1, -10, 54, -200, 553, -1176, 1935, -2424, 2211, -1328, 401]

which sidesteps any issues with numerical accuracy of eig. Obviously the (integer) coefficients of the characteristic polynomial can be quite large.

Kirill
  • 11,438
  • 2
  • 27
  • 51
  • I use syms x; polyA = charpoly(A, x); where A is the matrix of interest (is this good enough)? coefficients are very large – Turbo Dec 26 '15 at 05:56
  • @Turbo I'm sorry, I don't understand. Did it work? – Kirill Dec 27 '15 at 01:30
  • I use command $\mathsf{syms}\text{ }x$ to say $x$ is variable. I define matrix $A$ and then use $\mathsf{polyA} = \mathsf{charpoly}(A, x)$ to compute characteristic polynomial of $A$. Is this good enough? I do not know how to check for large matrices. – Turbo Dec 27 '15 at 01:39
2

Kirill's suggestion to use symbolic linear algebra is on-point. Another approach is to work out the characteristic polynomial over a number of finite fields, then use the Chinese remainder theorem to reconstruct the characteristic polynomial over $\mathbb{Z}$. Finite field linear algebra does not suffer from the same kinds of numerical problems as you'll run into with eig.

Community
  • 1
tmyklebu
  • 372
  • 1
  • 5