gauss benchmark und verhältnisse

japro

ich hab mir mal ein proggi geschrieben das lineare gleichungssysteme nach gauss auflöst... jetzt wollte ich das als benchmark benutzen. da allerdings die zeiten alleine noch nicht so viel aussagen wollte ich das ganze in relation zur grösse des gelcihungssystems...
ich habe als einfach mal angenommen das das lösen eines NxN systemes eine zu N^2 proportionale zeit benötigt...
aber irgendwie stimmt das nicht ...
wenn ich einfach N^2/laufzeit benutze bekomme ich keinesfalls mehr oder weniger ähnliche zahlen....

Gregor

Zeig doch mal den Code. Ich habe nämlich letzt auch soetwas programmiert und möchte sehen, ob dir vielleicht etwas eingefallen ist, was auch bei mir die Performanz steigern könnte!

Mein Code ist noch nicht sonderlich optimiert, aber wenn du ihn sehen willst, dann zeige ich ihn dir trotzdem. ...ist natürlich in Java (wer hätte das gedacht?! :))

japro

bin grad in der schule deshalb kann ich den code momentan nicht posten. aber ich glaube ich bin schonmal hinter das eine problem gekommen... der gaussalgorithmus hat nämlich eine laufzeit proportional zuz N^3

ich glaube nicht das meine variange besonders optimiert ist... ich habe den code so simpel wie möglich gehalten (vielleicht macht ihn ja das genau schnell???).
auf meinem athlon TB 1.1ghz löst er ein 100x100 system in 3 milisekunden und ein 1000x1000 in 13,7 sekunden

Gregor

Original erstellt von japro:
**
ich glaube nicht das meine variange besonders optimiert ist... ...1000x1000 in 13,7 sekunden**

Jo! Da wird noch ein bischen was rauszuholen sein. Kannst ja mal versuchen, mich zu schlagen. Sollte eigentlich recht leicht möglich sein. Ich brauche (mit Java) für ein 1001*1000-System 8,4s. (1,2GHz mit mp3-Player etc. im Hintergrund)

[ Dieser Beitrag wurde am 19.12.2002 um 17:54 Uhr von Gregor editiert. ]

japro

ich poste einfach mal den code. wie gesagt ist so simpel wie mögich gehalten:

struct gaussmatrix {
   int size;
   double *matrix, *result, *solution;
};

void gauss_init(struct gaussmatrix *matrix, int n)
{
   matrix->size     = n;
   matrix->matrix   = malloc(n*n*sizeof(double));
   matrix->result   = malloc(n*sizeof(double));
   matrix->solution = malloc(n*sizeof(double));
}

void gauss_destroy(struct gaussmatrix *matrix)
{
   free(matrix->matrix);
   free(matrix->result);
   free(matrix->solution);
}

void gauss_solve(struct gaussmatrix *matrix)
{
   int col, row;
   int size = matrix->size;
   int effsize = size*size;

   for(col=0, row=0;row<size;++row, col+=size)
   {
      int nextcol;
      for(nextcol=col+size;nextcol<effsize;nextcol+=size)
      {
         int i;
         double factor = matrix->matrix[nextcol+row]/matrix->matrix[col+row];
         for(i=row;i<size;++i)
         {
            matrix->matrix[nextcol+i]-=matrix->matrix[col+i]*factor;
         }
         matrix->result[nextcol/size]-=matrix->result[col/size]*factor;
      }
   }

   for(col=effsize-size, row=size-1;row>=0;--row, col-=size)
   {
      int i;
      double right = matrix->result[row];
      for(i=row+1;i<size;++i)
      {
         right-=matrix->matrix[col+i]*matrix->solution[i];
      }

      matrix->solution[row] = right/matrix->matrix[col+row];
   }
}

ich werde jetzt für 10 tage weg sein also nicht wunder wenn ich nicht so schnell antworte

Gregor

Das folgende ist ein Großteil der Klasse, die bei mir für das Lösen linearer Gleichungssysteme zuständig ist. Ich mache bei den Gleichungssystemen allerdings ein paar Einschränkungen. Es handelt sich um ein etwas modifiziertes Gauss-Jordan-Verfahren.
[java]
/*
* EquationSystemSolver.java
*
* Created on 15. Dezember 2002, 00:01
*/

package image.linearEquationSystem;

