[Numpy-discussion] permutation symbol

[David Goldsmith]

Hi!  I can't help but wonder if - out there somewhere - there's an optimized algorithm for implementing the general N-D Permutation Symbol:

"The symbol can be generalized to an arbitrary number of elements, in which case the permutation symbol is (-1)^(i(p)), where i(p) is the number of transpositions of pairs of elements (i.e., permutation inversions) that must be composed to build up the permutation p (Skiena 1990)."

(perhaps in the referenced paper - anyone have "free" access to such reprints online) which we could add to NumPy, including it's specializations to the 3-D and 2-D cases as convenience functions.  (I'd write it given the algorithm, but combinatorics was never my strong suit, i.e., I'm sure someone else on this list could figure out at least a brute force algorithm more efficiently than yours truly.)  Alternatively, isn't this "just" a tensor product with one factor a constant tensor, and thus we could implement it that way using an existing resource?  

DG
--- On Tue, 6/30/09, Charles R Harris <charlesr.harris at gmail.com> wrote:

> From: Charles R Harris <charlesr.harris at gmail.com>
> Subject: Re: [Numpy-discussion] permutation symbol
> To: "Discussion of Numerical Python" <numpy-discussion at scipy.org>
> Date: Tuesday, June 30, 2009, 10:10 AM
> 
> 
> On Tue, Jun 30, 2009 at 10:56 AM,
> Charles R Harris <charlesr.harris at gmail.com>
> wrote:
> 
> 
> 
> On
> Tue, Jun 30, 2009 at 10:40 AM, Nils Wagner <nwagner at iam.uni-stuttgart.de>
> wrote:
> 
> 
> On Tue, 30 Jun 2009 10:27:05 -0600
> 
>   Charles R Harris <charlesr.harris at gmail.com>
> wrote:
> 
> > On Tue, Jun 30, 2009 at 5:11 AM, Nils Wagner
> 
> > <nwagner at iam.uni-stuttgart.de>wrote:
> 
> >
> 
> >> On Tue, 30 Jun 2009 11:22:34 +0200
> 
> >>  "Nils Wagner" <nwagner at iam.uni-stuttgart.de>
> wrote:
> 
> >>
> 
> >>>  Hi all,
> 
> >>>
> 
> >>> How can I build the following product with
> numpy
> 
> >>>
> 
> >>> q_i = \varepsilon_{ijk} q_{kj}
> 
> >>>
> 
> >>> where  \varepsilon_{ijk} denotes the
> permutation symbol.
> 
> >>>
> 
> >>> Nils
> 
> >>>
> 
> >>  Sorry for replying to myself.
> 
> >> The permutation symbol is also known as the
> Levi-Civita
> 
> >>symbol.
> 
> >> I found an explicit expression at
> 
> >> http://en.wikipedia.org/wiki/Levi-Civita_symbol
> 
> >>
> 
> >> How do I build the product of the Levi-Civita
> symbol
> 
> >>\varepsilon_{ijk} and
> 
> >> the two dimensional array
> 
> >> q_{kj}, i,j,k = 1,2,3 ?
> 
> >>
> 
> >
> 
> > Write it out explicitly. It essentially
> antisymmetrizes
> 
> >q and the three off
> 
> > diagonal elements can then be treated as a vector.
> 
> >Depending on how q is
> 
> > formed and the resulting vector is used there may be
> 
> >other things you can do
> 
> > when you use it in a more general expression. If this
> is
> 
> >part of a general
> 
> > calculation there might be other ways of expressing
> it.
> 
> >
> 
> > Chuck
> 
> 
> 
> Hi Chuck,
> 
> 
> 
> Thank you for your response.
> 
> The problem at hand is described in a paper by Angeles
> 
> namely equation (17c) in
> 
> "Automatic computation of the screw parameters of
> 
> rigid-body motions.
> 
> Part I: Finitely-separated positions"
> 
> Journal of Dynamic systems, Measurement and Control, Vol.
> 
> 108 (1986) pp. 32-38
> 
> 
> You can solve this problem using quaternions also, in which
> case it reduces to an eigenvalue problem. You will note that
> such things as PCA are used in the papers that reference the
> cited work so you can't really get around that bit of
> inefficiency.
> 
> 
> 
> Here's a reference to the quaternion approach: http://people.csail.mit.edu/bkph/papers/Absolute_Orientation.pdf.
> You can get the translation part from the motion of the
> centroid.
> 
>  
> If you are into abstractions you will note that the problem
> reduces to minimising a quadratic form in the quaternion
> components. The rest is just algebra ;)
> 
> Chuck
> 
> 
> 
> -----Inline Attachment Follows-----
> 
> _______________________________________________
> Numpy-discussion mailing list
> Numpy-discussion at scipy.org
> http://mail.scipy.org/mailman/listinfo/numpy-discussion
>