Methoden zur Lösung nichtlinearer Advektionsdiffusionssysteme jenseits von Newton-Raphson?

Ich arbeite an einem Projekt, bei dem ich zwei Adv-Diff-gekoppelte Domänen über ihre jeweiligen Quellterme habe (eine Domäne fügt Masse hinzu, die andere subtrahiert Masse). Der Kürze halber modelliere ich sie im stationären Zustand. Die Gleichungen sind Ihre Standard-Advektions-Diffusionstransport-Gleichung mit einem Quellterm, der wie folgt aussieht:

\frac{\partial c_{1}}{\partial t} = 0 = F_{1} + Q_{1} (c_{1}, c_{2}) \frac{\partial c_{2}}{\partial t} = 0 = F_{2} + Q_{2} (c_{1}, c_{2})

$\frac{\partial c_1}{\partial t} = 0 = \mathcal{F}_1 + \mathcal{Q}_1(c_1,c_2) \\ \frac{\partial c_2}{\partial t} = 0 = \mathcal{F}_2 + \mathcal{Q}_2(c_1,c_2)$

Wobei $\mathcal{F}_i$ ein diffusiver und vorbeugender Fluss für Spezies $i$ ist und $\mathcal{Q}_i$ der Quellterm für Spezies $i$ .

Ich konnte mit der Newton-Raphson-Methode einen Löser für mein Problem schreiben und habe die beiden Domänen mithilfe einer Blockmassenmatrix vollständig gekoppelt, dh:

F_{c o u p l e d} = [\begin{array}{cc} A_{1} & 0 \\ 0 & A_{2} \end{array}] \underset{x_{i}}{\underset{⏟}{[\begin{matrix} c_{1, i} \\ c_{2, i} \end{matrix}]}} - [\begin{matrix} b_{1} (c_{1, i}, c_{2, i}) \\ b_{2} (c_{1, i}, c_{2, i}) \end{matrix}]

$F_{coupled} = \left[\begin{array}{c c} A_1 & 0 \\ 0 & A_2 \\ \end{array}\right]\underbrace{ \left[\begin{array}{c} c_{1,i} \\ c_{2,i} \\ \end{array}\right] }_{x_i} - \left[\begin{array}{c} b_1(c_{1,i}, c_{2,i}) \\ b_2(c_{1,i}, c_{2,i}) \\ \end{array}\right]$

Der Begriff wird verwendet, um die Jacobi-Matrix zu bestimmen und sowohl als auch aktualisieren : $F_{coupled}$ $c_1$ $c_2$

J (x_{i}) [x_{i + 1} - x_{i}] = - F_{c o u p l e d}

$\mathcal{J}(x_i) \left[x_{i+1} - x_i \right] = -\mathcal{F}_{coupled}$

oder

x_{i + 1} = x_{i} - {(J (x_{i}))}^{- 1} F_{c o u p l e d}

$x_{i+1} = x_i - \left(\mathcal{J}(x_i)\right)^{-1} \mathcal{F}_{coupled}$

Um die Dinge zu beschleunigen, berechne ich den Jacobi nicht bei jeder Iteration - im Moment spiele ich alle fünf Iterationen, was anscheinend gut genug funktioniert und die Lösung stabil hält.

Das Problem ist: Ich werde auf ein größeres System umsteigen, in dem sich beide Domänen in 2D / 2.5D befinden, und die Berechnung der Jacobi-Matrix wird meine verfügbaren Computerressourcen schnell erschöpfen. Ich baue dieses Modell, um es später in einer Optimierungseinstellung zu verwenden, sodass ich nicht bei jeder Iteration hinter dem Lenkrad sitzen kann, um den Dämpfungsfaktor usw. einzustellen.

Habe ich Recht, woanders nach einem robusteren Algorithmus für mein Problem zu suchen, oder ist das so gut wie es nur geht? Ich habe mich ein wenig mit Quasi-Linearisierung befasst, bin mir aber nicht sicher, wie sie auf mein System anwendbar ist.

Gibt es andere raffinierte Algorithmen, die ich möglicherweise übersehen habe und die ein System nichtlinearer Gleichungen lösen können, ohne den Jacobi als Straftat neu zu berechnen?

nonlinear-equations newton-method advection-diffusion coupling cbcoutinho
quelle

Haben Sie iterative Löser wie AMG - algebraische Multigrid-Methoden in Betracht gezogen? Möglicherweise müssen Sie gute Vorkonditionierer entwickeln, die auf Physik basieren.

NameRakes

