Content deleted Content added
→Cyclic and parallel Jacobi: Rewording. |
→Cyclic and parallel Jacobi: Removed duplicated text. |
||
Line 94:
The opportunity for parallelisation that is particular to Jacobi is based on combining cyclic Jacobi with the observation that Givens rotations for disjoint sets of of indices commute, so that several can be applied in parallel. Concretely, if <math> G_1 </math> pivots between indices <math> i_1, j_1 </math> and <math> G_2 </math> pivots between indices <math> i_2, j_2 </math>, then from <math> \{i_1,j_1\} \cap \{i_2,j_2\} = \varnothing </math> follows <math> G_1 G_2 = G_2 G_1 </math> because in computing <math> G_1 G_2 A </math> or <math> G_2 G_1 A </math> the <math> G_1 </math> rotation only needs to access rows <math> i_1, j_1 </math> and the <math> G_2 </math> rotation only needs to access rows <math> i_2, j_2 </math>. Two processors can perform both rotations in parallel, because no matrix element is accessed for both.
Partitioning the set of index pairs of a sweep into classes that are pairwise disjoint is equivalent to partitioning the edge set of a [[complete graph]] into [[Matching (graph theory)|matching]]s, which is the same thing as [[edge colouring]] it; each colour class then becomes a round within the sweep. The minimal number of rounds is the [[chromatic index]] of the complete graph, and equals <math>n</math> for odd <math>n</math> but <math>n-1</math> for even <math>n</math>. A simple rule for odd <math>n</math> is to handle the pairs <math> \{i_1,j_1\} </math> and <math> \{i_2,j_2\} </math> in the same round if <math> i_1+j_1 \equiv i_2+j_2 \textstyle\pmod{n} </math>. For even <math>n</math> one may create <math> n-1 </math> rounds <math> k = 0, 1, \dotsc, n-2 </math> where a pair <math> \{i,j\} </math> for <math> 1 \leqslant i < j \leqslant n-1 </math> goes into round <math> (i+j) \bmod (n-1) </math> and additionally a pair <math> \{i,n\} </math> for <math> 1 \leqslant i \leqslant n-1 </math> goes into round <math> 2i \bmod (n-1) </math>. This brings the time complexity of a sweep down from <math> O(n^3) </math> to <math> O(n^2) </math>, if <math> n/2 </math> processors are available.
| |||