Forums Neueste Beiträge
 

Matrix in Teilmatrizen zerlegen

10/06/2009 - 22:55 von Philipp Kraus | Report spam
Hallo,

ich habe eine Matrix (M x N) Elemente und p Prozesse.
Ich möchte nun die Matrix möglichst so in Teilmatrizen
zerlegen, dass jeder Prozess möglichst gleich viele
Elemente erhàlt.

Ich habe schon mehrere Ideen ausprobiert, aber
eine gute Lösung habe ich noch nicht gefunden.
Ich hatte mir überlegt, dass ich die Gesamtzahl
der Elemente gleich auf die Prozesse verteile
und dann diese Elemente quadratisch anordne.

Als Randbedingung gilt, dass die p Prozesse,
die gesamte Anzahl an Elemente verarbeiten
müssen und ich p als fest ansehen muss.
Wenn es Prozesse gibt, die weniger Elemente
berechnen müssen, ist das okay, aber es sollten
möglichst gleich viel Elemente pro Prozess vorhanden
sein, damit jeder optimal ausgelastet wird

Phil
 

Lesen sie die antworten

#1 Stephan Gerlach
11/06/2009 - 23:29 | Warnen spam
Philipp Kraus schrieb:

ich habe eine Matrix (M x N) Elemente und p Prozesse.
Ich möchte nun die Matrix möglichst so in Teilmatrizen



Blockmatrizen?

zerlegen, dass jeder Prozess möglichst gleich viele
Elemente erhàlt.



Ist das so zu verstehen:
a) Du zerlegst eine Matrix in Blockmatrizen.
b) Die entstehenden Blockmatrizen nennst du Prozesse(?).
c) In jedem Prozeß (=Blockmatrix?) sollen möglichst gleich viele
Elemente (=Matrixeintràge?) stehen?

Ich habe schon mehrere Ideen ausprobiert, aber
eine gute Lösung habe ich noch nicht gefunden.



Wenn meine Vermutungen a), b), c) zutreffend sind, ist das zumindest für
den Spezialfall, daß M*N durch p teilbar ist, recht einfach über
Teilbarkeitsargumente lösbar.

Ich hatte mir überlegt, dass ich die Gesamtzahl
der Elemente gleich auf die Prozesse verteile



Dazu muß ja M*N durch p teilbar sein. Andernfalls gibt es immer einen
"Rest".

und dann diese Elemente quadratisch anordne.



Die Form der Matrix ist aber schon vorgegeben? D.h. du kannst nicht
einfach aus einer 5x12-Matrix eine 1x60-Matrix machen (was die ganze
Aufgabenstellung irgendwie unsinnig machen würde).

Als Randbedingung gilt, dass die p Prozesse,
die gesamte Anzahl an Elemente verarbeiten
müssen und ich p als fest ansehen muss.
Wenn es Prozesse gibt, die weniger Elemente
berechnen müssen, ist das okay, aber es sollten
möglichst gleich viel Elemente pro Prozess vorhanden
sein, damit jeder optimal ausgelastet wird



Gehen wir mal vom Idealfall aus, das M*N durch p teilbar ist. Vermutlich
funktioniert Folgendes, an einem Beispiel erklàrt:

1.) Gegeben sei eine MxN-Matrix A und eine ganze Zahl p. Dabei sei p ein
Teiler von M*N, so daß A in genau p gleich große mxn-Blöcke zerlegt
werden soll.
Bsp.: A = 5X12-Matrix (5 Zeilen, 12 Spalten, 60 Elemente gesamt), p = 30

2.) Man bilde den größten gemeinsamen Teiler ggT(M,p) von M und p
Bsp.: ggT(5,30) = 5

3.) Der ggT(M,p) gibt nun an, in wieviele Block*zeilen* A zerlegt wird.
Weiterhin gilt m = M/ggT(M,p).
Bsp.: A besteht bei uns aus 5 Blockzeilen. m = 5/5 = 1

4.) Weiterhin muß gelten m*n*p = M*N. Uns fehlt noch n, dies erhalten
wir mittels n = M*N/(m*p).
Bsp.: n = 60/(1*30) = 2.

Zusammenfassung des Beispiels: Unsere 5x12-Matrix A mit 60 Elementen
wurde in 30 1x2-Blockmatrizen zerlegt.
Das Ganze sollte auch funktionieren, wenn man in 2.) statt des ggT(M,p)
den ggT(N,p) bildet:

2.') Man bilde den größten gemeinsamen Teiler ggT(N,p) von N und p
Bsp.: ggT(12,30) = 6

3.') Der ggT(N,p) gibt nun an, in wieviele Block*spalten* A zerlegt
wird. Weiterhin gilt n = N/ggT(N,p).
Bsp.: A besteht bei uns aus 6 Blockspalten. n = 12/6 = 2

4.') Weiterhin muß gelten m*n*p = M*N. Uns fehlt noch m, dies erhalten
wir mittels m = M*N/(n*p).
Bsp.: m = 60/(2*30) = 1.

Die Zerlegung ist nicht immer eindeutig, jenachdem ob man zuerst m oder
n ausrechnet.
-
Wenn der ungünstige Fall vorliegt, daß M*N *nicht* durch p teilbar ist,
ist es verstàndlicherweise nicht möglich, daß jeder Block gleich viele
Elemente enthàlt. 2 einfache Möglichkeiten, es trotzdem auf den
Teilbarkeits-Fall zurückzuführen:

a) Man rundet p bis zur nàchsten ganzen Zahl auf, die ein Teiler von M*N
ist. Wenn also in unserem Beispiel p = 27 ist, dann tun wir zunàchst so,
als sei p = 30. Wir erhalten dann die erwàhnte Zerlegung von A.
Anschließend fassen wir einfach 6 der 30 1x2-Blöcke zu 3 2x2- oder
1x4-Blöcken zusammen, so daß wir die gewünschte Anzahl von 27 Blöcken
erhalten.

b) Man rundet p bis zur nàchsten ganzen Zahl ab, die ein Teiler von M*N
ist. Wenn also in unserem Beispiel p = 33 ist, dann tun wir zunàchst so,
als sei p = 30. Wir erhalten dann die erwàhnte 30x(1x2)-Zerlegung von A.
Anschließend teilen wir einfach 3 der 30 1x2-Blöcke in 6 1x1-Blöcke auf,
so daß wir die gewünschte Anzahl von 33 Blöcken erhalten.

Eigentlich sollte Brain 1.0 laufen.


gut, dann werde ich mir das morgen mal besorgen...
(...Dialog aus m.p.d.g.w.a.)

Ähnliche fragen