|
|
|
Aufwand von Norm norm(.,2) |
|
| Bachelorette |
Forum-Newbie
|
 |
Beiträge: 4
|
|
|
|
Anmeldedatum: 12.06.19
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
 |
|
Verfasst am: 12.06.2019, 13:45
Titel: Aufwand von Norm norm(.,2)
|
 |
|
Wie hoch ich ist der numerische Aufwand zur Brechnung einer Norm in Matlab mithilfe des norm(.,2)-Befehls? Insb. bei mehrdimensionalen komplexen Argumenten wie norm([1+i; 2+2i],2). Arbeitet Matlab da mit dem Heron-Verfahren, um die Wurzel zu ziehen?
|
|
|
|
|
|
| Jan S |
Moderator
|
|
Beiträge: 11.057
|
|
|
|
Anmeldedatum: 08.07.10
|
|
|
|
Wohnort: Heidelberg
|
|
|
|
Version: 2009a, 2016b
|
|
|
|
|
|
|
Verfasst am: 12.06.2019, 18:46
Titel: Re: Aufwand von Norm norm(.,2)
|
|
| |
 |
 |
Hallo Bachelorette,
Manche Matlab Funktionen sind als M-Code in den Toolboxen zu finden. Die anderen sind entweder in der Dokumentation vollständig beschrieben, oder aber nicht-öffentlich lesbar. Den Code mit einem Debugger zu unetrsuchen wäre Reverse-Engineering, was in den Lizenzbestimmungen ausdrücklich untersagt ist. Deshalb ist dann der einzige Weg, sich bei Matlab als Programmierer anstellen zu lassen :-)
Trotzdem wage ich zu behaupten, dass Matlab die Wurzel sicherlich direkt mit den entsprechenden CPU-Befehlen berechnet. Das Heron-Verfahren eignet sich für numerische Untersuchungen. In echter Hardware ist eher etwas in dieser Art implementiert: https://www.netlib.org/fdlibm/e_sqrt.c
| Zitat: |
| Wie hoch ich ist der numerische Aufwand zur Brechnung einer Norm in Matlab mithilfe des norm(.,2)-Befehls? |
Wie möchtest du den "Aufwand" denn messen? In größeren Arrays kommt es darauf an, wie die Indizierung der Elemente ausgeführt wird. Falls das mit SSE oder AVX-Code geschieht, fallen deutlich weniger Instruktionen an. Dann könnte das noch auf mehreren Cores laufen. Eine direkte Korrelation zwischen arithmetischen Operationen und Rechnenzeit gibt es also kaum noch. Was bedeutet dann genau "Aufwand"?
Gruß, Jan
|
|
|
|
| Bachelorette |
Themenstarter
Forum-Newbie
|
|
Beiträge: 4
|
|
|
|
Anmeldedatum: 12.06.19
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
|
Verfasst am: 12.06.2019, 21:01
Titel: Re: Re: Aufwand von Norm norm(.,2)
|
|
Ich kenne es eben nur aus der Numerik so, dass man bei numerischen Verfahren den Aufwand, d.h. die Rechenleistung bestimmen will. Indikator dafür war bei uns immer die Anzahl der Mutiplikationen bzw. Divisionen, z.B. hat dann die Matrix-Matrix-Multiplikationen von nxn-Matrizen einen Aufwand von n^3 (n Multiplikationen pro neuem Matrixeintrag).
Kann man analoges auch für Normen im C^n oder R^n bei deinen genannten Verfahren/Codes berechnen?
|
|
|
|
| Jan S |
Moderator
|
|
Beiträge: 11.057
|
|
|
|
Anmeldedatum: 08.07.10
|
|
|
|
Wohnort: Heidelberg
|
|
|
|
Version: 2009a, 2016b
|
|
|
|
|
|
|
Verfasst am: 13.06.2019, 17:41
Titel: Re: Re: Aufwand von Norm norm(.,2)
|
|
| |
|
|
Hallo Bachelorette,
Die Anfänger-Vorlesungen in Numerik verwenden tatsächlich die O(n) Schreibweise und die hat auch ihre Berechtigung. Wenn ein Verfahren O(3) ist, kann man im Allgemeinen davon ausgehen, dass es deutlich "langsamer" sein wird als ein O(2)-Verfahren, sobald die Daten "riesig" sind. Wenn eine Methode schon in der Theorie langsam ist, wird das in der praktischen Umsetzung wahrscheinlich ähnlich aussehen.
In der Praxis auf echten CPUs sieht das deutlich anders aus. Sowie die Berechnunen separiert werden können, laufen sie im Multi-Threading schneller - das skaliert aber nicht mit der Anzahl der Prozessoren, denn moderne Prozessoren können schon mal doppelt so schnell laufen, wenn sie nicht zu heiß werden. Beim Multi-Threading überhitzen die CPUs aber sehr schnell...
Manche Code laufen doppelt so schnell, wenn man die Matrizen spaltenweise statt zeilenweise bearbeitet, weil das RAM and die CPU-Chachs dann effizienter ausgelesen werden. In der Theorie ist davon aber nichts zu sehen.
| Zitat: |
| z.B. hat dann die Matrix-Matrix-Multiplikationen von nxn-Matrizen einen Aufwand von n^3 |
Mit dem Coppersmith–Winograd-Algorithmus bekommst du für die Matrix-Matrix-Multiplikation O(n^2.37). Mit dem Strassen-Algorithmus sind es O(n^2.87). Mit Multi-Threading sieht das noch mal anders aus.
| Zitat: |
| Kann man analoges auch für Normen im C^n oder R^n bei deinen genannten Verfahren/Codes berechnen? |
"Analoges" wozu? Im SQRT-Code der fdlibm-Bibliothek hängt die Anzahl der arithmetischen Operationen vom Input ab. Wenn der in bestimmten Regionen liegt, werden andere Algorithmen verwendet. Das könnte bei der CPU-Implementation ebenfalls so sein. Bei SSE und AVX-Code würde ich vermuten, dass sie eine feste Anzahl von Takt-Zyklen verwenden. Aber auch hier gilt wieder: Wie lange ein Takt-Zyklus ist, ist keine Konstante mehr. CPUs takten dynamisch rauf und runter. Benchmarks liefern deshalb je nach Wetterlage unterschiedliche Ergebnisse.
Welches Problem möchtest du genau lösen?
Gruß, Jan
|
|
|
|
| Bachelorette |
Themenstarter
Forum-Newbie
|
|
Beiträge: 4
|
|
|
|
Anmeldedatum: 12.06.19
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
|
Verfasst am: 13.06.2019, 17:53
Titel: Re: Re: Re: Aufwand von Norm norm(.,2)
|
|
Ich muss für meine Bachelorarbeit den Aufwand einer Vektorberechnung mithilfe der O()-Notation beschreiben.
Konkreter: x (m-i+1)-dimensionaler Vektor über C(!), dann muss ich den O()-Aufwand von
v=x+(x_1/|x_1|)*||x||_2*e_1
berechnen. An für sich nicht schwer, wenn man den Aufwand zur Berechnung einer Norm/eines Betrages kennen würde...
|
|
|
|
| Jan S |
Moderator
|
|
Beiträge: 11.057
|
|
|
|
Anmeldedatum: 08.07.10
|
|
|
|
Wohnort: Heidelberg
|
|
|
|
Version: 2009a, 2016b
|
|
|
|
|
|
|
Verfasst am: 26.06.2019, 21:57
Titel: Re: Re: Re: Aufwand von Norm norm(.,2)
|
|
Hallo Bachelorette,
Ich würde die Anzahl der Multiplikationen und Addition abzählen und dazu noch "und eine Wurzel" angeben. Da die Wurzel in Konstanter Zeit berechnet wird (näherungsweise...), spielt sie für die O(n) Betrachtung keine Rolle.
Gruß, Jan
|
|
|
|
|
|
|
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
|
|
Impressum
| Nutzungsbedingungen
| Datenschutz
| FAQ
|  RSS
Hosted by:
Copyright © 2007 - 2024
goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks
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.
|
|
