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 eingrab 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. 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. timing Schwingi schrieb: > Ich weiß noch, daß das Teil die ganze Nacht durchgerechnet hat :D mfg mf
Schwingi schrieb: > Für meine Diplom-Arbeit habe ich mal ein Ersatzschaltbild aus 700 > Kondensatoren durchgerechnet. Uh, Details bitte ;-)
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.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.