Missverständnis der Wärmemethode
Ich habe eine Weile versucht, ein Papier in CG zu verstehen , das von Ken als Wärmemethode bezeichnet wird
Viele Dinge haben geklickt, aber ich verstehe es noch nicht ganz. Speziell.
Im Folgenden $u$ ist ein Vektor mit Dimensionen, die der Anzahl der Eckpunkte in einem Netz entsprechen.
Das Papier besagt, dass das Lösen $(id - t\Delta)u_t = u_0$ist eine zeitdiskretisierte Approximation des Wärmeflusses auf einer Oberfläche. Umschreiben gibt:$u_t = u_0 + t\Delta u_t $ oder auf Englisch der Wärmestrom zur Zeit $t$ ist gleich dem Wärmefluss zum Zeitpunkt 0 plus dem Laplace von $u$ zum Zeitpunkt $t$. Das ist nur eine rückwärts gerichtete Euler-Methode, die ziemlich einfach ist.
Dann bekommen wir das: $(M - tL_C)u = δγ,$ Dies ist zusammenfassend dasselbe wie oben, außer dass wir das Medium als Dreiecksnetz diskretisiert haben.
$M$ ist eine quadratische Diagonalmatrix, in der der Eintrag $m_{i,i}$ ist 2 mal ein Drittel der Summe der Flächen der Dreiecke, die den Scheitelpunkt enthalten $i$. In Mathe$m_{i,i} = 2\sum_j A_j / 3$ wo $A_j$ sind die Bereiche der Dreiecke, die den Scheitelpunkt enthalten $i$. Und$L_C$ ist auch eine quadratische Diagonalmatrix wo $(L_C u)_i = \sum_j (\cot \alpha_{ij} + \cot \beta_{ij})(u_j-u_i)$ Dies ist kurz gesagt eine Annäherung an den Laplace-Operator am Scheitelpunkt $i$.
So manipulieren Sie die Formel: $(id - tM^{-1}L_C)u = M^{-1}δγ,$ Welches ist die räumlich diskretisierte Form von: $(id - t\Delta)u_t = u_0$.
Das macht also algebraisch Sinn, aber jetzt kommt der Teil, den ich nicht verstehe.
Warum funktioniert das? Warum sollte das Lösen dieser Gleichung die richtige Wärmediffusion ergeben? Lassen Sie mich erklären, was ich meine. In meinem Kopf hängt eine geodätische Entfernung (oder ein Wärmefluss, der für die Zwecke dieser Methode dasselbe ist) stark von der Form eines Netzes ab. Also, um die geodätische Entfernung am Scheitelpunkt zu kennen$i$ Ich muss zuerst die geodätische Entfernung an den Eckpunkten kennen, die relativ zur Quelle davor liegen.
Diese Methode scheint jedoch zu implizieren, dass bei einem beliebigen Netz und einem beliebigen Punkt $p_0$auf diesem Netz. Ich kann jeden beliebigen Punkt erfassen$p_1$ auf dem Netz und sagen Sie, von welcher geodätischen Entfernung $p_1$ zu $p_2$ ist ohne die vollständige Konnektivität des Netzes betrachten zu müssen, um ein Konnektivitätsdiagramm zu bestimmen.
Ich bin mir nicht ganz sicher, ob das, was ich frage, klar ist. Ich verstehe die Algebra des Problems, aber ich kann nicht verknüpfen, wie das Lösen dieser Gleichung Ihnen überall auf einem Netz den richtigen Wärmefluss liefert. Warum können Sie dies parallel tun, ohne Rücksicht auf die spezifischen Konnektivitätsinformationen?
Antworten
Bei der Lösung der Gleichung $(M - tL_C)u = \delta_\gamma$müssen Sie den Operator effektiv umkehren: $$ u = (M - tL_C)^{-1} \delta_\gamma $$ Beachten Sie, dass während der einzelnen Operatoren $M$ und $L_C$sind nur lokal und enthalten Informationen über die einzelnen Eckpunkte und Kanten des Netzes. Der inverse Operator ist entschieden nicht lokal. Inversion ist eine globale Operation, die Informationen über die gesamte invertierte Matrix enthält, dh Informationen über das gesamte Netz. (Beachten Sie, dass$M$ hat eine triviale Umkehrung, da es diagonal ist, aber $L_C$ definitiv nicht.)
In der Praxis berechnen Sie die inverse Matrix möglicherweise nicht buchstäblich, sondern verwenden die Gaußsche Eliminierung oder eine ähnliche Methode, um die zu lösen $u$ für ein gegebenes $\delta_\gamma$. In diesem Fall ist es der Lösungsprozess, der Informationen über das gesamte Netz integriert. Effektiv$L_C$ codiert eine Reihe von Einschränkungen zwischen benachbarten Scheitelpunkten, und der Löser muss alle Einschränkungen über das gesamte Netz gleichzeitig erfüllen.
(Beachten Sie, dass es sich nicht um einen trivial parallelisierbaren Job handelt. Es gibt Methoden zur Verwendung von Parallelität, um das Lösen großer linearer Systeme zu beschleunigen. Es handelt sich jedoch um Multi-Pass-Methoden, mit denen Informationen zwischen verschiedenen "Skalen" des Problems auf und ab übertragen werden wie paralleler Präfix-Scan oder FFT - so etwas.)
Übrigens ist eine andere Perspektive auf diese Gleichung, dass sie nach dem Fixpunkt von löst $u$ im $$ u = M^{-1}(\delta_\gamma + tL_Cu) $$Dies ist eine weitere Möglichkeit, dieselbe Gleichung algebraisch umzuschreiben. In dieser Form sieht es der Rendering-Gleichung sehr ähnlich$L = L_e + \int L \, f_{\text{brdf}}$! Es hat eine ähnliche Struktur, wo$\delta_\gamma$ ist wie die emittierte Ausstrahlung und $L_C$ist wie die Streuung an Oberflächen. Genau wie in der Rendering-Gleichung suchen Sie nach einer globalen Gleichgewichtslösung. (Und wenn das Rendern diskretisiert würde, könnten wir es auf ähnliche Weise lösen, indem wir den Streuoperator in eine Matrix verwandeln und das Ganze in einen linearen Löser werfen.)