Re: [apple scitech] Determinant algorithm

• Subject: Re: [apple scitech] Determinant algorithm
• From: Martin Costabel <email@hidden>
• Date: Fri, 02 Nov 2007 09:23:13 +0100
• Delivered-to: email@hidden
• Delivered-to: email@hidden
• User-agent: Thunderbird 2.0.0.6 (Macintosh/20070728)

Daniel Farrell,

There is a way to effect a 4x4 determinant in 40 muls.
Let us assume a matrix

        double a[4][4];

whence, one simply calculates

    det = a[0][0] * F(1, 2, 3) - a[1][0] * F(0, 2, 3) +
          a[2][0] * F(0, 1, 3) - a[3][0] * F(0, 1, 2);

where the function F is:

double
F(int x, int y, int z) {
return(
    a[x][1] * (a[y][2] * a[z][3] - a[z][2] * a[y][3]) +
    a[y][1] * (a[z][2] * a[x][3] - a[z][3] * a[x][2]) +
    a[z][1] * (a[x][2] * a[y][3] - a[x][3] * a[y][2])
);
}

I am sure there are clever ways to reduce the ops yet further;

   det = G(0,1,2,3) + G(0,2,1,3) + G(0,3,1,2) +
         G(1,2,0,3) + G(1,3,0,2) + G(2,3,0,1);

where

   double
   G(int j, int k, int m, int n) {
   return(
       ( a[j][0] * a[k][1] - a[k][0] * a[j][1] ) *
       ( a[m][2] * a[n][3] - a[n][2] * a[m][3] )
   );
   }

in fact the F-function here suggests such (e.g., the product a[2][2]*a[3][3]
happens more than once, overall). Plus, the excellent suggestion appearing
before on this scitech list---namely to invoke pivoting even at 4x4---
also might apply to the optimization of the F-function.

--
Martin

_______________________________________________
Do not post admin requests to the list. They will be ignored.
Scitech mailing list      (email@hidden)
Help/Unsubscribe/Update your Subscription:
http://lists.apple.com/mailman/options/scitech/email@hidden

• Prev by Date: [apple scitech] Determinant algorithm
• Next by Date: [apple scitech] Determinant refinement
• Previous by thread: [apple scitech] Determinant algorithm
• Next by thread: [apple scitech] Determinant refinement
• Index(es):
  • Date
  • Thread