n-Dimensional rotation matrix generation algorithm

High-dimensional spaces frequently occur in mathematics and the sciences, in example N-dimensional feature space, which presents input signals of neural network or collection of N-dimensional parameters for multidimensional data analysis. Rotation is one of rigid transformations in geometrical space, that preserves length of vectors and can be presented using matrix operation like Y = M.X , where X and Y are input and output vector respectively, and M – rotation matrix.

Definition of the task

Let's say that we have two n-dimensional vectors X and Y, having the same dimension, X, Y $\in$ R^N. We want to obtain a rotation matrix M that satisfies the equation

$Y_{x}=MX$

where $Y_{x}$ has the same norm as X and the same direction as Y i.e. $\|Y_{x}\|=\|X\|$ ($\cos Y_{x}$,$Y=1$).

Algorithms for generation of n-dimensional rotation matrix

Description of three algorithms for generation of n-dimensional rotation matrix, which rotates given n-dimensional vector X to the direction of given n-dimensional vector Y are given below.

Using rotation in coordinate plane of basis, defined by given vectors

One of possibilities to generate rotation matrix M is to change basis and to create matrix, which rotates vector X in coordinate plane, in which lies the two given vectors . This algorithm includes the following sequence of operations:

• Obtain two orthogonal vectors in the plane, in which lies the two given vectors using Gramm-Schmidt procedure.
• Enlarge this 2-dimensional basis to N- dimensional basis B2 , in which given vectors X, Y are transformed to ${\overline {X}}$ и ${\overline {Y}}$.
• Create Givens matrix $G(1,2,\theta )$ for $R^{N}$ , which perform rotation of ${\overline {X}}$ in coordinate plane ${\overline {x_{1}}}$,${\overline {x_{2}}}$ to the direction of vector ${\overline {Y}}$.
• Obtain rotation matrix M as $M=P^{-1}G(1,2,\theta )P$ where $P$ is transformation matrix from initial basis B to the constructed basis B2.

Using Householder reflection

Another way to generate rotation matrix M is to use Householder reflection. If X and Y are vectors with the same norm, there exists an orthogonal symmetric matrix P such that $Y=PX$ where $P=I-2WW^{T}$ and $W=X-Y/\|X-Y\|$ . Matrix P is matrix of reflection (not a rotation) because det P = –1, (which gives the name to method) that’s why to obtain matrix of rotation M, for which det M = 1, have to be performed two subsequent reflections. Matrix of rotation can be obtained as multiplication of two matrix of reflection $P_{1}$ and $P_{2}$ as $M=P_{1}P_{2}$.

Using rotation of given vectors to the direction of one of coordinate axes

The third way to generate rotation matrix M is to use rotation of given vectors to the direction of one of coordinate axes (i.e. axis $x_{1}$). This algorithm (named NRMG algorithm) includes the following sequence of operations:

• Obtaining rotation matrix $M_{x}$, which rotates given vector $X$ to the direction of axis $x_{1}$.
• Obtaining rotation matrix $M_{y}$, which rotates given vector $Y$ to the direction of axis $x_{1}$.
• Obtaining rotation matrix $M$, as multiplication of $M_{x}$ by inverse matrix of $M_{y}$ given as:

$M=M_{y}^{-1}M_{x}=M_{y}^{T}M_{x}$

As it can be seen in description above, the base operation of NRMG algorithm is rotation of n-dimensional vector to the direction of one of coordinate axes (i.e. axis $x_{1}$).

Rotation of n-dimensional vector to the direction of axis $x_{1}$

Rotation of given n-dimensional vector to the direction of one of coordinate axes (i.e. axis x₁) can be performed by n − 1 subsequent rotations in coordinate planes (x_n−k, x_n−k+1), k = 1,…,n − 1 using multiplications by Givens matrices $G(n-k,n-k+1,\theta _{n-k})$, where coefficients S = sin(θ_n−k) and C = cos(θ_n−k) are calculated as follows:

${\begin{cases}\sin(\theta _{n-k})=-{\frac {x_{n-k+1}}{\sqrt {x_{n-k}^{2}+x_{n-k+1}^{2}}}},\cos(\theta _{n-k})={\frac {x_{n-k}}{\sqrt {x_{n-k}^{2}+x_{n-k+1}^{2}}}},\quad x_{n-k}^{2}+x_{n-k+1}^{2}>0\\\sin(\theta _{n-k})=0,\cos(\theta _{n-k})=1,\quad x_{n-k}^{2}+x_{n-k+1}^{2}=0\end{cases}}$

