SC²S Colloquium - June 10, 2009

From Sccswiki
Revision as of 06:51, 5 June 2009 by Weinzier (talk | contribs)
Jump to navigation Jump to search
Date: June 10
Room: 02.07.023
Time: 15 pm, s.t.

15:00 Uhr - Atanas Atanasov - t.b.a.

15:15 Uhr - Sebastian Pohle - Numerical Solution Methods for Nonlinear Equation Systems of the SDSIrep Reputation System (IDP)

Das SDSIrep-Reputationssystem benötigt die Lösung eines großen polynomiellen Gleichungssystems. Als nichtlineare Löser wurden Newton-Verfahren, Newton-ähnliche Verfahren höherer Ordnung sowie nichtlineare Splitting-/Gradientenverfahren angewendet. Für den impliziten linearen Newton-Schritt wurden Splitting- und Gradientenverfahren benutzt. Die Rechnung wurde für verschiedene (dünnbesetzte) Matrix-Repräsentationen ausgeführt, darüber hinaus wurde eine speziell angepasste effiziente Datenstruktur implementiert. Speicherbedarf und Rechenzeit konnten somit von kubisch auf Exponent ~1.5 in der Anzahl der Variablem im Reputations-Gleichungssystem reduziert werden.

The SDSIrep reputation system requires the solution of a large polynomial equation system. Newton’s method, Newton-like higher order methods, and nonlinear splitting/gradient methods are used as nonlinear solver. The implicit linear Newton step utilizes splitting and gradient methods. The computations are made with several (sparse) matrix representations, and an adapted efficient data structure has been implemented. Memory requirement and computation time have been reduced from cubic relation to a power law of exponent ~1.5, with respect to the number of variables in the reputation equation system.