Können Sie auf einen Computercluster zugreifen, in dem Sie die Jacobi-Formation und -Lösung mithilfe eines parallelen linearen Algebra-Pakets verteilen können?

Bill Barth

Nein, ich habe AMG nicht in Betracht gezogen. Ich dachte, diese sind nur für symmetrische Systeme gedacht und können nicht bei konvektionsdominierten Problemen verwendet werden. Ich werde noch einmal in der Literatur nach AMG suchen.

cbcoutinho

Parallele Berechnungen sind schwierig, da dieses Projekt als eigenständige Anwendung für Kollegen entwickelt wird, die keinen Zugriff auf diese Art von Ressourcen haben. Ich dachte darüber nach, mpi für mich selbst in das Projekt zu entwickeln, aber das würde die Eintrittsbarriere für andere erhöhen, was in erster Linie der

springende

Warum ist die Berechnung des Jacobian so problematisch? Wenn Sie endliche Differenzen / Volumina / Elemente verwenden, sollte es einen spärlichen Teil haben, der immer gleich ist, und einen diagonalen Teil, der sich ändert, aber trivial zu berechnen ist.

David Ketcheson

Antworten:

Ich gehe davon aus, dass die Einschränkung in 2D und 3D den Jacobian speichert.

Eine Möglichkeit besteht darin, die Zeitableitungen beizubehalten und einen expliziten "Pseudo" -Zeitschritt zu verwenden, um in den stationären Zustand zu iterieren. Normalerweise wird die CFL-Nummer, die Sie für diffusive und reaktive Systeme benötigen, möglicherweise unerschwinglich klein. Sie können nichtlineares Multigrid (auch als Full Approximation Storage Multigrid bezeichnet) und lokale Zeitschritte ausprobieren, um die Konvergenz zu beschleunigen.

D F (u^{n}) δ u^{n} = - F (u^{n})

$DF(u^n)\, \delta u^n = -F(u^n)$

D F

$DF$

D F (u^{n}) δ u \approx \frac{F (u^{n} + ϵ \frac{δ u}{‖ δ u ‖}) - F (u^{n})}{ϵ} .

$DF(u^n)\, \delta u \approx \frac{F(u^n+\epsilon\frac{\delta u}{\Vert\delta u\Vert}) - F(u^n)}{\epsilon}.$

A

$A$

A x

$Ax$

x

$x$

Mit einem korrekten Wert von (normalerweise ungefähr für Floats mit doppelter Genauigkeit) können Sie jetzt eine Newton-Schleife ausführen, ohne jemals einen Jacobian zu berechnen oder zu speichern. Ich weiß, dass diese Technik verwendet wird, um einige nicht triviale Fälle in der rechnergestützten Fluiddynamik zu lösen. Es ist jedoch zu beachten, dass die Anzahl der Auswertungen der Funktion größer ist als bei einer Matrixspeichertechnik, anstatt ein Matrixvektorprodukt zu erfordern. $\epsilon$ $10^{-7}$ $F$

Eine andere Sache, die Sie beachten sollten, ist, dass Sie, wenn Ihr System so ist, dass ein leistungsfähiger Vorkonditionierer benötigt wird (dh Jacobi oder Block-Jacobi nicht ausreichen), möglicherweise versuchen möchten, die oben erwähnte Methode als Glatter in einem Multigrid-Schema zu verwenden. Wenn Sie einen Punkt- oder Block-Jacobi-Vorkonditionierer ausprobieren möchten, können Sie nur die diagonalen Elemente oder diagonalen Blöcke des Jacobi berechnen und speichern, was nicht viel ist. Ich würde auch erwähnen, dass ein Gauß-Seidel- oder SSOR-Vorkonditionierer möglicherweise implementiert werden kann, ohne einen Jacobian explizit zu speichern. In diesem Artikel wird die Implementierung eines matrixfreien GMRES beschrieben, das mit matrixfreiem symmetrischem Gauß-Seidel im Kontext der rechnergestützten Fluiddynamik vorkonditioniert wurde.

Aditya Kashi
quelle

Aus meiner Erfahrung mit Navier-Stokes-Gleichungen kann man sehr gut ohne vollständig implizite Schemata auskommen.

Wenn Sie nur ein schnelles numerisches Schema für die Lösung der Zeitentwicklung wünschen, werfen Sie einen Blick auf IMEX-Schemata (implizit-explizit). siehe zB diese Arbeit von Ascher, Ruuth, Spiteri Implizit-Explizite Runge-Kutta-Methoden für zeitabhängige partielle Differentialgleichungen .

Sie können sogar versuchen, nur ein explizites Zeitintegrationsschema höherer Ordnung mit Schrittgrößensteuerung (wie bei Matlab ODE45) zu verwenden. Sie können jedoch aufgrund der Steifheit Ihres Systems, die vom diffusiven Teil herrührt, auf Probleme stoßen. Glücklicherweise ist der diffusive Teil linear, so dass er implizit behandelt werden kann (was die Idee der IMEX-Schemata ist).

Jan.
quelle

Zuerst wollte ich nur eine Bemerkung hinzufügen, aber der Platz reichte nicht aus, deshalb füge ich eine kurze Beschreibung meiner Erfahrungen mit diesem Thema hinzu.

ich zunächst Ihre Notation von sehe ich die gekoppelte Form nicht. Ich nehme an, dass und beide von und abhängig sind . Wenn und Matrixdarstellungen von Approximationen von und , sollten sie nicht nur von , sondern auch von Nachbarwerten abhängen , aber dies kann nur ein falsches Verständnis Ihrer Notation sein . $F_{coupled}$ $b_1$ $b_2$ $c_{1,i}$ $c_{2,i}$ $A_1$ $A_2$ $\mathcal{F}_1$ $\mathcal{F}_2$ $c_i$

Als allgemeinen Kommentar möchte ich hinzufügen, dass die Verwendung von analytischem Jacobian der einzige Weg zu sein scheint, um eine quadratische Konvergenz des nichtlinearen iterativen Lösers (dh des Newton-Raphson-Lösers in Ihrem Fall) zu erhalten. Haben Sie es in Ihrem Fall beobachtet? Dies ist sehr wichtig, da es sonst zu Missverständnissen bei Ihren Approximationen kommen kann (Linearisierung).

In allen Anwendungen, an denen ich beteiligt war (einige davon enthielten Berechnungen in großem Maßstab), hatten wir nie Probleme mit dem Zeitaufwand beim Zusammenbau des Jacobian. Das zeitaufwändigste Problem war immer die Anwendung eines linearen Lösers. Der analytische Jacobi (falls verfügbar) war immer in Anwendungen enthalten, an denen ich aufgrund der quadratischen Konvergenz an der bevorzugten Wahl gearbeitet habe. In einigen Fällen erzeugt ein solcher nichtlinearer Löser eine Matrix, die Probleme bei der Konvergenz des iterativen linearen Lösers verursacht. Daher haben wir versucht, eine einfachere Linearisierung als den analytischen Jacobian zu verwenden, um dem linearen Löser zu helfen. Ein solcher Kompromiss zwischen dem Verhalten eines nichtlinearen und eines linearen algebraischen Lösers in Abhängigkeit von der Linearisierung eines nichtlinearen algebraischen Systems war immer schwierig, und ich konnte keine allgemeine Empfehlung abgeben.

Sie haben jedoch Recht, dass der Nachteil (oder die Eigenschaft) des analytischen Jacobian für das PDE-System darin besteht, dass es ein gekoppeltes algebraisches System erzeugt. Wenn Sie also ein solches System auf irgendeine Weise entkoppeln, z. B. die Approximation jeder PDE durch beispielsweise iterative Aufteilung separat lösen Methode, dann verlieren Sie wieder die quadratische Konvergenz des globalen Lösers. Aber zumindest wenn Sie jede diskretisierte (entkoppelte) PDE separat lösen, können Sie die Lösung für dieses spezielle Problem mithilfe der Newton-Raphson-Methode erneut beschleunigen.

Peter Frolkovič
quelle

Grüß dich @Peter, du hast Recht mit der Kopplung, ich habe die Hauptgleichung bearbeitet, um zu zeigen, und und sind beide Funktionen von und . Die Matrizen und in diesem Fall die Steifheitsmatrizen beider Systeme, die nach der Finite-Elemente-Methode entwickelt wurden. Dies sind nur Funktionen der Koordinaten der Knoten und nicht der Zustandsvariablen. und sind Vektoren, also Funktionen eines Vektors von Zustandsvariablen, nicht nur einer Variablen. Ich berechne einen Jacobi numerisch mit endlichen Differenzen. Ich habe bisher keinen analytischen Jacobianer untersucht.

b_{1}

$b_1$

b_{2}

$b_2$

c_{1}

$c_1$

c_{2}

$c_2$

A_{1}

$A_1$

A_{2}

$A_2$

F_{1}

$F_1$

F_{2}

$F_2$

cbcoutinho