MathGroup Archive 2002

[Date Index] [Thread Index] [Author Index]

Search the Archive

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



  • Prev by Date: RE: friendly challenge 3
  • Next by Date: RE: Large-scale enumerations and memory problems
  • Previous by thread: RE: friendly challenge 3
  • Next by thread: Strange thing with exporting to PDF.