Ein Gauß 40 x 40 dürfte bei Floats so 1 sec. brauchen. Das Problem hier dürfte dein Zahlenformat sein. Wie wäre es hingegen, mit Floats zu arbeiten und zur Ausgabe sich eine FloatToFrac zu schreiben.
Hier das wäre mal ein Anfang.
Du musst aber einen langsamen Computer haben. Steht da TI-57 oder so drauf?
Ich habe mal MATLAB angeworfen auf meinem Desktop-PC von 2008. Ein 40x40 Gleichungssystem wird in 0,15ms gelöst. Eingabe "x = A\b;" entspricht anschaulich A^(-1)*b benutzt aber LU-Zerlegung.
Eine Gauss-Implementierung von Github schafft es immer noch in 0,6ms. Bei 400 Elementen ist es auffälliger, da braucht der Gauß 400ms und linsolve() 20ms.
Zum Thema: Du musst auf jeden Fall mit dem String-gerechne aufhören
Vll. als erste Maßnahme mal Int64 für Zähler/Nenner hernehmen, oder wenn es WIRKLICH rational bleiben muss, dann auf Byte-Arrays für Zähle/Nenner gehen. Oder halt etwas Gehirnschmalz in eine eigene Div/Mod Funktion für Extended stecken und doch Gleitkommazahlen verwenden.