# A Parallel Algorithm for Dividing Octonions
## 3 Synthesis of a Fast Algorithm for Octonion Division  
Let us multiply by \((-1)\) the first column of the matrix \(\mathbf{O}_{8}\). It is easy to see that this procedure leads to minimising the computational complexity of the final algorithm. This results in the following matrix:  
\[\mathbf{B}_{8}=\left[\begin{array}{cccccccc}-b_{0}&b_{1}&-b_{2}&b_{3}&b_{4} &b_{5}&b_{6}&b_{7}\\ b_{1}&b_{0}&b_{3}&-b_{2}&b_{5}&-b_{4}&-b_{7}&b_{6}\\ b_{2}  
where  
\[\mathbf{B}_{8}^{(1)}=\left[ \begin{array}{cccc|cccc}b_{0}&b_{1}&b_{2}&b_{3}&b_{4 }&b_{5}&b_{6}&b_{7}\\ b_{1}&b_{0}&b_{3}&b_{2}&b_{5}&b_{4}&b_{7}&b_{6}\\ b_{2}&b_{3}&b_{0}&b_{1}&b_{6}&b_{7}&b_{4}&b_{5}\\ b_{3}&b_{2}&b_{1}&b_{0}&b_{7}&b_{6}&b_{5}&b_{4}\\ \hline b_{4}&b_{5}&b_{6}&b_{7}&b_{0}&b_{1}&b_{2}&b_{3}\\ b_{5}&b_{4}&b_{7}&b_{6}&b_{1}&b_{0}&b_{3}&b_{2}\\ b_{6}&b_{7}&b_{4}&b_{5}&b_{2}&b_{3}&b_{0}&b_{1}\\ b_{7}&b_{6}&b_{5}&b_{4}&b_{3}&b_{2}&b_{1}&b_{0}\end{array} \right], \tag{7}\]  
\[\mathbf{B}_{8}^{(2)}=\left[ \begin{array}{cccccccc}b_{0}&0&0&0&0&0&0&0\\ 0&0&0&b_{2}&0&b_{4}&b_{7}&0\\ 0&b_{3}&0&0&0&b_{4}&b_{5}\\ 0&0&b_{1}&0&0&b_{6}&0&b_{4}\\ 0&b_{5}&b_{6}&b_{7}&0&0&0&0\\ 0&0&b_{7}&0&b_{1}&0&b_{3}&0\\ 0&0&0&b_{5}&b_{2}&0&0&b_{1}\\ 0&b_{6}&0&0&b_{3}&b_{2}&0&0\end{array} \right], \tag{8}\]  
\[\mathbf{\bar{T}}_{8}=diag(-1,1,1,1,1,1,1).\]  
The following notation may be introduced: \(\mathbf{\hat{Y}}_{8\times 1}=\eta_{8}\mathbf{B}_{8}^{(1)}\mathbf{\bar{T}}_{8} \mathbf{X}_{8\times 1}\), and \(\mathbf{\hat{Y}}_{8\times 1}=\eta_{8}2\mathbf{B}_{8}^{(2)}\mathbf{\bar{T}}_{8} \mathbf{X}_{8\times 1}\). Then, the division of two octonions can be represented as the following sum:  
\[\mathbf{Y}_{8\times 1}=\mathbf{\hat{Y}}_{8\times 1}-\mathbf{\hat{Y}}_{8\times 1}. \tag{9}\]  
It is easy to see that the matrix \(\mathbf{B}_{8}^{(1)}\) has symmetric Toeplitz-type structure. A matrix with such a structure can be successfully diagonalized using the fast discrete Walsh-Hadamard transform [35]. Let us take a closer look at this thought. The matrix \(\mathbf{B}_{8}^{(1)}\) has a block-symmetric structure:  
\[\mathbf{B}_{8}^{(1)}=\left[\begin{array}{cccc|cccc}b_{0}&b_{1}&b_{2}&b_{3}&b _{4}&b_{5}&b_{6}&b_{7}\\ b_{1}&b_{0}&b_{3}&b_{2}&b_{5}&b_{4}&b_{7}&b_{6}\\ b_{2}&b_{3}&b_{0}&b_{  
where  
\[\mathbf{W}_{8}^{(0)}=\mathbf{H}_{2}\otimes\mathbf{I}_{4}=\left[ \begin{array}{ c|cccccccc}1&&&&1&&&&\\ &1&&&&1&&\\ &&1&&&&1&\\ &&1&&&&1\\ \hline 1&&&&-1&&&&\\ &1&&&&-1&&\\ &&1&&&&-1&\\ &&1&&&&-1\end{array} \right],\]  
\[\mathbf{D}_{8}^{(1)}=\frac{1}{2}[(\mathbf{A}_{4}+\mathbf{B}_{4})\oplus(\mathbf{ A}_{4}-\mathbf{B}_{4})]=\frac{1}{2}\left[ \begin{array}{cc}\mathbf{A}_{4}+ \mathbf{B}_{4}&\mathbf{0}_{4}\\ \mathbf{0}_{4}&\mathbf{A}_{4}-\mathbf{B}_{4}\end{array} \right],\]  
\(\mathbf{H}_{2}=\left[ \begin{array}{cc}1&1\\ 1&-1\end{array} \right]\) is Hadamard matrix of order 2, \(\mathbf{0}_{N}\) is the \(N\times N\) null matrix (all of its entries are zero), and symbols \"\(\otimes\)\", \"\(\oplus\)\" denote the tensor product and direct sum of two matrices, respectively [31; 35; 36; 37]. The next step is to analyze the structures of matrix \(\mathbf{A}_{4}+\mathbf{B}_{4}\) and matrix \(\mathbf{A}_{4}-\mathbf{B}_{4}\):  
\[\mathbf{A}_{4}+\mathbf{B}_{4}=\left[ \begin{array}{c|c}\mathbf{A}_{2}& \mathbf{B}_{2}\\ \hline\mathbf{B}_{2}&\mathbf{A}_{2}\end{array} \right],\quad\mathbf{A}_{4}- \mathbf{B}_{4}=\left[ \begin{array}{c|c}\mathbf{C}_{2}&\mathbf{D}_{2}\\ \hline\mathbf{D}_{2}&\mathbf{C}_{2}\end{array} \right],\]  
\[\mathbf{A}_{2}=\left[ \begin{array}{c|c}b_{0}+b_{4}&b_{1}+b_{5}\\ \hline b_{1}+b_{5}&b_{0}+b_{4}\end{array} \right],\quad\mathbf{B}_{2}=\left[ \begin{array}{c|c}b_{2}+b_{6}&b_{3}+b_{7}\\ \hline b_{3}+b_{7}&b_{2}+b_{6}\end{array} \right],\]  
\[\mathbf{C}_{2}=\left[ \begin{array}{c|c}b_{0}-b_{4}&b_{1}-b_{5}\\ \hline b_{1}-b_{5}&b_{0}-b_{4}\end{array} \right],\quad\mathbf{D}_{2}=\left[ \begin{array}{c|c}b_{2}-b_{6}&b_{3}-b_{7}\\ \hline b_{3}-b_{7}&b_{2}-b_{6}\end{array}