A Fast Method For Computing The Purely Imaginary Eigenvalues Of Hamilton Matrices

Using Vector Fitting, one can generate a very accurate model for the SI analysis, but sometimes, the model is not passive. At this time, one must detect the model's passivity by the existence of the purely imaginary eigenvalues of the so called Hamiltonian matrix. The scale of this kind of matrix can be so large that it can reach to billions. So we must get rid of the traditional eigenvalue algorithms which desire O(n3) flops and O(n2) memory usage.In[26], the author described an method to compute all the purely imaginary eigenval-ues. The purely imaginary eigenvalues, which are the we only care about, usually have a low rate in number in the eigenvalue spectrum. So we can hope the saving of time when focusing on the calculation just these purely imaginary eigenvalues. As described, this algo-rithm can limit the arithmetic operations to O(c·d·n) and physical memory to O(n), where c is a case dependent constant and d is the number of purely imaginary eigenvalues. But this may depend on the distribution of the eigenvalue spectrum, the dense distribution of eigenvalues near the imaginary axis can slow down the process very much, for the constant c can be extremely large.Actually, when the eigenvalues of Hamiltonian matrix H distribute densely nearby the imaginary axis, the constant c will grow to be extremely large. So if we can move these eigenvalue away from the imaginary axis, we can hope for the increasing of efficiency of the algorithm. With the help of a intermediate matrix constructed by linear fractional transformation, we get this goal.Firstly, we will introduce this linear fractional transformation:Proposition 0.1 Suppose 1 is not the eigenvalue of H, the map C←(H+I)/(H-I) mapping the purely imaginary eigenvalue of H on to the unit circle of matrix C one by one.We have given some special treatment in the article to make this proposition suitable for our Hamilton matrix. In fact, if we have found the eigenvalue A of H which has the largest magnitude, then set H←1/(|λ|+ε) H, whereεis positive. Notice that all the eigenvalues of H have magnitudes smaller than 1, that's to say 1 will no longer be the eigenvalue of H.So the eigenvalues of C on the unit circle are corresponding to these purely imaginary eigenvalue of H. We can now focus on the computing of eigenvalues of C on the unit circle.For the densely distributed eigenvalues of H nearby the imaginary axis are now nearby the unit circle of C, we will show that the squaring of matrix C can move these eigenvalues away from the unit circle.Proposition 0.2 When q→∞, the eigenvalues of Cq only distribute on unit circle |C|= , origin point and infinite point. From this proposition, we can see when q is large enough, computing the eigenvalues of C on unit circle|C|=1 can get rid of the interference from near by eigenvalues. Then the purely imaginary eigenvalue of H can be recovered from these eigenvalues of Cq. But the q can not be infinitely large, so we must control this q. Then we have the following-proposition.Proposition 0.3 The ratio of arithmetic operations of computing the completely covering between H and Cq isWe can see that this ratio increases when q increases, and has the max value of 15. When q=8,δ≈10, so this might be a good choice, one can hope for 10x speed up if using C8As matrix balancing is a key skill to reduce the computer floating point rounding error on the non-symmetric solution of matrix eigenvalue[37,38]. So we must do balancing at first. But the general balancing algorithms need O(n2) flops, how can we introduce the pretreatment with O(n2) flops to an algorithm with O(c·d·n) flops. Based on a proposition we get, we will give a method to deal with the balancing in O(n) flops in this paper.Now we can describe our fast method for the purely imaginary eigenvalues computing.Algorithm 0.1 The fast method for the purely imaginary eigenvalues computing. Input:Hamiltonian matrix HOutput:purely imaginary eigenvalues of Hstepl:Do fast balancing for Hamiltonian matrix H.step2:Find the eigenvalue A of H which has the largest magnitude, set H←1/(|λ|+ε)H, whereεis positive.step3:Construct C←(H+I)/(H-I).step4:Computing all the eigenvalues of C8on the unit circle{γm}.step5:Recover the eigenvalues{λm} of H from{γm}. so{(|λ|+ε)·μm} are purely imaginary eigenvalues of H.