Re: "large" matrices, Eigenvalues, determinants, characteristic polynomials

*To*: mathgroup at smc.vnet.net*Subject*: [mg56492] Re: [mg56458] "large" matrices, Eigenvalues, determinants, characteristic polynomials*From*: Daniel Lichtblau <danl at wolfram.com>*Date*: Tue, 26 Apr 2005 21:52:57 -0400 (EDT)*References*: <200504260533.BAA14390@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

Grischa Stegemann wrote: > Dear group > > What is the difference between calculating Eigenvalues of a matrix M by > a) Eigenvalues[M] > b) Solve[CharacteristicPolynomial[M,x]==0,x] > c) Solve[Det[M - x IdentityMatrix[n]]==0,x] > ? > > Have a look at the following setting: > > n = 12; > M = Table[Table[Random[Real, {0, 100}], {n}], {n}] > > In this case all the 3 methods a, b and c give the same set of Eigenvalues > (neglecting small numerical differences and maybe using Chop). > > As soon as I increase n to at least 13 the result of method c gives a different > set of solutions. In particular method c gives 18 solutions instead of the > expected 13, where the 5 new ones always lay close together with small > imaginary parts. > > As far as I can see the problem occurs already when calculating the > characteristic polynomial: > h[x_] = Det[M - x IdentityMatrix[n]] > looks good up to n=12, for n>=13 this function looks very strange, including a > fraction and orders of x larger than n. > > This is particularly annoying since the actual problem I am dealing with > involves the calculation of a characteristic function like this: > h2[lambda_]=Det[M[lambda] - lambda IdentityMatrix[31]] > > where M[lambda] is a sparse 31x31 matrix having only the last row and the last > column as well as the main diagonal and the first secondary diagonals unequal > to zero. The dependence of lambda is an Exp[-lambda] in M[[31,31]]. > Of course I want to solve the transcendental equation > FindRoot[h2[lambda]==0,{lambda,...}] afterwards. But since the calculation of > the determinant already "fails" (giving really high order terms in lambda) I > have no chance to get any sane results out of FindRoot. > In this case it also doesn't make a difference whether I use > h2[lambda_]=Det[M[lambda] - lambda IdentityMatrix[31]] > or > h2[lambda_]=CharacteristicPolynomial[M[lambda],lambda] > which is only available in Mathematica 5 whereas I am using 4.0 or 4.1 very > often. > > Any suggestions, clarifications or hints are really appreciated. > Thank you, > Grischa For a matrix of approximate numbers, Eigenvalues will use Lapack functions. Solve will call on a Jenkins-Traub based rootfinder to obtain roots of the input given by CharacteristicPolynomial. Depending on the matrix, even finding the characteristic polynomial can be numerically unstable. Moreover, the step of finding its roots can likewise be problematic even if the polynomial, expressed in Horner form, is stable as a "black box" for numeric evaluation. Explicit computation of Det[...] will depend very much on internals of how it is computed. I think you are seeing the effect of it using a row reduction based approach when dimension is sufficiently high and input contains symbolic data. As to getting too many solutions, the explanation follows readily from what you have observed. Det is producing a rational function that, were it done in exact arithmetic, would have denominator exactly cancelled by numerator factors. The numeric root finder is passed the numerator which has degree too high, and any later checking in Solve will reveal that the denominator does not vanish at the roots (it merely "almost" vanishes). All this simply shows that symbolic methods will not be up to the task if input is not exact. Among your choices are: (1) Use exact arithmetic. (2) Use, say, PolynomialReduce or PolynomialQuotient/Remainder to figure out a "close" numerator of correct degree, that is, such that the fractional part may be discarded. (3) Use more refined methods based on optimization e.g. least squares, in order to get a better approximation of the determinant. (4) Compute the determinant by interpolation. Specifically, find e.g. Map[Det[mat/.lambda->#]&, Range[32]] and use these in InterpolatingPolynomial[mat,lambda] I do not recommend (3) because it will involve nontrivial programming and some familiarity with the relevant literature. Moreover it is not likely to be worth the bother as an improvement to (2) since already in computing Det you will have introduced numeric error. I would say either (2) or (4) are your best bets unless exact arithmetic is an option and does not turn out to be too slow. Daniel Lichtblau Wolfram Research

**References**:**"large" matrices, Eigenvalues, determinants, characteristic polynomials***From:*Grischa Stegemann <grix7-usenet@yahoo.de>