Matrixmultiplikation, traditionelle Methode

[p. specht]

Abt. Matrixmultiplikation, traditionelle Methode
==============================
Beschleunigung wäre sehr wünschenswert (Stichwort "Physikrechnen").
Dieser traditionelle Algorithmus ist nur bei eher voll belegten Matrizen sinnvoll. Für sogenannte 'Sparse-Matrizen' (schwach - meist entlang der Haupt- oder Nebendiagonale besetzte Matrizen; solche treten insb. im Bereich Finite Elemente Methode bei Statikberechnungen auf) gibt es schnellere Methoden:

' Traditionelle Matrixmultiplikation V1.3beta (Demo by P.Specht. Nur zu Timingzwecken gedacht!)
' HIER GEWÜNSCHTE TESTDIMENSIONEN EINGEBEN:
' Zeilen,Spalten von A / Gestürzte Spalten s&, gestürzte Zeilen t& von B

  var z&= 1000 : var s&= 100 : var t&= 100

' Vorbereitung
WindowTitle "Traditionelle Matrixmultiplikation (Nur für Timingzwecke)"
Font 2:@Set("RandSeed",10):Cls rnd(8^8)
set("Decimals",18)
Declare A![z&,s&],B![s&,t&],C![z&,t&],i&,j&,k&,w!,tm&,a$


' Matrix A traditionell mit Zufallswerten <> 0 belegen
Print " Erforderlicher Speicherplatz: ";int(((z&*s&+s&*t&+z&*t&)*8));" Byte"
Print " Matrix-Zufallsbelegung..."


tm&=&GetTickCount
i&=1:While i&<=z&
  j&=1:While j&<=s&
    w!=(50000000-rnd(100000000))/rnd(50000000)+1
    A![i&,j&]=w!
  inc j&:Endwhile
inc i&:Endwhile
tm&=&GetTickCount-tm&
Print " Matrix A ("+str$(int(s&*z&))+" Elemente) traditionell belegt in "+str$(tm&)+" ms."



' &Index hier genullt, da er nur als schnelle Schleife benötigt wird:
tm&=&GetTickCount
b![]=rnd(99999+0*&Index)+1
tm&=&GetTickCount-tm&
Print " Matrix B ("+str$(int(s&*t&))+" Elemente) Highspeed-zufallsbelegt in "+str$(tm&)+" ms."



' Möglichkeit zur Überprüfung der Matrixfunktion an Hand einfacher Matrizen:
If 0  ' Funktionstest 0 = Off , 1 = ON
  z&=2 : s&=2 : t&=2
' Matrix A =
  A![1,1]=2 : A![1,2]=0
  A![2,1]=0 : A![2,2]=1
' Matrix B =
  B![1,1]=2 : B![1,2]=0
  B![2,1]=0 : B![2,2]=1
Endif


Print " Die Matrizen sind verlinkt in Breite "+str$(s&)+" A-Spalten=B-Zeilen."
Beep
Print " ";int(z&*s&*t&);" Multiplikationen und Additionen erforderlich."
print "\n Zum Start der Matrixmultiplikation Taste drücken!"
SetTimer 12000 : WaitInput : killtimer
Print "\n Berechnung der "+str$(int(z&*t&))+" Elemente von C läuft."
Print " Ein Punkt steht jeweils für "+str$(int(t&))+" fertige Elemente."
print " Das wird ca. "+str$(int(z&/61+1))+" Zeilen benötigen."


if 0
$MAKE CL
endif
' Traditionelle Matrixmultiplikation
tm&=&GetTickCount
W!=0
i&=1:While i&<=z&
   k&=1:While k&<=t&
      w!=0
      j&=1:While j&<=s&
          w!=w!+A![i&,j&]*B![j&,k&]
      inc j&:Endwhile
      C![i&,k&]=w!
  inc k&:Endwhile
  print ".";
  case %pos>61:print
  case %csrlin>22:cls
inc i&:Endwhile:print
tm&=&GetTickCount-tm&


Beep
Print " 2 Matrizen multipliziert in "+ if( tm& > 9000 , str$(tm&\1000)+" sec." ,str$(tm&)+" ms." )
Print "\n Ergebnis C ausgeben?"
WaitInput
case IsKey(27):end
case IsKey(78):end
' Ausgabe der Ergebnis-Matrix C
CLS


tm&=&GetTickCount
i&=1:While i&<=z&
   print "********* Zeile "+trim$(str$(i&))+" von "+trim$(str$(z&))+":  *********"
   k&=1:While k&<=t&
     if %csrlin>22:SetTimer 700: WaitInput :Killtimer:cls:endif
     Print "S"+trim$(str$(k&))+":"+format$("%e",C![i&,k&]),
     case %pos > 50:print
   inc k&:Endwhile :print 
inc i&:Endwhile
tm&=&GetTickCount-tm&
Print "\n Matrix C ausgegeben in " + if( tm& > 9000 , str$(tm&\1000)+" sec." , str$(tm&)+" ms." )


WaitInput
End

EDIT: In V1.3beta noch etwas beschleunigt und deutlich gesprächiger gemacht...