n-Dimensional rotation matrix generation algorithm

High-dimensional spaces frequently occur in mathematics and the sciences, for example, N-dimensional feature space, which presents input signals of a neural network or a collection of N-dimensional parameters for multidimensional data analysis. Rotation is one of the rigid transformations in geometrical space that preserves the length of vectors and can be presented using matrix operations like Y = M.X, where X and Y are input and output vectors respectively, and M is the 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. $\Vert Y_x\Vert =\Vert X\Vert$ ($\cos Y_x$,$Y=1$).

Algorithms for generation of n-dimensional rotation matrix

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

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

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

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

Using Householder reflection

Another way to generate a 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-2W{W}^T$ and $W=X-Y/\Vert X-Y\Vert$. Matrix P is a matrix of reflection (not a rotation) because det P = –1 (which gives the name to the method). That’s why to obtain a matrix of rotation M, for which det M = 1, two subsequent reflections have to be performed. The matrix of rotation can be obtained as a multiplication of two matrices 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 a rotation matrix M is to use rotation of given vectors to the direction of one of the coordinate axes (i.e. axis $x_1$). This algorithm (named NRMG algorithm) includes the following sequence of operations:

• Obtain rotation matrix $M_x$, which rotates given vector $X$ to the direction of axis $x_1$.
• Obtain rotation matrix $M_y$, which rotates given vector $Y$ to the direction of axis $x_1$.
• Obtain rotation matrix $M$, as a multiplication of $M_x$ by the inverse matrix of $M_y$ given as:

$M=M_y^{-1}{M}_x=M_y^T{M}_x$

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

Rotation of n-dimensional vector to the direction of axis $x_1$

Rotation of a given n-dimensional vector to the direction of one of the 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{array}{l}\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}},x_{n-k}^2+x_{n-k+1}^2>0\\ \sin ({\theta }_{n-k})=0,\cos ({\theta }_{n-k})=1,x_{n-k}^2+x_{n-k+1}^2=0\end{array}$

After every rotation, we get a vector that is orthogonal to the coordinate axis x_n−k+1 in the 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 give a vector that is orthogonal to all coordinate axes except x₁. Rotation matrix $M_x$ is obtained as a multiplication of Givens matrices $G(n-k,n-k+1,{\theta }_{n-k}),k=1,\dots ,n-1,$ as follows:

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

The length $r_X=\Vert X\Vert$ 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 a negative sign, because rotation of a given vector to the direction of the coordinate axis x₁ calculates angles from the vector to the coordinate axes, while presentation of the vector in hyperspherical coordinate system calculates opposite direction angles – from axes to vector.

The advantage of using Givens rotations for rotation of an n-dimensional vector to the direction of one of the 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 reduced to $\lceil lo{g}_2(n)\rceil$ regardless of the fact that the total number of rotations in coordinate planes will remain equal to $n-1$.

Notes

The time complexity of the algorithms described above depends on the "density" of given vectors X and Y. Like for the task of QR decomposition, for "dense" vectors Householder Reflection can be the most efficient, while for vectors that have many zero elements, the NRMG algorithm (which uses Givens rotations) can be more efficient than the other two.

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)

• Matrix field
• 2 × 2 real matrices
• Statistical stability
• Arrowhead-like matrix
• Kirchhoff graph
• Raphael Neelamkavil
• X–Y–Z matrix

---