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