After every one rotation we get vector, which is orthogonal to coordinate axis x_n−k+1 in current coordinate plane (x_n−k, x_n−k+1). Thus subsequent rotations in coordinate planes (x_n−k, x_n−k+1), k = 1,…,n − 1 gives vector, which is orthogonal to all coordinate axes except x₁. Rotation matrix $M_{x}$ is obtained as multiplication of Givens matrices $G(n-k,n-k+1,\theta _{n-k}),\ k=1,\ldots ,n-1,$ as follows:

$M_{x}=\prod _{k=1}^{n-1}G(n-k,n-k+1,\theta _{n-k})$

The length $r_{X}=\|X\|$ of given vector X and angles of rotation θ₁ , ... , θ_n−1 in the equation above are in reality coordinates of vector X, presented in hyperspherical coordinate system as X_S = [r_X, −θ₁ , ... , −θ_n−1 ]^T. Angles of rotation are included with negative sign, because rotation of given vector to the direction of coordinate axis x₁ calculates angles from vector to coordinate axes, while presentation of vector in hyperspherical coordinate system calculates opposite direction angles – from axes to vector.

Advantage of using Givens rotations for rotation of n-dimensional vector to the direction of one of coordinate axes is that rotations in coordinate planes can easily be parallelised. This way the number of subsequent rotations in coordinate planes (i.e. the number of matrix multiplications) can be redused to $\lceil log_{2}(n)\rceil$ regardless that the total number of rotations in coordinate planes will remain equal to $n-1$.

Notes

Time complexity of algorithms, described above depends of "density" of given vectors X and Y. Like for the task of QR decomposition, for "densy" vectors Hauseholder Reflection can be the most efficient, while for vectors, that have many zero elements NRMG algorithm (which uses Givens rotations) can be more efficient then two others.

References

• H.G. Golub, J.M. Ortega, 1993, Scientific Computing and Introduction with Parallel Computing, Academic Press, Inc., San Diego
• G. A. Korn, T.M. Korn, 1961, Mathematical Handbook for Scientists and Engineers (1st ed.), New York: McGraw-Hill. pp. 55–79.
• H. Friedberg, A. Insel, L. Spence, 1997, Linear Algebra (3rd ed), Prentice Hall.
• M. Cosnard, Y. Robert. Complexity of parallel QR factorization. J. ACM 33, 4 (August 1986), 712–723. DOI=10.1145/6490.214102, 1986
• A. H. Sameh, D. J. Kuck. On Stable Parallel Linear System Solvers. J. ACM 25, 1 (January 1978), 81–91. DOI= http://dx.doi.org/10.1145/322047.322054, 1978
• N. J. Higham, 1996, Accuracy and Stability of Numerical Algorithms, SIAM, Philadelfia
• G. W.Steward, 1976, The economical storage of plane rotations, Numer. Math, 25, 2 1976, 137–139
• N. K. Bose, 1985, Multidimensional Systems Theory: Progress, Directions, and Open Problems. D.Reidel Publishing Co., Dordrecht, The Netherland
• A. S. Householder, 1958, “Unitary triangularization of a nonsimetric matrix”, J. ACM 5, 339–342, 1958
• E. Anderson, 2000, “Discontinuous Plane Rotations and the Symmetric Eigenvalue Problem” LAPACK Working Note 150, University of Tennessee, UT-CS-00-454, December 4, 2000. page 2
• Zhelezov O. I. N-dimensional Rotation Matrix Generation Algorithm, American Journal of Computational and Applied Mathematics , Vol. 7 No. 2, 2017, pp. 51–57. doi: 10.5923/j.ajcam.20170702.04.

This article "N-Dimensional rotation matrix generation algorithm" is from Wikipedia. The list of its authors can be seen in its historical. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

📰 Article(s) of the same category(ies)

• Combinatorial hierarchy
• Mathematical physics
• Phase Retrieval
• Arrowhead-like matrix
• Network capacity
• 2 × 2 real matrices
• Statistical stability

---