View source for N-Dimensional rotation matrix generation algorithm


{{Article for deletion/dated|page=N-Dimensional rotation matrix generation algorithm|timestamp=20170723224502|year=2017|month=July|day=23|substed=yes|help=off}}
<!-- Once discussion is closed, please place on talk page: {{Old AfD multi|page=N-Dimensional rotation matrix generation algorithm|date=23 July 2017|result='''keep'''}} -->
<!-- End of AfD message, feel free to edit beyond this point -->
{{DISPLAYTITLE:''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 <math>\in</math> R<sup>N</sup>. We want to obtain a rotation matrix M that satisfies the equation

<math>Y_x=MX</math>

where <math>Y_x</math> has the same norm as X and the same direction as Y, i.e. <math>\|Y_x\|=\|X\|</math> (<math>\cos Y_x</math>,<math>Y=1</math>).

== 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 <math>\overline{X}</math> и <math>\overline{Y}</math>. 
* Create a [[Givens rotation|Givens matrix]] <math>G(1, 2, \theta)</math> for <math>R^N</math>, which performs rotation of <math>\overline{X}</math> in coordinate plane <math>\overline{x_1}</math>,<math>\overline{x_2}</math> to the direction of vector <math>\overline{Y}</math>.
* Obtain rotation matrix M as <math>M=P^{-1}G(1,2,\theta)P</math> where <math>P</math> 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 transformation|Householder reflection]]. If X and Y are vectors with the same norm, there exists an orthogonal symmetric matrix P such that <math>Y=PX</math> where <math>P=I-2WW^T</math> and <math>W=X-Y/\|X-Y\|</math>. Matrix ''P'' is a matrix of reflection (not a rotation) because det&nbsp;''P''&nbsp;=&nbsp;–1 (which gives the name to the method). That’s why to obtain a matrix of rotation ''M'', for which det&nbsp;''M'' =&nbsp;1, two subsequent reflections have to be performed. The matrix of rotation can be obtained as a multiplication of two matrices of reflection <math>P_1</math> and <math>P_2</math> as <math>M = P_1P_2</math>.

=== 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 <math>x_1</math>). This algorithm (named NRMG algorithm) includes the following sequence of operations:
* Obtain rotation matrix <math>M_x</math>, which rotates given vector <math>X</math> to the direction of axis <math>x_1</math>. 
* Obtain rotation matrix <math>M_y</math>, which rotates given vector <math>Y</math> to the direction of axis <math>x_1</math>. 
* Obtain rotation matrix <math>M</math>, as a multiplication of <math>M_x</math> by the inverse matrix of <math>M_y</math> given as: 

: <math>M=M_y^{-1} M_x=M_y^{T} M_x</math>

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 <math>x_1</math>).

=== Rotation of n-dimensional vector to the direction of axis <math>x_1</math> ===
Rotation of a given n-dimensional vector to the direction of one of the coordinate axes (i.e. axis ''x''<sub>1</sub>) can be performed by ''n''&nbsp;−&nbsp;1 subsequent rotations in coordinate planes (''x''<sub>''n''−''k''</sub>, ''x''<sub>''n''−''k''+1</sub>), ''k''&nbsp;=&nbsp;1,…,''n''&nbsp;−&nbsp;1 using multiplications by Givens matrices <math>G(n-k,n-k+1,\theta_{n-k})</math>, where coefficients ''S''&nbsp;=&nbsp;sin(''θ''<sub>''n''−''k''</sub>) and ''C''&nbsp;=&nbsp;cos(''θ''<sub>''n''−''k''</sub>) are calculated as follows:

: <math>\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}
</math>
 
After every rotation, we get a vector that is orthogonal to the coordinate axis ''x''<sub>''n''−''k''+1</sub> in the current coordinate plane (''x''<sub>''n''−''k''</sub>, ''x''<sub>''n''−''k''+1</sub>). Thus subsequent rotations in coordinate planes (''x''<sub>''n''−''k''</sub>, ''x''<sub>''n''−''k''+1</sub>), ''k''&nbsp;=&nbsp;1,…,''n''&nbsp;−&nbsp;1 give a vector that is orthogonal to all coordinate axes except x<sub>1</sub>. Rotation matrix <math>M_x</math> is obtained as a multiplication of Givens matrices <math>G(n-k,n-k+1,\theta_{n-k}),\  k=1,\ldots,n-1,</math> as follows:

: <math>M_x =\prod_{k=1}^{n-1} G(n-k,n-k+1,\theta_{n-k})</math>

The length <math>r_X = \|X\|</math> of given vector ''X'' and angles of rotation ''θ''<sub>1</sub> , ... , ''θ''<sub>''n''−1</sub> in the equation above are in reality coordinates of vector ''X'', presented in hyperspherical coordinate system as {{nowrap|1=''X''<sub>''S''</sub> = [''r''<sub>''X''</sub>, −''θ''<sub>1</sub> , ... , −''θ''<sub>''n''−1</sub> ]<sup>T</sup>}}. Angles of rotation are included with a negative sign, because rotation of a given vector to the direction of the coordinate axis x<sub>1</sub> 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 <math>\lceil log_2(n)\rceil</math> regardless of the fact that the total number of rotations in coordinate planes will remain equal to <math>n-1</math>.

== 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|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.

[[Category:Transformation (function)]]
[[Category:Matrices]]
[[Category:Mathematical physics]] {{⚠️🚨COPIED from en.EverybodyWiki.com ❗❕⚠️😡😤Please respect Licence CC-BY-SA ❗}}
{{Source Wikipedia}}