Verfasst am: 26.11.2008, 20:36
Titel: Matrix-Multiplikation und Laufzeitvergleich
Hallo,
ich muss folgende Aufgabe erledigen:
a) Schreiben Sie eine Octave-Function function [Lx] = dreiMatVecMul(L,x),
die die Matrix-Vektor-Multiplikation Lx, x Rn, ohne unnötige Rechenoperationen (d.h. Multiplikationen mit Null) durchführt. Verwenden Sie dazu keine if-Abfrage, sondern wählen Sie angepaßte Grenzen für die Laufvariablen der Schleifen. Testen Sie ihren Code am Beispiel l(ij) = i + j für i ≥ j und l(ij) = 0 sonst, sowie x = (1, . . . , 1)^T ∈ Rn und n = 10.
Ich weiß dass es auch ein Octave Unterforum gibt, aber das ist nicht so stark frequentiert wie dieses hier. Und da sich die Sprachen ja recht ähnlich sind, hoffe ich dass ihr mir weiterhelfen könnt
Ich hab auch schon etwas getan und glaube (hoffe) dass es richtig ist:
Erstmal das Script in dem der Vektor und die Matrix definiert werden:
Code:
%Aufgabe 28 a)
x = [1;1;1;1;1;1;1;1;1;1];
%Berechnung der Matrix L (Dreiecksmatrix)
%k= 10 ist die Zeilenzahl
%i= 10 ist die Spaltenzahl
Als Ergebnis kommt der Vektor Lx = (2,7,15,26,40,57,77,100,126,155)^T raus. Den bekomme ich auch, wenn ich statt dem "function-file" einfach L*x rechnen lasse. Sollte also stimmen oder?
Zur zweiten Teilaufgabe hab ich leider noch nicht ganz so viel. Meine Überlegung wäre, dass ich Octave jeweils die verschiedenen Möglichkeiten durchrechnen lasse und jeweils die Zeit nehme. Dann würde ich ein KoSy mit x-Achse = Zeit und y-Achse = n und die Graphen ploten lassen.
Nur stellt sich jetzt die Frage wie?
Zur Multiplikation sind mir 3 verschiedene Varianten eingefallen, zum einen die oben durchgeführte, dann die mit dem Falk-Schema und als letztes würde ich Octave einfach ohne "function-file" rechnen lassen (also L*x).
2. Ich würde mal behaupten, dass L*x die schnellste Variante ist, da sie intern schnell umgesetzt ist. Das Falk-Schema sagt mir nichts, die Vorgehensweise du du benutzt ist sicher eine der langsamen (du berücksichtigst du Dreieckstruktur überhaupt nicht).
Code:
Lx = dreiMatVecMul1 (L,x)
N = length(x);
Lx = zeros(N,1);
for k=1:N
for i=1:k
Lx(k) = Lx(k) + L(k,i) * x(i);
end end
NaNs deshalb, weil ich mit "zeros" ja nicht unterscheiden kann ob es da einen Fehler gab oder ob die Laufzeit wirklich 0 Zeit gedauert hat. Ausserdem werden NaNs nicht geplottet, d.h. Einträge, die aus irgendeinem Grund nicht gesetzt werden, scheinen in Diagrammen nicht auf.
Das mache ich damit Matlab in der Schleife keine Zeit benötigt, um den Zeitvektor zu vergrößern (=Speicher allozieren). Du willst ja deine Berechnungen so schnell wie möglich machen
Ich habe leider kein Octave, aber es scheint dass Octave mit einer Berechnung Schwierigkeiten hat - d.h. die Daten enthalten nur NaNs. Da Octave NaNs nicht plottet, kann natürlich für diesen Eintrag auch keine Legende erstellt werden. Was steht in den drei Vektoren t1, t2 und t3 drin? Falls irgendwo nur NaNs auftauchen, muss da was in der Berechnung von "cputime" schief gelaufen sein.
hm.. das kann mit "cputime" zu tun haben. Ich habe das bei mir mal getestet, und von 500 haben 492 den Wert 0.
Zitat:
Although it is possible to measure performance using the cputime function, it is recommended that you use the tic and toc functions for this purpose exclusively. It has been the general rule for CPU-intensive calculations run on Windows machines that the elapsed time using cputime and the elapsed time using tic and toc are close in value, ignoring any first time costs. There are cases however that show a significant difference between these two methods. For example, in the case of a Pentium 4 with hyperthreading running Windows, there can be a significant difference between the values returned by cputime versus tic and toc.
Es wird also empfohlen, statt "cputime" tic und toc zu verwenden.
also ich habe das jetzt noch einmal mit tic und toc versucht. Weiß nur nicht genau, ob ich das mit dem tic Befehl so richtig gemacht habe. Methode 1 zeigt immernoch komische Werte.
Beispiel für N=100, jetzt aber mit tic und toc:
Code:
N = 100;
t1 = nan(N,1);
t2 = nan(N,1);
t3 = nan(N,1);
for k=1:N
L = rand(k);
x = rand(k,1);
% Berechnung 1 tic;
Lx = dreiMatVecMul1(L,x);
t1(k)=toc;
Problem bei der ganzen Sache ist nur, dass wir das mit cputime lösen sollen! Denkst du dass es auch an meinem Rechner liegen kann? Ich benutze dafür meinen Laptop (P4 - 1,8Ghz - 256MB RAM). Alternativ könnte ich es auch mal an meinem Rechner versuchen (P4 - 2,4 GHz - 1,5 GB RAM).
die Verwendung von tic und toc ist so richtig. Ich habe eigentlich noch nie Laufzeitmessungen verwendet bzw. verglichen und kann deshalbt nur das zitieren, was in der Matlab-Hilfe steht (dass tic-toc besser ist als cputime). Bei mir liefert t1 allerdings eine recht schöne Kurve, sieht sehr exponentiell bzw. quadratisch aus.
Was genau steht denn in t1 drin? Sind da Nullen drin oder NaNs (ist leider aus dem Plot nicht ersichtlich)?
ich nehm die Kurven mit tic und toc, weil cputime bei mir sehr viele Werte mit Nullen enthält (da seh ich irgendwie keine Abhängigkeit von der Matrixgröße).
Versuch mal N = 500 zu wählen. Kommen da plausible Werte für die Berechnung raus? Ich kann mir das irgendwie nicht erklären - in Matlab scheint das ganze zu funktionieren.
Wenn du in den Plot reimzoomst, kannst du da zumindest eine "richtige" Tendenz feststellen? Es scheint ja dass Octave bei den ersten 3-4 Berechnungen ziemlich lange benötigt.
Die "Berge" wiederholen sich und sin jeweils gleichgroß. Eine Tendenz ist nicht erkennbar!
Ich werde die ganze Sache jetzt nochmal mit tic-toc versuchen. Ergebniss wird aber noch etwas auf sich warten lassen, da die Berechnung doch sehr zeitaufwendig ist!
die Tendenz ist mit tic-toc einigermaßen sichtbar (zoom mal horizontal etwas rein und vernachlässige die ersten paar Werte). Allerdings scheint es so dass er für die ersten Werte verhältnismäßig lang braucht. Keine Ahnung warum (unter Matlab bzw. auf meinem Arbeitsrechner sieht das bei mir eigentlich so wie erwartet aus).
Ich kann nur spekulieren warum cputime nicht richtig funktioniert. Es kann sein dass cputime nur 0.01 Sekunden auflösen kann (oder dein Rechner) - warum auch immer. Dass die Frequenz der "Berge" zum Schluss hin zunimmt liegt dann daran, dass die Berechnungen etwas länger dauern und deshalb die Möglichkeit zunimmt, dass während der Berechnung ein Taktwechsel oder so ähnlich stattfindet.
Ok danke. Ich muss es morgen abgeben, mal schauen wie das dann korrigiert wird. Wenn du willst/Interesse hast, dann kann ich dir die Lösung des Problems gerne zukommen lassen.
Wir hatten das Script heute auch mal auf einem anderem Rechner laufen lassen - selbes Ergebniss. Also entweder hat Octave da ein Problem, oder zwei Rechner auf einmal. Wobei ich auch eher vermute, dass der PC schuld ist.
Trotzdem 1000 Dank, hast mir sehr geholfen
Beste Grüße,
tycro
Einstellungen und Berechtigungen
Du kannst Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen. Du kannst Dateien in diesem Forum posten Du kannst Dateien in diesem Forum herunterladen
MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.
RSS