Optimierung, überbestimmtes Gleichungssystem, auf GPU

20.05.2013, 15:18	DemolitionMan	Auf diesen Beitrag antworten »
Optimierung, überbestimmtes Gleichungssystem, auf GPU Hallo, Problem: ich habe ein Optimierungsproblem, dieses ist bereits linearisiert und in Form eines überbestimmten Gleichungssystems vorliegend. Es soll gelöst werden: $\begin{eqnarray} A x = a \end{eqnarray}$ wobei A eine 307200 × 6 Matrix ist. x ist ein Vektor mit den 6 gesuchten Elementen und a ein Vektor mit 307200 Elementen. Es ist davon auszugehen, dass etwa 50% der Zeilen keine Informationen beinhalten, also 0 sind. Dieses Problem soll auf einer Grafikkarte gelöst werden (die Berechnungen sollten in Blöcke mit je 256 oder 512 Threads aufgeteilt werden). Lösung 1:* Einteilung der 307200 Zeilen in Blöcke der Größe 256 Zeilen. Man erhält also 1200 Mal (307200/256): $\begin{eqnarray} A_k \textrm{ und } a_k \textrm{, mit } 0 \leq k \leq 1200 \end{eqnarray}$ in jedem Block wird bestimmt: $\begin{eqnarray} B_k = A_k^\mathrm{T} A_k \textrm{ und } b_k = A_k^\mathrm{T} a_k \end{eqnarray}$ Die Matrixen haben nun die Größe 6 × 6 und Vektoren passend 6 Elemente. Zuletzt werden die Matrix C und der Vektor c bestimmt als elementweise Summe. z.B. (analog für c): $\begin{eqnarray} C_{ij} = \sum_{0 \leq k \leq 1200}(B_k)_{ij} \end{eqnarray}$ Abschließend erfolgt die Lösung von Cx=c. Lösung 2:* Reduzierung der 307200 Zeilen auf 512 Zeilen indem die elementweise Summe berechnet wird (analog für den Vektor c): $\begin{eqnarray} B_{ij} = \sum_{0 \leq k \leq 600} A_{i+k512,j} \textrm{, mit } 0 \leq i < 512 \end{eqnarray}$ B ist nun eine 512 × 6 Matrix und b ein Vektor mit 512 Elementen. Anschließend wird die Lösung berechnet für: $\begin{eqnarray} B^\mathrm{T} B * x = B^\mathrm{T}b \end{eqnarray}$ Bewertung: Beide Lösungen sind nahezu ausreichend schnell, wobei mir Lösung 2 lieber wäre. Die Ergebnisse von Lösung 1 sind ausreichend stabil und genau. Leider sind die Ergebnisse von Lösung 2 schlechter und nicht mehr ausreichend. Fragen: Wie kann man die Fehler (Differenz zur Lösung mit minimalem quadratischen Fehler) der beiden Lösungen abschätzen? Gibt es eine bessere Lösung? Vielen Dank

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »