Content deleted Content added
→Cyclic and parallel Jacobi: Removed duplicate word. |
Citation bot (talk | contribs) Added doi. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Numerical linear algebra | #UCB_Category 14/123 |
||
Line 91:
=== Cyclic and parallel Jacobi ===
An alternative approach is to forego the search entirely, and simply have each sweep pivot every off-diagonal element once, in some predetermined order. It has been shown that this ''cyclic Jacobi'' attains quadratic convergence,<ref>{{cite journal |last1=Wilkinson |first1=J.H. |title=Note on the Quadratic Convergence of the Cyclic Jacobi Process |journal=Numerische Mathematik |date=1962 |volume=6 |pages=296–300|doi=10.1007/BF01386321 }}</ref><ref>{{cite journal |last1=van Kempen |first1=H.P.M. |title=On Quadratic Convergence of the Special Cyclic Jacobi Method |journal=Numerische Mathematik |date=1966 |volume=9 |pages=19–22|doi=10.1007/BF02165225 }}</ref> just like the classical Jacobi.
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 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.
| |||