/**
*
* @author Otaku 2
*/
public class EquationSystemSolver
{

/** Creates a new instance of EquationSystemSolver */
private EquationSystemSolver ()
{
}

/**
* @param system [row][column]
*/
public static float [] solveSystem (float [][] system)
throws NotSolvableException
{
int rows = system.length;
int columns = system[0].length;
if (rows + 1 != columns) throw new NotSolvableException ();
int [] selectedRows = new int [rows];
boolean [] usedRows = new boolean [rows];
int i,j;
int vars = columns - 1;
for (i = 0 ; i < vars ; ++i)
{
selectedRows [i] = getOptimalRow (system,i,usedRows);
usedRows [selectedRows [i]] = true;
processRow (system,i,selectedRows [i]);
}
float [] result = new float [vars];
for (i = 0 ; i < vars ; ++i)
{
result [i] = system [selectedRows [i]][vars];
}
return result;
}

/**
* @param system [row][column]
*/
private static void processRow (float [][] system, int column, int row)
{
float factor = 1.0f / system [row][column];
system [row][column] = 1.0f;
int columnCount = system[0].length;
int rowCount = system.length;
int i,j;
for (i = column + 1 ; i < columnCount ; ++i)
{
system [row][i] *= factor;
}
for (j = 0 ; j < rowCount ; ++j)
{
if (j == row) continue;
factor = system [j][column];
system [j][column] = 0.0f;
for (i = column + 1 ; i < columnCount ; ++i)
{
system [j][i] -= factor * system [row][i];
}
}
}

/**
* @param system [row][column]
*/
private static int getOptimalRow (float [][] system, int column,
boolean [] usedRows)
throws NotSolvableException
{
int selectedRow = 0;
float currentAbsValue = 0.0f;
float tempValue = 0.0f;
int rows = system.length;
for (int i = 0 ; i < rows ; ++i)
{
if (usedRows [i]) continue;
if ((tempValue = Math.abs(system[i][column])) > currentAbsValue)
{
currentAbsValue = tempValue;
selectedRow = i;
}
}
if (currentAbsValue < 1e-5f) throw new NotSolvableException();
return selectedRow;
}
}[/code]

japro

also wenn ich float anstatt double nehme löst er das 1000x1000 system in 7.4 s

Marc++us

Das ist hier nicht sonderlich angebracht. Der übliche Gauß-Algorithmus ist nämlich numerisch nicht sonderlich stabil und daher anfällig gegenüber Rechenungenauigkeiten bei Fließkommazahlen. float ist daher zwar schnell, aber die Lösung hat nicht mehr viel mit der wirklichen Lösung zu tun... mach mal die Probe, multipliziere die Lösung wieder mit der Originalmatrix, da müßte ja die Einheitsmatrix rauskommen... zumindest ungefähr, d.h. alle Diagonalelemente bei 0.95 - 1.05 und der Rest nahe bei 0. Und dann betrachte den Unterschied für double.

Üblicherweise rechnet man den Gauß wenn schon numerisch dann mit Pivot-Elementen, da sich hierdurch die numerische Stabilität erhöht.

Gregor

Hmmm.... ich habe meinen Algorithmus bisher explizit nur für kleine Gleichungssysteme getestet. ...so 2-3 Unbekannte! ...da habe ich eine Genauigkeit von 6 Stellen. Das hat mir erstmal gereicht. Ich brauche das allerdings größtenteils für Gleichungssysteme mit 16 Unbekannten. ...vielleicht sollte ich das da auch nochmal testen! ...3-4 Stellen Genauigkeit reichen mir eigentlich aus.

[ Dieser Beitrag wurde am 22.12.2002 um 17:21 Uhr von Gregor editiert. ]

Gregor

Also ich nutze meinen Gleichungsystem-löser, um eine zweidimensionale Funktion über 4*4 vorgegebene Punkte zu legen. Unten habe ich mal willkürlich ein paar Punkte vorgegeben. Rechts daneben steht, was rauskommt, wenn ich in die Funktion wieder den entsprechenden x- und y-Wert einsetze. Die Genauigkeit sollte eigentlich noch ausreichen. ...kann sein, dass das bei größeren Gleichungssystemen anders aussieht.

200.0     199.9999
150.0     150.00002
100.0     100.00008
50.0       50.000107
2.0         2.0000458
1.0         1.0000153
234.0     234.0
123.0     123.000015
255.0     255.00006
243.0     243.00002
120.0     120.000046
43.0       43.000015
9.0         9.000198
6.0         6.0000153
186.0     185.99998
149.0     148.99986