User:Tholden/11-1100/Homework Part 1

This page showcases my work done in implementing the Non-Commutative Gaussian Elimination algorithm with direct application to solving a permutation puzzle. I would like it to be known that I had originally chosen the Megaminx puzzle and am still in the process of solving it. The algorithm is currently running on a Sun x4600 computational server using Matlab 2010b including eight Opteron 8212 processors with 32 GB of memory. However, the algorithm is not conducive to parallelization and so has yet to converge. As a test-case, I have solved the $2\times 2\times 2$ Rubik's cube, which I will also present here. In the event that the algorithm has not converged, I will submit the $2\times 2\times 2$ Rubik's cube for marking.

Theoretical Review of the Algorithm

The purpose of Non-Commutative Gaussian Elimination (NCGE) is to find the elements and order of a subgroup generated by a finite set of generators. The algorithm proceeds as follows:

Let $G=\langle g_{1},\ldots ,g_{\alpha }\rangle$. Define the pivot of $\sigma \in S_{n}$ to be the minimal $k\in \mathbb {N}$ such that $\sigma (k)\neq k$. We prepare a table which is mostly empty

A mostly empty table for Gaussian Elimination

Feed $g_{1},\ldots ,g_{n}$ in order. To feed a non-identity $\sigma$, find its pivotal position $i$ and let $j=\sigma (i)$. \begin{enumerate} \item If box $(i,j)$ is empty, put $\sigma$ in this box. \item If box $(i,j)$ is not-empty, feed $\sigma '=\sigma _{i,j}^{-1}\sigma$ into the table. \end{enumerate}