Re: friendly challenge 3

*To*: mathgroup at smc.vnet.net*Subject*: [mg35099] Re: friendly challenge 3*From*: Samuel Kutter <sk256 at phy.cam.ac.uk>*Date*: Tue, 25 Jun 2002 03:39:39 -0400 (EDT)*Organization*: University of Cambridge, England*References*: <af6hk6$lkc$1@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

Hello everybody, vaguely remembered a test from undergraduate lectures... - I hope, it is all right! Sam In[268]:= sign2[M_?MatrixQ] := Count[Eigenvalues[M], _?(# > 0 &)] - Count[Eigenvalues[M], _?(# < 0 &)] In[290]:= <<LinearAlgebra`MatrixManipulation` In[376]:= SubMat[M_,p_]:=TakeMatrix[M,{1,1},{p,p}] In[384]:= Signew[M_]:= Module[{count,sign},count=0; sign=1; Do[If[sign Det[SubMat[M,i]]>0,count=count+1,count=count-1; sign=- sign]; ,{i,1,Dimensions[M][[1]]}];count]; In[441]:= m = Table[Random[Integer, {1, 9}], {30}, {30}]; n = m + Transpose[m]; sign2[n]//Timing Signew[n]//Timing %%[[1]]/%[[1]] Out[441]= {8.383 Second,2} /*not EXACTLY a fast machine! ;-) */ Out[442]= {0.66664 Second,2} Out[443]= 12.575 /*factor 12 faster!*/ On Mon, 24 Jun 2002, 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