User:Tholden/11-1100/Homework Part 1

From Drorbn
< User:Tholden
Revision as of 11:56, 10 October 2011 by Tholden (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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.

Contents

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

The table initialization for Non-Commutative Gaussian Elimination.
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}


Matlab Implementation

 2 \times 2 \times 2 Rubik's cube

Megaminx