Determinant Function (Correction & Speedup)
- To: mathgroup <mathgroup at yoda.physics.unc.edu>
- Subject: Determinant Function (Correction & Speedup)
- From: HAY at leicester.ac.uk
- Date: Wed, 22 APR 92 09:43:15 GMT
Correction: multiply the output of NewDet3 by Signature[M] to take care of the
case when this is -1, eg {{2,1}, {1,2}}.
Speedup: use Transpose once instead of twice -
getting to know Transpose better has been one of the benefits of keeping at this
problem.
NewDet4[M_] :=
( Signature[M]
Plus@@Times@@
Append[ Transpose[#,{2,1,1}],(Signature/@#) ]&@
Permutations[ M ]
)
NewDet4[{{2,1},{1,2}}]
3
The timings are (on MacIIfx Mma Version 2.03)
a[n_] := Table[ StringJoin["a",ToString[i],ToString[j]], {i,1,n},{j,1,n}]
Do[ Print[ First[ Timing[ NewDet4[ a[i]]]]], {i,1,7}]
0.0666667 Second
0.0666667 Second
0.116667 Second
0.233333 Second
0.716667 Second
3.73333 Second
28.0167 Second
I am grateful for two suggestions for speeding up NewDet3:
FRANK ZIZZA <zizza at edu.willamette.pioneer>
suggests getting rid of the second Transpose by using Thread.
This seems to work for the smaller sizes but it is slower than NewDet3 for 7 by
7 determinants,at least on my machine:
NewDetZizza[M_] :=
( Signature[M]
Plus@@Times@@
Append[ Thread[Transpose[#,{1,2,2}]],Signature/@#]&@
Permutations[M]
)
Do[ Print[ First[ Timing[ NewDetZizza[ a[i]]]]], {i,1,7}]
0.0666667 Second
0.0666667 Second
0.133333 Second
0.266667 Second
0.75 Second
4. Second
35.5167 Second
The timings for New Det3 were
Timings[NewDet3]
0.25 Second
0.0666667 Second
0.116667 Second
0.25 Second
0.75 Second
4.03333 Second
31.0167 Second
DAVID SIBLEY <sibley at edu.psu.math> says
>"Permutations" always seems to return a list whose signatures are in the
>order 1,-1,-1,1,1,-1,-1,1,1,... There must be some way to take advantage
>of this, something better than actually computing the signatures."
but this pattern breaks down on Range[5] at the 25 th entry
{1, -1, -1, 1, 1, -1, -1, 1, 1, -1, -1, 1, 1, -1, -1, 1, 1, -1, -1, 1, 1, -1,
-1, [[ here 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, 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, -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, 1, 1, -1,
-1, 1, 1, -1, -1, 1, 1, -1, -1, 1}
Any suggestions on this?
From
Allan Hayes
Department of Mathematics
The University
Leicester LE1 7RH
U.K.
hay at leicester.ac.uk