Hi!
Für ein Projekt bin ich auf der Suche nach einer Bibliothek für lineare
Algebra für einen Atmega1280.
Es müsste ein 10x10-generalized-eigenvalue-problem gelöst werden (in
floating-point-arithmetik). Habt ihr da schonmal was von gehört, obs da
was für gibt?
Bzw. denkt ihr, dass das der 1280 überhaupt schaffen könnte? Falls es
gar nichts gibt, könnte ich höchstens noch versuchen, normale PC-Libs zu
portieren, aber ob die dann dort auch funktionieren, bezweifle ich...
Liebe Grüße, Max
etMax schrieb:> 10x10-generalized-eigenvalue-problem
Du brauchst dazu sowas wie einen Matrixcompiler. Gaußsches
Eliminationsverfahen wäre doch ein Weg?
mfg mf
mit dem GCC?
besorg dir dann auch gleich noch ein Floating Point Packet mit echten
double dazu. Mit 4 Byte float wirst du mit den Rechenergebnissen nicht
glücklich werden.
@Mini float:
ich habe noch nie von einem matrix-compiler gehört, auch google spuckt
da nichts interessantes aus...
Ich dachte auch evtl. an eine bereits fertige Lib, da eine eigene
Implementierung sicherlich a) langsamer und b) ungenauer c) aufwändiger
sein würde, als etwas fertiges.
@Karl-Heinz:
meinst du dazu sowas wie SoftFloat
(http://www.jhauser.us/arithmetic/SoftFloat.html) ?
Gruß, Max
etMax schrieb:> Es müsste ein 10x10-generalized-eigenvalue-problem gelöst werden
Ich hab ein bischen gegoogled, was das bedeuten könnte, aber nur Bahnhof
verstanden.
Ich kann mir ehrlich gesagt überhaupt nichts darunter vorstellen.
Wofür kann man das denn praktisch auf einem Microcontroller einsetzen?
etMax schrieb:> Bzw. denkt ihr, dass das der 1280 überhaupt schaffen könnte?
Dazu mußt Du diese Black-Box aufdröseln, also in einen konkreten
Algorithmus umsetzen.
Und dann abschätzen, welche und wie viele Rechenoperationen man dafür
benötigt und wieviele Variablen.
Wie schnell muß denn eine solche Berechnung ausgeführt werden?
Peter
etMax schrieb:> Es müsste ein 10x10-generalized-eigenvalue-problem gelöst werden (in> floating-point-arithmetik). Habt ihr da schonmal was von gehört, obs da> was für gibt?>> Bzw. denkt ihr, dass das der 1280 überhaupt schaffen könnte?
hast du noch restraints bzgl. timing? Ich nehme doch an, du brauchst die
Daten auch innerhalb eines gewissen Zeitfensters, oder?
Peter Dannegger schrieb:> Ich hab ein bischen gegoogled, was das bedeuten könnte, aber nur Bahnhof> verstanden.
Mit den Eigenwerten einer Matrix kommt man auf die Eigenvektoren einer
Matrix.
*Mathematik für Ingenieure II ausgrab, staubwisch, hust, röchel*
sei A die Matrix, Xi ein Eigenvektor dieser Matrix, Li ein
Eigenwert(ist ein Skalar also eine Zahl), E die Einheitsmatrix, i ist
eine natürliche Zahl um die Eigenvektoren und Eigenwerte zu
beziffern/zählen(mehr dazu später).
Es gilt die Charakteristische Gleichung: A * Xi = Li * Xi
Kochrezept zum Finden von Eigenwerten/-Vektoren:
1.Bestimmungsgleichung: det(A - Li * E) = 0
Es gibt nun hoffentlich eine wenn nicht mehrere Lösungen für Li.
2.Die Setzt man in die Charakteristische Gleichung ein und erhält
generalisierte Ausdrücke, die die Xi bestimmen lassen.
3.Linear voneinander abhängige Koeffizienten(jeweils einem vielfachen
voneinander entsprechend + evtl. ein "Offset") in Xi kann man
zusammenfassen und durch Skalare Koeffizienten a,b,c ausdrücken.
IMHO gibt es so viele Eigenvektoren einer Matrix, wie ihr Rang
ist(stimmt das??).
Mathe II wieder eingrabetMax schrieb:> ich habe noch nie von einem matrix-compiler gehört
Ja äh, ich meinte damit, dass du einen Algorithmus implementieren musst,
der durch inkrementelles Vorgehen deine Lösung(en) findet. Dazu eignet
sich z.B. das Gaußsche Eliminationsverfahren. Ich frage mich aber
gerade, ob das auch funktioniert, wenn zwei "Zeilen" linear voneinander
abhängig sind.
mfg mf
etMax schrieb:> Es müsste ein 10x10-generalized-eigenvalue-problem gelöst werden (in> floating-point-arithmetik). Habt ihr da schonmal was von gehört, obs da> was für gibt?
Was heisst "generatized"?
Ist die Matrix noch nichtmal symmetrisch/positiv definit?
Mini Float schrieb:> etMax schrieb:>> ich habe noch nie von einem matrix-compiler gehört> Ja äh, ich meinte damit, dass du einen Algorithmus implementieren musst,> der durch inkrementelles Vorgehen deine Lösung(en) findet. Dazu eignet> sich z.B. das Gaußsche Eliminationsverfahren.
Nein. Das ist absolut ungeeignet wegen schlechter Konditionierung.
> Ich frage mich aber gerade, ob das auch funktioniert,> wenn zwei "Zeilen" linear voneinander abhängig sind.
Auch dann gibt es Eigenwerte und Eigenvektoren.
Johann L. schrieb:> Mini Float schrieb:>> etMax schrieb:>>> ich habe noch nie von einem matrix-compiler gehört>> Ja äh, ich meinte damit, dass du einen Algorithmus implementieren musst,>> der durch inkrementelles Vorgehen deine Lösung(en) findet. Dazu eignet>> sich z.B. das Gaußsche Eliminationsverfahren.>> Nein. Das ist absolut ungeeignet wegen schlechter Konditionierung.
Das is mal n Argument!
Dann mach nen besseren Vorschlag, das interessiert mich jetzt nämlich
auch(trotz eines -sich mir noch nicht ganz erschließenden-
Anwendungsbereiches).
mfg mf
Für meine Diplom-Arbeit habe ich mal ein Ersatzschaltbild aus 700
Kondensatoren durchgerechnet. Das habe ich mit Gauß-Verfahren und
Pivotisierung gemacht. In meiner Not hatte ich das in aller Eile
übrigens mit BASIC in einen ZX Spectrum Homecomputer gehackt. Ich weiß
noch, daß das Teil die ganze Nacht durchgerechnet hat...
Schwingi schrieb:> ein Ersatzschaltbild aus 700 Kondensatoren
würde ich nicht in einen Atmega quetschen wollen.
Vielleicht erfahren wir ja auch irgendwann, dass der TO eine ganz andere
Lösung gefunden oder sein Problem auf ein anderes zurückgeführt hat.
Diese beiden Zitate gehören einfach zusammen:
Thomas Klima schrieb:> restraints bzgl. timingSchwingi schrieb:> Ich weiß noch, daß das Teil die ganze Nacht durchgerechnet hat
:D mfg mf
Naturlich kann man fuer eine 10x10 Matrix die Eigenwerte rechnen. Ich
erinnere mich an einen iterativen Algorithmus. Der Speicherbedarf ist
100 Plaetze zu 8 byte fuer double. Das hat Platz im 1280er. Mein
Compiler kann zB kein double. Aber machbar sollte es trotzdem sein.
Allenfalls als Fixedkomma. Dann muss man nur noch zuruecklehnen und
warten bis der Algorithmus konvergiert.
Mini Float schrieb:> Johann L. schrieb:>> Mini Float schrieb:>>> etMax schrieb:>>>> ich habe noch nie von einem matrix-compiler gehört>>> Ja äh, ich meinte damit, dass du einen Algorithmus implementieren musst,>>> der durch inkrementelles Vorgehen deine Lösung(en) findet. Dazu eignet>>> sich z.B. das Gaußsche Eliminationsverfahren.>>>> Nein. Das ist absolut ungeeignet wegen schlechter Konditionierung.> Das is mal n Argument!> Dann mach nen besseren Vorschlag,
Für solch kleine Matrizen etwa QR-Algorithmus.
Oder man suche zB nach Eigenwertproblem oder Säkulargleichung
Danke für eure Antworten!
also nochmal zum Problem genau:
geg. ist die Matrix A (10x10, nicht-singulär, symmetrisch) und C
(singulär, symmetrisch). Zu lösen ist das folgende Gleichungssystem:
A*x=l*C*x, dabei sind x die zu bestimmenden Eigenvektoren und l die dazu
passenden Eigenwerte. Das ist das generalisierte Eigenwertproblem. Es
gibt 10x und 10passende l, wovon einige "Inf" sind. Es ist also leider
nicht einfach Ax=lx zu lösen.
Man könnte A invertieren (allerdings ist diese Matrix fast singulär ->
instabile Invertierung) und es umformen zu x/l=A^-1*C*x, was ein
normales Eigenwertproblem ist, aber A^-1*C ist nicht mehr symmetrisch,
was auch nicht mehr gut ist.
Die Berechnung darf/sollte nicht länger als 20ms dauern. Es geht um die
Online-Kalibrierung eines Magnetometers und wenn die Berechnung zu lange
dauert, können andere wichtige Codeteile nicht oft genug ausgeführt
werden.
Prinzipiell geht es mir aber vorrangig um die Möglichkeit, das überhaupt
auf einem Atmaga machen zu lassen, da ich gelesen habe, dass die
algoritmische Umsetzung davon alles andere als simpel ist. Ich suchte
also eigentlich nach Bibliotheken dafür :)
etMax schrieb:> Die Berechnung darf/sollte nicht länger als 20ms dauern.
20ms mit dem 1280 -> Vergiß es! Die Berechnung könnte er schaffen,
codetechnisch. Aber der Rechenknecht wäre hauptsächlich mit kopieren
beschäftig.
etMax schrieb:> geg. ist die Matrix A (10x10, nicht-singulär, symmetrisch) und C
Also, für diesen Anspruch würde ich Dir einen Mikrocontroler mit FPU
mindestens jedoch ein 32-Bitter. dringend empfehlen.
TC 1796 / 1762 etc. oder Freescale MP5556 oder diverse. Es gibt da
bestimmt auch was von ARM (Cortex)
Wenn Du abenteuerlustig bist, bestände mit AT32UC3C0512 ein AVR32 zur
Verfügung der eine hardware Fließkomma-Einheit hat. Die wird jedoch mit
dem GNU aus C nicht unterstützt (Kenntnisstand 03/2011).
Übrigens nur mal so interessehalber, wie willst Du den die Berechnung
programmieren? Prozedural in C ? Das wäre sehr fehleranfällig und
erfordert ein Höchstmass an Disziplin.
Schon über automatische Codegenerierung mit Matlab oder SciLab
nachgedacht?
Nur so als Tip.
Eigenwerte lassen sich mit diesem
http://en.wikipedia.org/wiki/Jacobi_eigenvalue_algorithm
Algorithmus berechnen. Der benötigt für einen 'sweep' O(n^3)
Multiplikationen, also in Deinem Fall etliche Tausend.
Außerdem muß Du das Problem vorher degeneralisieren ( 'Numerical recipes
in C'), kostet auch nochmal. Um das in 20ms zu schaffen brauchst Du nen
mittelfetten DSP, mit nem uC gehts vielleicht in nem Stündchen.
Interessantes Thema.
Machs mit nem FPGA, das macht dann auch noch richtig Spaß.
Cheers
Detlef
Hallo,
bei http://www.trumphurst.com/cpplibs/cpplibs.php
findet man das zum Beispiel, aber ob das auf einem Controller läuft?
Villeicht ARM, mit ext. Memory.
Aber Versuch macht kluch...
:-)
Robert
> Die Berechnung darf/sollte nicht länger als 20ms dauern.> Es geht um die Online-Kalibrierung eines Magnetometers und> wenn die Berechnung zu lange dauert, können andere wichtige> Codeteile nicht oft genug ausgeführt werden.
Na ja. Das bedeutet ja nicht, dass die Berechnung in Summe nicht länger
als 20ms dauern darf. Es bedeutet nur, dass du deine Berechnung in
Happen aufteilen musst, von denen jeder einzelne nicht länger als 20ms
dauern darf.
Wenn die Kalibrierung 2 Minuten läuft und dabei alle 20ms die Kontrolle
abgibt, so dass andere lebenswichtige Operationen eine Chance haben, ist
das sicherlich auch ok.
