Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2002
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2002

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

Search the Archive

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
>
>



  • Prev by Date: Re: Working with Strings
  • Next by Date: RE: Re: Friendly Challenge 2: sort by column
  • Previous by thread: friendly challenge 3
  • Next by thread: Re: friendly challenge 3