How to efficiently compute the generalized cross product? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T10:14:30Z http://mathoverflow.net/feeds/question/109949 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/109949/how-to-efficiently-compute-the-generalized-cross-product How to efficiently compute the generalized cross product? aegirxx 2012-10-17T20:35:06Z 2012-10-22T08:21:00Z <p>It's possible to extend the well known cross product between two vectors in $\mathbb{R}^3$ to $n-1$ vectors in $\mathbb{R}^n$.</p> <p>Let $\vec{v_1}, \vec{v_2}, \dots, \vec{v}_{n-1} \in \mathbb{R}^n$ and $\vec{e}_1 = (1, 0, 0, \dots, 0)^T, \vec{e}_2 = (0, 1, 0, \dots, 0)^T, \dots, \vec{e}_n = (0, 0, \dots, 0, 1)^T$ be the unit vectors of the standard basis in $\mathbb{R}^n$. Then we can define the a "cross product" in $\mathbb{R}^n$ by the following determinant:</p> <p><code>$\vec{v}_1 \times \vec{v}_2 \times \dots \times \vec{v}_{n-1} = det\ \begin{pmatrix} v_{1,1} &amp; v_{2,1} &amp; \cdots &amp; v_{n-1,1} &amp; \vec{e}_1\cr v_{1,2} &amp; v_{2,2} &amp; \cdots &amp; v_{n-1,2} &amp; \vec{e}_2\cr \vdots &amp; \vdots &amp; \ddots &amp; \vdots &amp; \vdots\cr v_{1,n} &amp; v_{2,n} &amp; \cdots &amp; v_{n-1,n} &amp; \vec{e}_n \end{pmatrix}$</code></p> <p>In theory it's easy to compute the determinant by cofactor expansion along the last column, but i'm wondering how one would do this in practice. Computing the $n$ minors on their own seems like a lot of overhead to me and i guess it's not very stable.</p> <p><strong>Edit:</strong> <em>As turned out later, the following system of equations is wrong! Furthermore the approach is not used to compute the cross product but an orthogonal vector with arbitrary length.</em></p> <p>The only approach i've found on this topic is in the code of <a href="http://qhull.org/" rel="nofollow">qhull</a>. But unfortunately it's quite obfuscated and there aren't any helpful comments. I figured out that there the problem is adressed by solving the following system of equations:</p> <p>$A * \vec{x} = \vec{b}$ <br/> with $A = \begin{pmatrix} v_{1,1} &amp; v_{1,2} &amp; \dots &amp; v_{1,n}\cr v_{2,1} &amp; v_{2,2} &amp; \dots &amp; v_{2,n}\cr\vdots &amp; \vdots &amp; \ddots &amp; \vdots\cr v_{n-1,1} &amp; v_{n-1,2} &amp; \dots &amp; v_{n-1,n}\cr 0 &amp;0&amp; \cdots &amp; 1 \end{pmatrix}$, $\vec{b} = \begin{pmatrix}0\cr0\cr\vdots\cr 0 \cr sgn(det(A)) \end{pmatrix}$ and $sgn(x) := \begin{cases} +1 &amp; x \geq 0 \cr -1 &amp; x &lt; 0 \end{cases}$</p> <p>It's clear that the first $n-1$ rows are enforcing $\vec{x}$ to be orthogonal to <code>$\vec{v}_1, \dots, \vec{v}_{n-1}$</code> but i can't get the origin or meaning of the last row. Furthermore i guess this approach is problematic if $det(A) = 0$ (e.g. if vectors are parallel to a standard unit vector).</p> <p>So my questions are:</p> <ol> <li>How is the last row deduced and what is its meaning?</li> <li>Are there other approaches that are faster and/or more stable?</li> </ol> http://mathoverflow.net/questions/109949/how-to-efficiently-compute-the-generalized-cross-product/109995#109995 Answer by Federico Poloni for How to efficiently compute the generalized cross product? Federico Poloni 2012-10-18T09:29:01Z 2012-10-18T09:29:01Z <p>Regarding your question 2: the approach I'd take is computing the first determinant from a RQ factorization of the leading $(n-1)\times(n-1)$ matrix, and then each other by replacing in turn each row of $R$ with $(last row)Q$ and re-orthogonalizing manually with $O(n)$ Givens transformations on the left. In this way you pay $O(n^3)$ for the first determinant and then $O(n^2)$ (instead of the usual $O(n^3)$) for each subsequent one.</p> <p>Normwise stability should be ensured since we are only making orthogonal transformations.</p>