Re: friendly challenge 3
- To: mathgroup at smc.vnet.net
- Subject: [mg35087] Re: friendly challenge 3
- From: Andrzej Kozlowski <andrzej at bekkoame.ne.jp>
- Date: Mon, 24 Jun 2002 03:22:07 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
After posting my message I remembered that I should have added that speed is not the only consideration. So is returning correct answers. There is a rather obvious way do define the signature function that is much faster than my sign1. We just replace the matrix M by its floating point approximation: sign3[M_?MatrixQ] := Count[#, _?(# > 0 &)] - Count[#, _?(# < 0 &)] &@Chop[Eigenvalues[N[M]]] In many cases this works well, but it is easy to produce examples where it gives wrong answers. For example, let's take the singular symmetric matrix: In[7]:= p={{1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 100000000000, 100000000001}, {1, 1, 1, 1, 100000000001, 1}}; the (still unrevealed) sign1 returns In[8]:= sign1[p]//Timing Out[8]= {0.02 Second,1} while In[9]:= sign3[p]//Timing Out[9]= {0. Second,0} sign3 is faster than sign1 but it is also wrong. Actually, in this case sign2 also does not work (it produces error messages about comparisons between complex numbers and a wrong answer). Somewhat surprisingly replacing it by sign4[M_?MatrixQ] := Count[#, _?(# > 0 &)] - Count[#, _?(# < 0 &)] &@Chop[N[Eigenvalues[M]]] still does not work. It is now much slower and although it returns the right answer it still complains about comparisons between complex numbers, suggesting that this right answer was not arrived at correctly. To make this approach work correctly we need: sign5[M_?MatrixQ] := (Count[#, _?(# > 0 &)] - Count[#, _?(# < 0 &)] &)@ Chop[N[RootReduce[Eigenvalues[M]]]] In[13]:= sign5[p]//Timing Out[13]= {6.07 Second,1} This gives the right answer without any error messages, but the time taken is over 300 times longer than sign1 took! Finally, here is the definition of sign1: sign1[M_?MatrixQ] := Round[N[RootSum[Function[x, CharacteristicPolynomial[M, x]], Sign]]] Andrzej Kozlowski Toyama International University JAPAN http://platon.c.u-tokyo.ac.jp/andrzej/ On Friday, June 21, 2002, at 07:37 PM, Andrzej Kozlowski wrote: > While the season for "friendly challenges" lasts, here is something > that has just come up in my own work. Let's define the signature of a > symmetric matrix as the number of positive eigenvalues - the number of > negative ones. I need an efficient function to compute this. > There is the obvious and rather pedestrian one: > > sign2[M_?MatrixQ] := > Count[Eigenvalues[M], _?(# > 0 &)] - Count[Eigenvalues[M], _?(# < > 0 &)] > > For example, let's construct a symmetric matrix of random integers (all > matrices I am considering have integer entries): > > m = Table[Random[Integer, {1, 9}], {30}, {30}]; n = m + Transpose[m]; > > the above sign2 gives: > > In[4]:= > sign2[n]//Timing > > Out[4]= > {3.5 Second,0} > > > > My best function, sign1 gives (on 400 mghz PowerBOok G4) > > In[5]:= > sign1[n]//Timing > > Out[5]= > {1.44 Second,0} > > Nearly two and a half times as fast. Can anyone do better? > > Andrzej > >