Beispiel Masse-Feder-Feder: Tearing-Algorithmus

• Problem:
  • in Anwendungen algebraische Schleife leicht über viele (100, 1000) Variablen
  • Newton-Solver wird sehr langsam
  • Tearing: reduziere Schleife auf weniger Variable
• Verfahren:
  • wähle eine Gleichung ("Residual Equation") und eine Variable darin ("Tearing Variable")
  • verbinde diese durch eine rote Linie und führe Tarjan-Algorithmus durch

• Resultat:
  • Newton-Verfahren mit nur einer Iterationsvariablen s₄
  • manchmal bleibt kleinere Schleife übrig → iterieren
  • abhängig von der Wahl der Tearing-Variablen!
  • aber: optimale Wahl der Tearing-Variablen NP-vollständig
  • in der Praxis: gute Heuristiken