MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 3 corrected spelling

This seems to be an $O(n^3)$ problemdo , so if your matrix is smaller than 100 by 100 you might as well use an eigensolver.

For bigger matrices you can use Newton's method (see Higham's papers or book) to get a real almost orthogonal matrix and take the trace and round off. To get near the orthogonal in the polar decomposition iteratively replace $A$ by the average of $A$ with the transpose of the inverse of $A$.

That is, let $A_0 = A$ and $A_{n+1} = \left( \frac{1}{2}A + \frac{1}{2}\left( A^{\mathrm{T}} \right)^{-1} \right) $ and then the signature is \[ \lim_{n \rightarrow \infty} \mathrm{Trace} \left( A_N \right ) \]

If you have a priori information on the norm of $A$ and the size of the spectral gap at zero, you can figure how many iterations to do easily. If not many, this is very fast.

Nicholas J. Higham and Pythagoras Papadimitriou, A parallel algorithm for computing the polar decomposition, Elsevier, Parallel Computing, 20, (1994).
show/hide this revision's text 2 added 539 characters in body

This seems to be an $O(n^3)$ problem do if your matrix is smaller than 100 by 100 you might as well use an eigensolver.

For bigger matrices you can use Newton's method (see Higham's papers or book) to get a real almost orthogonal matrix and take the trace and round off. To get near the orthogonal in the polar decomp decomposition iteratively replace $A$ by the average of $A$ with the transpose of the inverse of $A$.I can say more whenI am at

That is, let $A_0 = A$ and $A_{n+1} = \left( \frac{1}{2}A + \frac{1}{2}\left( A^{\mathrm{T}} \right)^{-1} \right) $ and then the signature is \[ \lim_{n \rightarrow \infty} \mathrm{Trace} \left( A_N \right ) \]

If you have a computer priori information on the norm of $A$ and the size of the spectral gap at zero, you can figure how many iterations to do easily. If not a phonemany, this is very fast.

Nicholas J. Higham and Pythagoras Papadimitriou, A parallel algorithm for computing the polar decomposition, Elsevier, Parallel Computing, 20, (1994).
show/hide this revision's text 1

This seems to be an $O(n^3)$ problem do if your matrix is smaller than 100 by 100 you might as well use an eigensolver.

For bigger matrices you can use Newton's method to get a real almost orthogonal matrix and take the trace and round off. To get near the orthogonal in the polar decomp iteratively replace $A$ by the average of $A$ with the transpose of the inverse of $A$. I can say more whenI am at a computer and not a phone.