c++.de :: Schema gesucht: Sehr teure Gleichungen parallel lösen, ohne viel Rechenzeit zu verschwenden

SeppJ Moderator 20:33:05 03.05.2012 Titel:

Achtung, jetzt wird es erst einmal mathematisch (aber nicht schwer! Bloß abstrakt), ich suche aber einen Algorithmus, daher frage ich hier:

Ich habe eine Funktion §E(x)§. Die Funktionswerte sind sehr sehr teuer zu berechnen, sagen wir ein CPU-Tag, nicht parallelisierbar. Aber ich kann mehrere §E(x)§ gleichzeitig parallel berechnen.

Nun habe ich eine weitere Funktion
§F(E(x_1),E(x_2)) \text{ mit } x_1 < x_2§,
die auf diesen §E(x)§ operiert. Diese Funktion ist billig. Es gilt (falls es hilft):
§F(E(x), E(x+\delta x_1)) < F(E(x), E(x+\delta x_2)), \text{dann und genau dann, wenn } \delta x_1 < \delta x_2§
In Worten: F ist monoton, wenn man eines der Argumente festhält. (Da gibt's bestimmt auch noch Fachsprech für, das mir gerade nicht einfällt)
Außerdem ist F stetig, (numerisch) differenzierbar und alles was man sich sonst noch so wünschen kann.

Problemstellung:
Nun möchte ich eine Kette von x'en §(x_0 = x_{start}, x_1, x_2, \dots , x_{end})§ mit vorgegebenem §x_{start}§ und einem ungefähren Wunschwert §x_{end}§ erzeugen. Als Nebenbedingung soll dabei gelten
§F(E_{x_i}, E_{x_{i+1}}) = C§
wobei §C§ eine vorgegebene Konstante ist. Wegen der oben angegebenen Eigenschaft der Funktion F ist es immer möglich, zu einem gegebenen §x_i§ ein (eindeutiges) §x_{i+1}§ zu finden, für das diese Bedingung exakt erfüllt ist. Aber eine Approximation reicht mir! Sie muss noch nicht einmal besonders gut sein. Wie genau formuliert werden soll, wann eine Approximation ausreichend ist, lasse ich erst einmal offen. Meinetwegen kann man es so formulieren, dass ich eine vorgegebene Abweichung §\delta C§ toleriere.

Bedingungen an den Algorithmus:
Ich möchte nun möglichst effizient herausfinden, welchen Wert diese §x_i§ ungefähr haben müssen. Dabei möchte ich von dem Algorithmus zwei Dinge:
1. Ich will nicht ewig auf das Ergebnis warten. Ich erwarte, dass die Kette 10-50 Werte enthalten wird.Die Angabe oben mit dem einen Tag pro §E(x_i)§ war nicht übertrieben, eher untertrieben. Ich sag mal, ein bis zwei Wochen kann ich mich gedulden.
2. Ich habe nicht unendlich Ressourcen. Ja, ich kann Rechenzeit verschwenden, es muss nicht jeder berechnete Wert am Ende im Ergebnis auftauchen. Aber ich kann nicht einfach das Zielintervall in 10.000 Schritte aufteilen, zu jedem Schritt das §E§ ausrechnen und mir dann die passenden Werte rauspicken. Es muss schon irgendwie halbwegs gezielt passieren. Aber ein paar Dutzend Schüsse ins Blaue sind noch ok. Sagen wir ein paar CPU-Monate sollten insgesamt nicht überschritten werden.

So, nun suche ich Ideen, wie man das möglichst effizient machen könnte. Bitte keine ganz naiven Vorschläge, die euch beim ersten Querlesen gekommen sind. Ich habe schon eine ganze Weile darüber nachgedacht und das Problem ist nicht einfach. Ich habe aber auch nie eine informatische Algorithmenvorlesung besucht, also wenn euch die Problemstellung bekannt vorkommt, dann nur raus damit.

Was ich bisher gemacht habe:
Es gibt hier zwei/drei Probleme:
1. Eine iterative Lösung ist halbwegs schwer, da man dafür normalerweise die Ableitung von F berechnen müsste. Und dazu braucht man mehrere E. Und dann wird's teuer. Außerdem kann die Ableitung vom F durchaus wild sein, eine Approximation durch zwei weit auseinanderliegende Werte könnte schlecht sein. Aber wie schon gesagt, so schrecklich genau braucht es nicht zu sein.
2. Die Kettenbildung scheint mir inhärent seriell. Ich muss bei §x_{start}§ anfangen und mich dann von x zu x weiterhangeln. Wenn ich zwischendurch E's berechne, dann kann ich mir diese zwar merken und später vielleicht nochmal nutzen. Aber insgesamt scheint mir dadurch doch die Zeitbeschränkung schwer. Die E's die ich berechne sollten also möglichst gut angelegt sein.
(3. Metaproblem: Solche Arten von Problemen algorithmisch zu lösen habe ich nie gelernt. Hier ist man mal ganz praktisch durch Hardware und Zeit beschränkt. Ich brauche eine Lösung die in der Praxis gut funktioniert, nicht in meinem Theoretikerturm, indem ich mich bisher so wohl gefühlt habe)

Naiver Algorithmus, den ich mir ausgedacht habe:
Starte bei §x_i§. Gucke schon berechnete §E(x > x_i)§ an und bestimme so ein Intevall, in dem §x_{i+1}§ liegen muss. Dann Intervallschachtelung. Oder vielleicht besser ein Newtonverfahren? Ist halt nichtlinear

. Zwischendurch berechnete E's natürlich aufheben.

Nachteil: Ich nutze nicht die Möglichkeit, dass ich mehrere E's parallel berechnen kann, da dieser Algorithmus seriell ist.

Mögliche Verbesserung: Es könnte was bringen, das Zielintervall (sowohl das konkrete Intervall zum Berechnen des nächsten §x_{i+1}§, als auch das noch übrige Gesamtintervall, in dem §x_{i+2}§ und folgende liegen werden) im Vorhinein schon grob einzuteilen und einfach auf gut Glück ein paar E's darin verteilt zu berechnen. Das lässt aber zwei Fragen offen:
1. Ist das gut angelegte Rechenzeit? Kann ich leider gar nicht einschätzen.
2. Wie diese Werte verteilen? Ich weiß a priori gar nichts über das F, außer den oben angegebenen Bedingungen. Verteilt man die spekulativen Werte dann gleichmäßig auf dem Intervall? Oder gibt es da was besseres?

cooky451 Mitglied 21:02:53 03.05.2012 Titel:

Ich kann dir wahrscheinlich nicht wirklich weiterhelfen, einfach weil mir der mathematische Hintergrund fehlt. Mich würde aber E(x) interessieren. Kannst (darfst) du die Funktion posten?

SeppJ Moderator 21:31:52 03.05.2012 Titel:

cooky451 schrieb:

Ich kann dir wahrscheinlich nicht wirklich weiterhelfen, einfach weil mir der mathematische Hintergrund fehlt. Mich würde aber E(x) interessieren. Kannst (darfst) du die Funktion posten?

Ich könnte jetzt zwar einen Klugscheißerausdruck hinschreiben, aber das was du wissen möchtest: Die Funktionswerte sind Ergebnis einer Simulation, das x ist ein Parameter dieser Funktion.

SideWinder Moderator 21:42:45 03.05.2012 Titel:

Kann man bzgl. E gar keine Annahmen treffen? Die Funktion springt wild umher, ist weder approximierbar noch sonstwie monoton, stetig, etc.?

Wenn du nämlich "F(E(x), E(x+1)) = C +- deltaC" haben willst, und F monoton wachsend ist, dann kannst du ja ein ungefähres Wachstum von F angeben, oder? Bspw. ob F exponentiell steigt, etc.

Wenn man nun über E besser Bescheid wüsste, könnte man ja sicher eine gute Heuristik zum Raten bauen, oder?

MfG SideWinder

SeppJ Moderator 22:09:39 03.05.2012 Titel:

Das E ist stetig, es ist differenzierbar und sonstwie gutartig.

Das E ist sicherlich auch nicht wild, sprich: Die erste und zweite Ableitung ist eher klein. Man kann erwarten, dass es im Gesamtintervall vielleicht ein bis zwei "Schwingungen" macht. (kein ganz zutreffendes Wort, da es keine reelle Zahl ist, aber das trifft's ganz gut)
Wie könnte mir das helfen? Heuristik klingt gut. Man könnte die auch ein bisschen anfüttern, indem man vorher das Gesamtintervall grob absteckt.

Was dem jedoch zuwieder läuft: In das F fließen immer zwei E's ein, es zählt eher so etwas wie die Differenz zweier Werte (ist leider etwas komplizierter). Daher nützt mir der absolute Wert des E nicht so viel, es zählt eher das Verhalten. Könnte jedoch gehen, indem man die erste Ableitung abschätzt.

knivil Mitglied 22:21:42 03.05.2012 Titel:

§F(E_{x_i}, E_{x_{i+1}}) - C = 0§ Damit reduziert es sich auf das Finden von Nullstellen, da §x_i§ bzw. §x_{start}§ vorgegen ist. Wenn F, wie du sagst, billig ist, kann der Wer von §E(x_{i+1})§ berechnet werden. Dann bleibt §0 = E(x) - E(x_{i+1})§ wieder als Nullstellenproblem uebrig. ... so als Anzatz.

SeppJ Moderator 23:22:30 03.05.2012 Titel:

knivil schrieb:

§F(E_{x_i}, E_{x_{i+1}}) - C = 0§ Damit reduziert es sich auf das Finden von Nullstellen, da §x_i§ bzw. §x_{start}§ vorgegen ist. Wenn F, wie du sagst, billig ist, kann der Wer von §E(x_{i+1})§ berechnet werden. Dann bleibt §0 = E(x) - E(x_{i+1})§ wieder als Nullstellenproblem uebrig. ... so als Anzatz.

Kapier ich gerade irgendwie nicht.

Zitat:

Wenn F, wie du sagst, billig ist, kann der Wer von §E(x_{i+1})§ berechnet werden.

Jain. Ein nötiger Wert kann berechnet werden. Es gibt aber mehrere Möglichkeiten dafür. Ich weiß aber nur, dass konstruktionsbedingt eine dieser Möglichkeiten auftreten wird. Aber nehmen wir mal an, ich kenne das nötige §E(x_{i+1})§, dann will ich ja wissen, was §x_{i+1}§ ist:

Zitat:

Dann bleibt §0 = E(x) - E(x_{i+1})§ wieder als Nullstellenproblem uebrig.

Ja. Aber das zu lösen ist doch gerade mein Problem, bloß umformuliert.

Michael E. Mitglied 23:58:21 03.05.2012 Titel:

Seien §x_1 < x_2 < x_3§. Wenn man §F(E(x_1), E(x_2))§ und §F(E(x_1), E(x_3))§ hat, welche Aussagen kann man dann für §F(E(x_2), E(x_3))§ machen?

knivil Mitglied 00:06:10 04.05.2012 Titel:

SeppJ schrieb:

Ja. Aber das zu lösen ist doch gerade mein Problem, bloß umformuliert.

Ja, aber es steht jetzt explizit als Nullstellenproblem da. Nunn kannst du beispielsweise Intervallschachtelung anwenden und parallelisierst diese. Normalerweise berechnest du den naechsten Punkt E(x') und entscheidest dann, ob mit E(x+dx) oder E(x-dx) fortgefahren wird. E(x'), E(x+dx) und E(x-dx) kannst du parallel berechnen. PS: Das ist ein sehr naiver Ansatz.

audacia Mitglied 02:17:48 04.05.2012 Titel:

http://ars.userfriendly.org/cartoons/?id=19980708